# 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

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 updated