Обратная польская запись (RPN)

Обратная польская запись (постфиксная) записывает оператор после операндов, что избавляет от скобок и приоритетов. Выражение вычисляется за один проход стеком: числа кладутся на стек, оператор снимает два верхних значения и кладёт результат.

Сложность: время O(n) по длине выражения; память: O(n) под стек. Классическое применение стека в разборе выражений.

def eval_rpn(tokens):
    stack = []
    ops = {"+", "-", "*", "/"}
    for t in tokens:
        if t in ops:
            b, a = stack.pop(), stack.pop()
            stack.append(int(eval(f"{a}{t}{b}")))
        else:
            stack.append(int(t))
    return stack[0]

print(eval_rpn(["2", "3", "+", "4", "*"]))  # 20