Обратная польская запись: принцип работы и преимущества

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

Обратная польская запись (ОПЗ) – это форма записи математических выражений, в которой операторы располагаются после своих операндов. Это означает, что в ОПЗ сначала указываются все операнды, а затем оператор, выполняемый над этими операндами. Такая форма записи упрощает вычисление выражений, поскольку нет необходимости в использовании скобок и приоритетов операций.

Одним из способов преобразования обычного инфиксного выражения в ОПЗ является использование стека. Идея заключается в просмотре выражения слева направо и выполнении следующих шагов:

1. Создать пустой стек операций.
2. Проходить по каждому символу в выражении.
3. Если символ является операндом (числом), добавить его в выходную строку.
4. Если символ является открывающей скобкой, поместить его в стек.
5. Если символ является оператором, выполнить следующие действия:
   1. Пока есть операторы в стеке и их приоритет больше или равен приоритету текущего оператора, добавлять операторы из стека в выходную строку.
   2. Поместить текущий оператор в стек.
6. Если символ является закрывающей скобкой, то:
   1. Пока верхний оператор стека не является открывающей скобкой, добавлять операторы из стека в выходную строку.
   2. Удалить открывающую скобку из стека.
7. После обработки всех символов, добавить все оставшиеся операторы из стека в выходную строку.

Приведу пример преобразования выражения "2 + 3 * 4" в ОПЗ:

1. Создаем пустой стек и пустую выходную строку.

2. Проходим по каждому символу: '2', '+', '3', '*', '4'.

3. '2' является операндом, добавляем его в выходную строку: "2".

4. '+' является оператором, добавляем его в стек.

5. '3' является операндом, добавляем его в выходную строку: "2 3".

6. '*' является оператором, приоритет которого выше чем у '+'. Поэтому добавляем '+' в выходную строку, а затем '*' в стек.

7. '4' является операндом, добавляем его в выходную строку: "2 3 4".

8. Заканчиваем обработку символов, добавляем все оставшиеся операторы из стека в выходную строку: "2 3 4 * +".

Таким образом, выражение "2 + 3 * 4" в ОПЗ будет выглядеть как "2 3 4 * +".

Теперь рассмотрим пример кода на языке Python, который преобразует инфиксное выражение в ОПЗ:

def infix_to_rpn(expression):
    operator_stack = []
    output_queue = []
    operators = {'+': 1, '-': 1, '*': 2, '/': 2}  # операторы и их приоритеты

    for char in expression:
        if char.isdigit():
            output_queue.append(char)
        elif char in operators:
            while operator_stack and operators[char] <= operators.get(operator_stack[-1], 0):
                output_queue.append(operator_stack.pop())
            operator_stack.append(char)
        elif char == '(':
            operator_stack.append(char)
        elif char == ')':
            while operator_stack[-1] != '(':
                output_queue.append(operator_stack.pop())
            operator_stack.pop()

    while operator_stack:
        output_queue.append(operator_stack.pop())

    return ' '.join(output_queue)


if __name__ == '__main__':
    infix_expression = "2 + 3 * 4"
    rpn_expression = infix_to_rpn(infix_expression)
    print(rpn_expression)

В этом примере функция infix_to_rpn принимает инфиксное выражение в качестве аргумента и возвращает преобразованное выражение в ОПЗ. Приоритеты операторов заданы в словаре operators. Выражение "2 + 3 * 4" преобразуется в ОПЗ и выводится на экран. Результатом будет "2 3 4 * +".

ОПЗ – эффективный способ записи и вычисления математических выражений. С его помощью можно упростить обработку и решение сложных вычислительных задач.