rpn

Reverse Polish Notation

Reverse Polish notation | Wikipedia, aka the postfix notation.

Reduce List in Place

Very straightforward solution. This solution runs in $O(n)$ time, since modifying a list takes $O(n)$ time, and we’re scanning the list from left to right, conducted $O(n)$ operations. The space complexity is nicely $O(1)$.

With a doubly-linked list, this algorithm can be reduced to $O(n)$ time, since we’re traversing it.

operations = {
    "+": lambda a, b: a + b,
    "-": lambda a, b: a - b,
    "/": lambda a, b: int(a / b),
    "*": lambda a, b: a * b,
}
 
i = 0
 
while len(tokens) > 1:
    while tokens[i] not in operations:
        i += 1
 
    operator = tokens[i]
    operand1 = int(tokens[i - 2])
    operand2 = int(tokens[i - 1])
 
    tokens[i] = operations[operator](operand1, operand2)
 
    tokens.pop(i - 2)
    tokens.pop(i - 2)
    i -= 1  # move on to the next value
 
return int(tokens[0])

The dictionary of lambda functions can also be replaced with a match statement.

Evaluate with Stack

operations = {
    "+": lambda a, b: a + b,
    "-": lambda a, b: a - b,
    "/": lambda a, b: int(a / b),
    "*": lambda a, b: a * b,
}
 
operands = []
for token in tokens:
    if token in operations:
        operation = operations[token]
        operand1 = operands.pop()
        operand2 = operands.pop()
        operands.append(operation[token](operand1, operand2))
    else:
        operands.append(int(token))
return operands.pop()