To convert an expression tree to infix notation, you perform an in-order traversal of the tree. During traversal, if a node is an operator, you enclose its children in parentheses.
Here's an example code in Python to demonstrate the construction, evaluation, and conversion of an expression tree:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def construct_expression_tree(postfix):
stack = []
operators = {'+', '-', '*', '/'}
for char in postfix:
if char not in operators:
node = Node(char)
stack.append(node)
else:
right_operand = stack.pop()
left_operand = stack.pop()
operator_node = Node(char)
operator_node.left = left_operand
operator_node.right = right_operand
stack.append(operator_node)
return stack.pop()
def evaluate_expression_tree(root):
if root is None:
return 0
if root.value.isdigit():
return int(root.value)
left_val = evaluate_expression_tree(root.left)
right_val = evaluate_expression_tree(root.right)
if root.value == '+':
return left_val + right_val
elif root.value == '-':
return left_val - right_val
elif root.value == '*':
return left_val * right_val
elif root.value == '/':
return left_val / right_val
def infix_expression(root):
if root:
if root.left or root.right:
print('(', end='')
infix_expression(root.left)
print(root.value, end='')
infix_expression(root.right)
if root.left or root.right:
print(')', end='')
# Example usage:
postfix_expression = "ab+cde+**"
expression_tree = construct_expression_tree(postfix_expression)
print("Infix Expression:")
infix_expression(expression_tree)
print("\nEvaluation:", evaluate_expression_tree(expression_tree))
This code demonstrates the construction of an expression tree from a postfix expression, evaluation of the expression tree, and conversion of the expression tree to infix notation.
