Обратная польская запись: что это такое и как с ней работать?

Обратная польская запись (ОПЗ) – это форма записи математических выражений, в которой операторы расположены после операндов. Например, выражение "2 + 3" может быть записано в ОПЗ как "2 3 +" (где "+" - оператор сложения).

Для работы с ОПЗ используется стек. Алгоритм вычисления выражения заключается в последовательной обработке каждого элемента ОПЗ. Если текущий элемент является операндом, он помещается в стек. Если текущий элемент - оператор, то из стека извлекаются два последних операнда, над которыми выполняется операция согласно текущему оператору. Результат операции помещается в стек. После обработки всего выражения, в стеке останется один элемент - результат его вычисления.

Пример кода на языке Python, реализующий алгоритм вычисления выражения в ОПЗ:

python
def eval_rpn(rpn: List[str]) -> int:
    stack = []
    for val in rpn:
        if val.isdigit():
            stack.append(int(val))
        else:
            op2 = stack.pop()
            op1 = stack.pop()
            if val == '+':
                res = op1 + op2
            elif val == '-':
                res = op1 - op2
            elif val == '*':
                res = op1 * op2
            else:
                res = op1 // op2
            stack.append(res)
    return stack.pop()

В этом примере функция `eval_rpn` принимает список строк `rpn`, представляющий выражение в ОПЗ, и возвращает его значение. Каждый элемент списка проверяется на наличие цифр (операндов) с помощью метода `isdigit()`. Если элемент является операндом, он преобразуется в целое число и помещается в стек. Если элемент является оператором, из стека извлекаются два последних операнда, над которыми выполняется соответствующая операция. Результат помещается в стек. После обработки всего выражения в стеке остается один элемент - результат его вычисления, который и возвращается.

Пример использования функции:

python
>>> rpn = ['2', '3', '+', '4', '-']
>>> eval_rpn(rpn)
1

В этом примере выражение "2 3 + 4 -" в ОПЗ соответствует выражению "(2 + 3) - 4" в инфиксной записи. Результат вычисления выражения равен 1.