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())