Expression tree is a binary tree in which the operators are stored in the interior nodes and the operands are stored in the exterior nodes which are the leaves. An expression tree can be used to evaluate the expression or for converting an
infix expression to either
Infix: An expression where the operator is placed in between the operands. \
Ex: (A+B) * (C-D) \
Prefix: An expression where the operator is in the expression before the operands. \
The expression tree structure is dependent on which the order of the operators is evaluated. The operator in every internal node is evaluated when each of its left and right subtrees is evaluated. In this manner, the lower an operator is in a subtree, the prior it will be evaluated. The root node contains the
operator to be evaluated.
To build expression trees, we use the stack data structure. We iterate over each character when a postfix string expression is passed and determine if it will be pushed on to our stack or not.
1. We push it onto the stack if the character is an operand. \
2. We pop two elements from the stack if the character is an operator, make them the character's left and right node child, and push the sequence back into the stack.
Note: Repeat the above steps until end of Prefix expression.
Let’s pass the postfix expression
The first character is
x; we push it onto the stack. The next character is
y; we also push it onto the stack. The final character is the
‘-’ operator; we pop
y and make them left and right child of
‘-’. So we end up with
x - y as our Infix expression.
# Python program for expression tree # create a class for an expression tree node class Expression_tree: # Constructor to create a node def __init__(self , value): self.value = value self.left = None self.right = None # function to check if 'c' is an operator def isOperator(c): if (c == '+' or c == '-' or c == '*' or c == '/' or c == '^'): return True else: return False # function to do inorder traversal # Process all nodes of a tree by recursively processing the left subtree, the root, and finally the right subtree. def inorder(t): if t is not None: inorder(t.left) print (t.value, end=" ") inorder(t.right) # Returns root of constructed tree for given postfix expression def constructTree(postfix): stack =  # Traverse through every character of input expression # Traverse - process every character in a string, from left end to right end. for char in postfix : # if operand, push into stack if not isOperator(char): t = Expression_tree(char) stack.append(t) # Operator else: # Pop two top nodes t = Expression_tree(char) t1 = stack.pop() t2 = stack.pop() # make them left and right children t.right = t1 t.left = t2 # Add this subexpression to stack stack.append(t) # Only element will be the root of expression tree t = stack.pop() return t # Driver program to test above postfix = "ab*ef-g+i-" r = constructTree(postfix) print ("Infix expression: ") inorder(r)