UniLecs #157. Reverse Polish notation

Задача: обратная польская запись (RPN) - это форма записи математических выражений, в которой операнды расположены перед знаками операций. Это постфиксная запись, которая позволяет обходится без скобок в арифметических выражениях.

Давайте объясним суть на конкретных примерах:

Например,

- выражение 1 + 3 в польской нотации будет: 1 3 +

- выражение 1 * 3 + 5 в польской нотации будет: 1 3 * 5 +

- выражение 1 * (3 + 5) в польской нотации будет: 1 3 5 + *

Вам необходимо вычислить арифметическое выражение записанное в польской нотации.

Входные данные: str - строка, в которой записано арифметическое выражение в польской нотации. Каждый операнд (число, операция) разделен пробелом.

Вывод: результат арифметического выражения.

Примечание: для простоты используйте следующие возможные операции:

+, -, *, /.

Пример:

1. str = "7 2 3 * -"; Answer = 1. Пояснение: 7 - 2 * 3 = 1

2. str = "10 15 - 3 *"; Answer = -15. Пояснение: (10 - 15) * 3 = -15

3. str - "3 10 15 - *"; Answer = -15. Пояснение: 3 * (10 - 15) = -15

Идея: исходим из алгоритма работы польской записи, операция применяется в последним двум числам, а результат это операции применяется к элементу стоящему перед ними. Т.е. числа мы перебираем с конца, а операции с начала. Поэтому для реализации вычисления такой записи напрашивается стек.

Итак, вот алгоритм:

Обрабатываем строку с начала:

• если текущий операнд - это число, то заносим его в стек.
• если текущий операнд - это арифм.операция, то достаем из стека последние два числа, вычисляем текущую операцию и результат заносим в стек.

Проводим эту операцию до конца строки. В результате в стеке должно остаться одно число - это и будет результатом всего арифметического выражения.

Для большей наглядности покажем схематический пример:

10 15 - 3 * = (10 - 15) * 3 = -15

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

Забавный факт: существует несколько языков программирования (Forth, Factor, Postscript, BibTeX), которые используют обратную польскую запись в качестве основной для арифметических операций.

Реализация:

https://gist.github.com/unilecs/3aaca1242cf208015b08fc43cd73d994

Play-test: https://dotnetfiddle.net/fzuhUG