Given an infix expression which contains three operators ‘+’, ‘-’ and ‘*’, operating on non-negative integers. Build a corresponding syntax tree for it.
To parse such infix expressions, use the grammar below.
Expression := Term | Expression ADDSUB(+ -) Term
Term := Factor | Term MUL(*) Factor
Factor := Integer
You are provided with function.h and main.c, where function.h contains the declarations/definitions of the involved data structures, variables, constants, and functions, while main.c contains the implementation of two functions printPrefix and FACTOR. You only need to implement the following five functions in function.c.
Node* EXPR() // parse an infix expression and generate its syntax tree
Node* TERM() // handle the rule Term := Factor | Term MUL Factor
Node* makeNode(char c, int value) // create a tree node without any child
void freeTree(Node *root) // free the whole tree
long long calculate(Node *root) // calculate the result of the infix expression
For OJ submission:
Step 1. Submit only your function.c into the submission block. (Please choose C compiler)
Step 2. Check the results and debug your program if necessary.
The input consists of multiple lines. Each line is an infix expression.
The input integers are guaranteed to be less than 1000, and all the intermediate values during caculation won't exceed 1018 (don't need to consider overflow if you use long long).
The length of each expression is less than 106. Total length of all lines is less than 107.
For each infix expression, print its prefix expression and result.