In this problem, you have to build a Boolean expression with right associativity into a syntax tree.
The associativity of an operator is a property that determines how operators of the same precedence are grouped in the absence of parentheses.
EX.
Consider the expression: A&B|C
With left associativity, the expression is interpreted as:
(A&B)|C
With right associativity, the expression is interpreted as:
A&(B|C)
Given an infix Boolean expression with parentheses, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Build a corresponding syntax tree for it following right associativity.
To parse the infix expression with parentheses following right associativity, use the grammar below.
EXPR = FACTOR | FACTOR OP EXPR
FACTOR = ID | (EXPR)
EXPR is the expression, ID is one of ‘A’, ‘B’, ’C’, or ‘D’, and OP is one of ‘&’ or ‘|’.
You will be provided with main.c and function.h. main.c contains the implementation of functions printPrefix and freeTree. function.h contains the definition of tree node and variables. You only need to implement the following three functions in function.c.
BTNode* makeNode(char c) // create a node without any child
BTNode* EXPR() // parse an infix expression and generate a syntax tree
BTNode* FACTOR() // use the parse grammar FACTOR = ID | (EXPR) to deal with parentheses
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 contains N infix expressions, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, two operators ‘&’ and ‘|’, and parentheses. All parentheses are matched.
The output contains N prefix expressions without parentheses, which are preorders of syntax trees.