Evaluating expressions

In infix notation, the form people write, operators sit between numbers: 3 + 2 * 2. To evaluate it correctly you must follow precedence (* and / before + and -), left-to-right order for equal precedence, and parentheses.

In postfix notation (Reverse Polish Notation, RPN) the operator comes after its operands: 3 2 2 * +. Postfix needs no parentheses or precedence rules: you push numbers, and each operator pops two numbers and pushes the result. Dijkstra's shunting-yard algorithm converts infix to postfix with an operator stack, and calculators, compilers and interpreters use these ideas.

1. 1Postfix: scan tokens. A number is pushed. An operator pops b (top) then a, computes a op b and pushes the result. At the end the stack holds exactly one value.
2. 2Infix without parentheses (Basic Calculator II): read digits into num. When you reach an operator or the end, apply the previous operator: '+' pushes num, '-' pushes -num, '*' and '/' pop the top, combine it with num and push. The answer is the sum of the stack. Multiplication and division are applied immediately, additions are deferred, which is how precedence is respected.
3. 3Infix with parentheses and + and - only (Basic Calculator I): keep a running result and sign; on '(' push the current result and sign and reset; on ')' pop them and combine.
4. 4General infix (shunting-yard): use a number stack and an operator stack. Before pushing an operator, apply operators on the stack with higher or equal precedence (for left-associative operators). '(' is pushed; ')' applies operators until the matching '('.
5. 5Integer division in these problems usually truncates toward zero. In Python, -7 // 2 is -4 (floor), so use int(a / b) or handle signs explicitly.

def eval_rpn(tokens):
    stack = []
    for tok in tokens:
        if tok in {"+", "-", "*", "/"}:
            b, a = stack.pop(), stack.pop()      # order matters for - and /
            if tok == "+": stack.append(a + b)
            elif tok == "-": stack.append(a - b)
            elif tok == "*": stack.append(a * b)
            else: stack.append(int(a / b))       # truncate toward zero
        else:
            stack.append(int(tok))
    return stack[0]


def calculate(s):
    """+, -, *, / on non-negative integers, no parentheses."""
    stack, num, op = [], 0, "+"
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if ch in "+-*/" or i == len(s) - 1:
            if op == "+": stack.append(num)
            elif op == "-": stack.append(-num)
            elif op == "*": stack.append(stack.pop() * num)
            else: stack.append(int(stack.pop() / num))
            op, num = ch, 0
    return sum(stack)

eval_rpn is O(n) time and space; note b is popped before a. calculate handles + - * / with spaces and multi-digit numbers in O(n): spaces are skipped because they are neither digits nor operators, and the last character always triggers the final operation.

Cost: Time O(n) in the number of characters or tokens. Space O(n) for the stacks in the worst case (deep nesting or many pending additions).