alexander joslin github github comechoaj explanation https medium comhaleesammarimplementedinjsdijkstras2stack algorithmforevaluatingmathematicalexpressionsfc0837dae1ea we can use dijkstra s two stack algorithm to solve an equation such as 5 4 2 2 3 these are the algorithm s rules rule 1 scan the expression from left to right when an operand is encountered push it onto the operand stack rule 2 when an operator is encountered in the expression push it onto the operator stack rule 3 when a left parenthesis is encountered in the expression ignore it rule 4 when a right parenthesis is encountered in the expression pop an operator off the operator stack the two operands it must operate on must be the last two operands pushed onto the operand stack we therefore pop the operand stack twice perform the operation and push the result back onto the operand stack so it will be available for use as an operand of the next operator popped off the operator stack rule 5 when the entire infix expression has been scanned the value left on the operand stack represents the value of the expression note it only works with whole numbers doctests dijkstrastwostackalgorithm5 3 8 dijkstrastwostackalgorithm9 2 9 8 1 5 dijkstrastwostackalgorithm3 2 2 3 2 4 3 3 param equation a string return result an integer rule 1 rule 2 rule 4 rule 5 answer 45 doctests dijkstras_two_stack_algorithm 5 3 8 dijkstras_two_stack_algorithm 9 2 9 8 1 5 dijkstras_two_stack_algorithm 3 2 2 3 2 4 3 3 param equation a string return result an integer rule 1 rule 2 rule 4 rule 5 answer 45
__author__ = "Alexander Joslin"

import operator as op

from .stack import Stack


def dijkstras_two_stack_algorithm(equation: str) -> int:
    
    operators = {"*": op.mul, "/": op.truediv, "+": op.add, "-": op.sub}

    operand_stack: Stack[int] = Stack()
    operator_stack: Stack[str] = Stack()

    for i in equation:
        if i.isdigit():
            
            operand_stack.push(int(i))
        elif i in operators:
            
            operator_stack.push(i)
        elif i == ")":
            
            opr = operator_stack.peek()
            operator_stack.pop()
            num1 = operand_stack.peek()
            operand_stack.pop()
            num2 = operand_stack.peek()
            operand_stack.pop()

            total = operators[opr](num2, num1)
            operand_stack.push(total)

    
    return operand_stack.peek()


if __name__ == "__main__":
    equation = "(5 + ((4 * 2) * (2 + 3)))"
    
    print(f"{equation} = {dijkstras_two_stack_algorithm(equation)}")