Question

Объясните Обратную польскую запись

Answer 1

Есть стек чисел (условно) бесконечной глубины.

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

Это дает возможность выполнять сложные вычисления с учетом правил приоритета операторов, т. к. можно хранить результаты предыдущих вычислений в стеке.

Например, (5 + 1) * (6 - 2) запишется так:
5 1 + (сейчас в стеке по адресу 0 лежит 6) 6 2 - (сейчас в стеке по адресу -1 лежит 6, а по адресу 0 лежит 4) * (сейчас в стеке по адресу 0 лежит 24).

Стек:

Адрес Число
0  24
-1  -
-2  -
...  -

Answer 2

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

Рассмотрим пример обычного инфиксного выражения (выражение, в котором операторы располагаются между операндами с использованием скобок для определения порядка выполнения операций):

Инфиксное выражение: 3 + 5 * 2

Теперь переведем это выражение в обратную польскую запись:

Шаг 1: Создаем пустой стек для операторов. Шаг 2: Обрабатываем выражение слева направо.

Текущий символ: 3 Добавляем 3 в выходную строку.

Текущий символ: + Добавляем + в стек.

Текущий символ: 5 Добавляем 5 в выходную строку.

Текущий символ: * Стек: + * Так как * имеет более высокий приоритет, чем +, добавляем * в стек.

Текущий символ: 2 Добавляем 2 в выходную строку.

Шаг 3: Завершаем обработку выражения и переносим оставшиеся операторы из стека в выходную строку.

Стек: + * Переносим * из стека в выходную строку.

Выходная строка: 3 5 2 *

Таким образом, выражение "3 + 5 * 2" в обратной польской записи будет выглядеть как "3 5 2 * +".

Чтобы вычислить значение выражения в ОПЗ, можно прочитать выражение слева направо, выполняя операции над операндами с помощью стека. В нашем примере:

1. Читаем 3 и помещаем его в стек: Стек: 3
2. Читаем 5 и помещаем его в стек: Стек: 3, 5
3. Читаем *, выполняем операцию над двумя последними элементами стека (5 и 2), помещаем результат (10) в стек: Стек: 3, 10
4. Читаем +, выполняем операцию над двумя последними элементами стека (3 и 10), помещаем результат (13) в стек: Стек: 13

После чтения всего выражения, остается только одно значение в стеке - результат выражения. В нашем случае результат равен 13.