Comment on page
Infix to Postfix Expression Evaluater
Evaluate a generic mathematical expression.
Examples:
input: 10 + 2 * 8 - 3
output: 23
input: 10 - 2 ^ 8 * 3
output: -758
The Idea: Convert the expression from Infix (AOB) to Postfix (ABO), where A and B are numbers and O is an operator. The algorithms go as follows:
Infix to Postfix:
- 1.Maintain a stack and scan the infix expression from left to right.
- 2.When we get a number, output it.
- 3.When we get an operator O, pop the top element in the stack until there is no operator having higher priority then O and then push(O) into the stack.
- 4.When the expression is ended, pop all the operators remain in the stack
Postfix to Answer:
- 1.Maintain a stack and scan the postfix expression from left to right.
- 2.When we get a number, place it into the stack.
- 3.When we get an operator O, pop two elements from the stack and append new number O(a, b).
- 4.In the end, return the top of the stack.
Complexity: O(n) time and space
import operator as op
class SimpleExpressionEval:
def __init__(self, expression):
# PEMDAS - paren, exp, mult, div, add, sub - define the operator priorities
self.ops = {'^': 3, '*': 2, '/': 2, '+': 1, '-': 1}
self.expression = expression
def eval_expression(self):
# infix to postfix to answer
postfix = self._infix_to_postfix()
return self.postfix_to_ans(postfix)
def _infix_to_postfix(self):
s = []
str_builder = []
tokens = self.expression.split(' ')
for token in tokens:
if token in self.ops:
# pop until top of s has lower priority or is empty
while s and self.ops[s[-1]] >= self.ops[token]:
str_builder.append(s[-1])
s.pop()
s.append(token)
else:
str_builder.append(token)
while s:
str_builder.append(s[-1])
s.pop()
return ' '.join(str_builder)
def postfix_to_ans(self, postfix):
s = []
map_op = {'+': op.add, '-': op.sub, '*': op.mul, '/': op.truediv, '^': op.pow}
tokens = postfix.split(' ')
for token in tokens:
if token in self.ops:
num1 = s[-1]
s.pop()
num2 = s[-1]
s.pop()
s.append(map_op[token](int(num2), int(num1)))
else:
s.append(token)
return s[-1]
obj = SimpleExpressionEval("10 + 2 * 8 - 3")
print(obj.eval_expression())
obj2 = SimpleExpressionEval("10 - 2 ^ 8 * 3")
print(obj2.eval_expression())
Last modified 4yr ago