Description

Kuo-chan wants to build a syntax tree for infix algebraic expressions with number, addition, subtraction, and parentheses.

To parse the infix expressions, he can use the grammar below.

EXPR = FACTOR | EXPR OP FACTOR

FACTOR = ID | (EXPR)

EXPR is the expression. ID is the number. OP is either + (addition) or - (subtraction).

Please help Kuo-chan to build the syntax tree.

You can use the following default code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h> //for isdigit() 

typedef struct _Node {
    int value;
    char OP;
    struct _Node *left;
    struct _Node *right;
} Node;

char expr[120];
int pos;
Node *head;

Node* Factor();
Node* Expr();
void PrefixPrint(Node* node);

Node* CreateNode(int value , char ch) {
    Node *newNode;
    newNode = (Node*) malloc(sizeof(Node));
    
    if(ch == 'N') {
        newNode->value = value;
        newNode->OP = 'N';
    }
    else {
        newNode->value = -1;
        newNode->OP = ch;
    }
    return newNode;
}

int main() {
    while((scanf("%s" , expr)) != EOF) {
        pos = strlen(expr) - 1;
        head = Expr();
        PrefixPrint(head);
        printf("\n");
        head = NULL; 
    }
    
    return 0;
}

Input

There're multiple testcases. 

Every number is positive and smaller than 10⁹.

All parentheses are matched. 

The length of every input is at most 100.

 

Different testcases have different constraints.

1. All number is smaller than 10. No parentheses.
2. All number is smaller than 10. No nested parentheses such as (1+(2)), but (1)+(2) is permitted.
3. All number is smaller than 10. 
4. No parentheses.
5. No nested parentheses.
6. No extra constraints.

Output

The output contains N prefix expressions without parentheses, which are preorders of syntax trees.

Please ouput a whitespace after every number, addition, and subtraction. Read the sample output for more detail.

Remember to add new line in the end.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss