the expression is (3 + 2 * 6) / (8 – 5) Please use C++ or Python Design and impl
ID: 3855301 • Letter: T
Question
the expression is (3 + 2 * 6) / (8 – 5)
Please use C++ or Python
Design and implement an algorithm which takes a binary tree representing an arithmetic expression, and evaluate the binary expression it represents, using: (a) In-order traversal of the tree (b) Produces the reverse Polish expression corresponding to the tree obtained by post-order tree traversal, and (c) it evaluates the reverse Polish expression, showing all the necessary steps, by using a stack as follows a. the expression is scanned from left to right b. if an operand is encountered, it is pushed on the stack c. if an operator is encountered two elements are popped from the stack, the operator ids applied to them, and the result is pushed on the stack. d. At the end the result is popped from the stack For the expression given above, the reverse Polish expression, obtained by post-order traversal is 326*+85-/and the stack evolution is as follows:Explanation / Answer
class Stack :
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def InfixToPostfix(expression):
precedence = {}
precedence["*"] = 3
precedence["/"] = 3
precedence["+"] = 2
precedence["-"] = 2
precedence["("] = 1
data_stack = Stack()
postfix_exp = []
tokens = expression.split()
for token in tokens:
if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
postfix_exp.append(token)
elif token == '(':
data_stack.push(token)
elif token == ')':
top_token = data_stack.pop()
while top_token != '(':
postfix_exp.append(top_token)
top_token = data_stack.pop()
else:
while (not data_stack.is_empty()) and (precedence[data_stack.peek()] >= precedence[token]):
postfix_exp.append(data_stack.pop())
data_stack.push(token)
while not data_stack.is_empty():
postfix_exp.append(data_stack.pop())
return " ".join(postfix_exp)
def eval_postfix(postfixExpr):
operand_stack = Stack()
Tlist = postfixExpr.split()
for token in Tlist:
if token in "0123456789":
operand_stack.push(int(token))
else:
operand2 = operand_stack.pop()
operand1 = operand_stack.pop()
result = evaluate(token,operand1,operand2)
operand_stack.push(result)
return operand_stack.pop()
def evaluate(op, op1, op2):
if op == "*":
return op1 * op2
elif op == "/":
return op1 / op2
elif op == "+":
return op1 + op2
else:
return op1 - op2
print("Infix expression is 5 + 6")
postfix=InfixToPostfix("5 + 6")
print("postfix expression is",postfix)
print("Result is",eval_postfix(postfix))
======================================================
Output:
akshay@akshay-Inspiron-3537:~/Chegg$ python infit.py
Infix expression is 5 + 6
('postfix expression is', '5 6 +')
('Result is', 11)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.