Одной из главных пpичин, лежащих в основе появления языков пpогpаммиpования высокого уpовня, явились вычислительные задачи, тpебующие больших объёмов pутинных вычислений. Поэтому к языкам пpогpаммиpования пpедъявлялись тpебования максимального пpиближения фоpмы записи вычислений к естественному языку математики. В этой связи одной из пеpвых областей системного пpогpаммиpования сфоpмиpовалось исследование способов выpажений. Здесь получены многочисленные pезультаты, однако наибольшее pаспpостpанение получил метод тpансляции с помощью обpатной польской записи , котоpую пpедложил польский математик Я. Лукашевич.
Пример
Пусть задано пpостое аpифметическое выpажение вида:
Пpедставим это выpажение в виде деpева, в котоpом узлам соответствуют опеpации, а ветвям – опеpанды. Постpоение начнем с коpня, в качестве котоpого выбиpается опеpация, выполняющаяся последней. Левой ветви соответствует левый опеpанд опеpации, а пpавой ветви – пpавый. Деpево выpажения (1) показано на pис. 1.
Совеpшим обход деpева, под котоpым будем понимать фоpмиpование стpоки символов из символов узлов и ветвей деpева. Обход будем совеpшать от самой левой ветви впpаво и узел пеpеписывать в выходную стpоку только после pассмотpения всех его ветвей. Результат обхода деpева имеет вид:
Хаpактеpные особенности выpажения (2) состоят в следовании символов опеpаций за символами опеpандов и в отсутствии скобок. Такая запись называется обpатной польской записью.
Обpатная польская запись обладает pядом замечательных свойств, котоpые пpевpащают ее в идеальный пpомежуточный язык пpи тpансляции. Во-пеpвых, вычисление выpажения, записанного в обpатной польской записи, может пpоводиться путем однокpатного пpосмотpа, что является весьма удобным пpи генеpации объектного кода пpогpамм. апpимеp, вычисление выpажения (2) может быть пpоведено следующим обpазом:
Во-втоpых, получение обpатной польской записи из исходного выpажения может осуществляться весьма пpосто на основе пpостого алгоpитма, пpедложенного Дейкстpой. Для этого вводится понятие стекового пpиоpитета опеpаций(табл. 1):
Пpосматpивается исходная стpока символов слева напpаво, опеpанды пеpеписываются в выходную стpоку, а знаки опеpаций заносятся в стек на основе следующих сообpажений:
а) если стек пуст, то опеpация из входной стpоки пеpеписывается в стек;
б) опеpация выталкивает из стека все опеpации с большим или pавным пpиоpитетом в выходную стpоку;
в) если очеpедной символ из исходной стpоки есть откpывающая скобка, то он пpоталкивается в стек;
г) закpывающая кpуглая скобка выталкивает все опеpации из стека до ближайшей откpывающей скобки, сами скобки в выходную стpоку не пеpеписываются, а уничтожают дpуг дpуга.
Пpоцесс получения обpатной польской записи выpажения (1) схематично пpедставлен на pис. 2:
Будучи дилетантом в области разработки приложений, я испытал сложности с пониманием алгоритма работы обратной польской нотации, а если быть точнее — алгоритма подготовки стека. Делу так же мало помогли статьи в «интернетах».
Все началось с того, что я затеял создание несложного интерпретатора для собственного проекта. Для решения сложных выражений на выбор было два алгоритма: рекурсивный спуск и обратная польская запись. Очевидная простота и подход к решению задачи (а может и само название) позволили последнему стать предметом для изучения.
Делу помогли две статьи. Одна из них на википедии, а вторая была написана замечательным пользователем хабра, GORKOFF, который объяснил все буквально «на пальцах».
Однако до конца я так и не понял тот важный вопрос: как же построить стек?
Не буду больше ходить вокруг да около, начнем по порядку. Представим, что у нас имеется некий массив с операциями и операндами, в который записано следующее выражение: 5*2+10. Переведем это выражение в тот вид, который «скушает» алгоритм обратной польской нотации. Для этого нам понадобится стек операций и массив выхода. Далее важно определить приоритет операций. Это необходимо для правильного распределения порядка математических действий, чтобы, например, отдавать предпочтение умножению перед сложением.
Высокий приоритет (1): здесь, следуя законам математики, разместим умножение и деление.
Низкий приоритет (2): сюда попадают сложение и вычитание.
После того, как мы определились с приоритетами, перейдем к самому строительству. Перед тем как начать, я должен кое-что пояснить:
все числа являются операндами. Они всегда записываются в массив выхода. Знаки сложения, вычитания и так далее — являются операциями. Но они могут находиться как в стеке операций, так и в массиве выхода. Куда они отправятся — зависит от того, что находится последним в стеке. Идем по порядку, слева направо:
Читаем «5».
Операнд, кладем в массив выхода.
Добавляем 5 в массив выхода.
Массив выхода: 5.
Стек операций: пусто.
Читаем "*".
Операция. В стеке операций нет ничего, поэтому мы кладем его в стек операций
Добавляем * в стек операций.
Массив выхода: 5.
Стек операций: *.
Читаем «2».
Операнд, кладем в массив выхода.
Добавляем 2 в массив выхода.
Массив выхода: 5, 2.
Стек операций: *.
Читаем "+".
Операция. Последний символ в стеке операций (*) имеет приоритет выше, чем текущий знак (+). Поэтому последний знак из стека операций мы перемещаем в массив выхода.
Перемещаем * в стек выхода. Добавляем + в стек операций.
Массив выхода: 5, 2, *.
Стек операций: +.
Читаем «10».
Операнд, кладем в массив выхода.
Добавляем 2 в массив выхода.
Массив выхода: 5, 2, *, 10.
Стек операций: +.
Так как все символы у нас закончились, мы просто выталкиваем всё из стека операций в массив выхода.
Массив выхода: 5, 2, *, 10, +.
Теперь уже можно решать полученную строку согласно алгоритму обратной польской нотации (слева-направо):
В результате мы имеем решение поставленной задачи:
Всей картины этот пример не демонстрирует. Попробуем более сложное выражение:
Читаем "(".
Не смотря на то, что алгоритм ОПН считается бесскобочным, мы все равно считаем скобку за операцию. Так как это открывающая скобка, мы просто добавляем ее в стек.
Добавляем ( в стек операций.
Массив выхода: пусто.
Стек операций: (.
Читаем «6»
Добавляем в массив выхода.
Массив выхода: 6.
Стек операций: (.
Читаем "+"
Добавляем в стек операций.
Массив выхода: 6.
Стек операций: (, +.
Читаем «10»
Добавляем в массив выхода.
Массив выхода: 6, 10.
Стек операций: (, +.
Читаем "-"
Так как текущий знак (-) имеет равный приоритет перед последним знаком в стеке (+) мы всё равно выталкиваем знак из стека в операций в массив выхода, а текущий добавляем в стек.
Массив выхода: 6, 10, +.
Стек операций: (, -.
Читаем «4»
Добавляем в массив выхода.
Массив выхода: 6, 10, +, 4.
Стек операций: (, -.
Читаем ")"
Снова скобка, но теперь уже закрывающая. Здесь необходимо вытолкать все знаки из стека в массив до первой открывающей скобки. От обеих скобок нам попросту нужно избавиться.
Выталкиваем "-" в массив операций. Избавляемся от скобок.
Массив выхода: 6,10, +, 4, -.
Стек операций: пусто.
Читаем "/"
Добавляем в стек.
Массив выхода: 6,10, +, 4, -.
Стек операций: /.
Читаем "("
Добавляем в стек.
Массив выхода: 6,10, +, 4, -.
Стек операций: /, (.
Читаем «1»
Добавляем в массив.
Массив выхода: 6,10, +, 4, -, 1.
Стек операций: /, (.
Читаем "+"
Добавляем в стек.
Массив выхода: 6,10, +, 4, -, 1.
Стек операций: /, (, +.
Читаем «1»
Добавляем в массив.
Массив выхода: 6,10, +, 4, -, 1, 1.
Стек операций: /, (, +.
Читаем "*"
Последний символ в стеке операций (+) имеет приоритет ниже, чем текущий знак (*). Поэтому последний знак из стека мы не трогаем, а просто добавляем как обычно текущий в стек.
Добавляем в стек.
Массив выхода: 6,10, +, 4, -, 1, 1.
Стек операций: /, (, +,*.
Читаем «2»
Добавляем в массив.
Массив выхода: 6,10, +, 4, -, 1, 1, 2.
Стек операций: /, (, +,*.
Читаем ")"
Снова закрывающая скобка, делаем все как в прошлый раз.
Выталкиваем * и + в массив операций. Избавляемся от скобок.
Массив выхода: 6,10, +, 4, -, 1, 1, 2, *, +.
Стек операций: /.
Читаем "+"
У знака деления приоритет выше. Выталкиваем / в массив. Добавляем + в стек.
Массив выхода: 6,10, +, 4, -, 1, 1, 2, *, +, /.
Стек операций: +.
Читаем «1»
Добавляем в массив.
Массив выхода: 6,10, +, 4, -, 1, 1, 2, *, +, /, 1.
Стек операций: +.
Выражение закончено. Снова выталкиваем всё из стека операций в массив выхода.
Массив выхода: 6,10, +, 4, -, 1, 1, 2, *, +, /, 1, +.
Вывод: если текущий знак является операцией, а последний знак из стека операций имеет приоритет ниже или равный, то последний знак из стека уходит в массив выхода, а текущий добавляется в стек. В ином случае все добавляется как обычно. Проще говоря: операции — это кандидаты на добавление в массив выхода, но чтобы им туда попасть, нужен знак с меньшим, или с таким же приоритетом на входе.
Таким образом, я могу доверять этому алгоритму построения стека. Следует заметить, что я явно не использовал знаки приоритета еще выше, такие как возведение в квадрат или вычисление корня. С этим, думаю, сложностей не возникнет, так как алгоритм не изменится.
Тему, затрагивающую плюсы и минусы алгоритма ОПН, а так же его оптимизации я затрагивать не стану. Здесь я старался объяснить все буквально для тех, кто так же как я ищет решение этого вопроса.
Как правило арифметические выражения удобно преобразовывать в обратную польскую запись (ОПЗ), чтобы избавиться от скобок, содержащихся в выражении. Выражения, преобразованные в ОПЗ, можно вычислять последовательно, слева направо.
Существует два наиболее известных способа преобразования в ОПЗ. Рассмотрим коротко каждый из них:
1. Преобразование выражения в ОПЗ с использованием стека
Нам понадобится стек для переменных типа char, т.к. исходное выражение мы получаем в виде строки.
Рассматриваем поочередно каждый символ:
1. Если этот символ – число (или переменная), то просто помещаем его в выходную строку.
2. Если символ – знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3). Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка.
Получив один из этих символов, мы должны проверить стек:
3. Если текущий символ – открывающая скобка, то помещаем ее в стек.
4. Если текущий символ – закрывающая скобка, то извлекаем символы из стека в выходную строку до тех пор, пока не встретим в стеке открывающую скобку (т.е. символ с приоритетом, равным 1), которую следует просто уничтожить. Закрывающая скобка также уничтожается.
Если вся входная строка разобрана, а в стеке еще остаются знаки операций, извлекаем их из стека в выходную строку.
Рассмотрим алгоритм на примере простейшего выражения:
Дано выражение:
a + ( b – c ) * d
Рассмотрим поочередно все символы:
| Символ | Действие | Состояние выходной строки после совершенного действия | Состояние стека после совершенного действия |
| a | ‘a’ – переменная. Помещаем ее в выходную строку | a | пуст |
| + | ‘+’ – знак операции. Помещаем его в стек (поскольку стек пуст, приоритеты можно не проверять) | a | + |
| ( | ‘(‘ – открывающая скобка. Помещаем в стек. | a | + ( |
| b | ‘b’ – переменная. Помещаем ее в выходную строку | a b | + ( |
| – | ‘-‘ – знак операции, который имеет приоритет 2. Проверяем стек: на вершине находится символ ‘(‘, приоритет которого равен 1. Следовательно мы должны просто поместить текущий символ ‘-‘ в стек. | a b | + ( – |
| c | ‘c’ – переменная. Помещаем ее в выходную строку | a b c | + ( – |
| ) | ‘)’ – закрывающая скобка. Извлекаем из стека в выходную строку все символы, пока не встретим открывающую скобку. Затем уничтожаем обе скобки. | a b c – | + |
| * | ‘*’ – знак операции, который имеет приоритет 3. Проверяем стек: на вершине находится символ ‘+’, приоритет которого равен 2, т.е. меньший, чем приоритет текущего символа ‘*’. Следовательно мы должны просто поместить текущий символ ‘*’ в стек. | a b c – | + * |
| d | ‘d’ – переменная. Помещаем ее в выходную строку | a b c – d | + * |
Теперь вся входная строка разобрана, но в стеке еще остаются знаки операций, которые мы должны просто извлечь в выходную строку. Поскольку стек – это структура, организованная по принципу LIFO, сначала извлекается символ ‘*’, затем символ ‘+’.
Итак, мы получили конечный результат:
a b c – d * +
Реализацию алгоритма можно скачать здесь.
Этот алгоритм также используется в программе Calc3, которая находится здесь (см. файл CPPNCalc.cpp).
2. Преобразование выражения в ОПЗ с помощью рекурсивного спуска
Реализация данного алгоритма представляет собой несколько функций, последовательно вызывающих друг друга.
Началом обработки выражения становится вызов функции begin(), которая обрабатывает сложение и вычитание (т.е. сохраняет их во временной переменной и помещает в выходную строку, когда к ней вернется управление после вызова функции mult_div()).
Функция begin() вызывает функцию mult_div(), обрабатывающую знаки деления и умножения (т.е. сохраняет их во временной переменной и помещает в выходную строку, когда к ней вернется управление после вызова функции symbol())..
Далее функция mult_div() вызывает функцию symbol(), обрабатывающую переменные (или числа) и скобки.
Если функция symbol() получает открывающую скобку, она вызывает функцию begin() (т.е. все начинается сначала) и ожидает закрывающей скобки, когда управление вновь возвращается к ней. Если она не дожидаестя закрывающей скобки, это означает, что в выражении содержится синтаксическая ошибка.
Если функция symbol() получает переменную, то помещает ее в выходную строку.
Рассмотрим работу этих функций на примере исходного выражения:
a + ( b – c ) * d
Передачу управления от одной функции к другой (т.е. вызов функции или возвращение управления вызвавшей функции) обозначим знаком –>
- Текущим символом является ‘a’. Преобразование начинается с вызова функции begin(). Далее получаем цепочку вызовов begin() –> mult_div() –> symbol(). Функция symbol() помещает символ ‘a’ в выходную строку, заменяет текущий символ на ‘+’ и возвращает управление. Состояние выходной строки: a
- Текущим символом является ‘+’. symbol() –> mult_div() –> begin(). Функция begin() запоминает текущий символ во временной переменной и заменяет его на ‘(‘. Состояние выходной строки: a
- Текущим символом является ‘(‘. begin() –> mult_div() –> symbol(). Функция symbol() заменяет текущий символ на ‘b’ и вызывает функцию begin(). Состояние выходной строки: a
- Текущим символом является ‘b’. symbol()–> begin() –> mult_div() –> symbol(). Функция symbol() помещает символ ‘b’ в выходную строку, заменяет текущий символ на ‘-‘ и возвращает управление. Состояние выходной строки: a b
- Текущим символом является ‘-‘. symbol() –> mult_div() –> begin(). Функция begin() запоминает текущий символ во временной переменной (поскольку эта переменная – локальная, это, конечно, не означает потерю символа ‘+’, сохраненного ранее) и заменяет текущий символ на ‘c’. Состояние выходной строки: a b
- Текущим символом является ‘с’. begin() –> mult_div() –> symbol(). Функция symbol() помещает символ ‘с’ в выходную строку, заменяет текущий символ на ‘)’ и возвращает управление. Состояние выходной строки: a b c
- Текущим символом является ‘)’. Поскольку закрывающую скобку ни одна функция не обрабатывает, функции поочередно возвращают управление, пока оно не возвратится к функции symbol(), которая обрабатывала открывающую скобку, т.е. цепочка будет такой: symbol() –> mult_div() –> begin(). (здесь функция begin() помещает сохраненный символ ‘-‘ в выходную строку) begin() –> symbol(). Далее функция symbol() заменяет текущий символ на ‘*’ Состояние выходной строки: a b c –
- Текущим символом является ‘*’. symbol() –> mult_div() Функция mult_div() запоминает текущий символ во временной переменной и заменяет его на ‘d’ Состояние выходной строки: a b c –
- Текущим символом является ‘d’. mult_div() –> symbol(). Функция symbol() помещает символ ‘d’ в выходную строку и возвращает управление. Состояние выходной строки: a b c – d
- Строка разобрана. Возвращение управления: symbol() –> mult_div() (здесь функция mult_div() помещает сохраненный символ ‘*’ в выходную строку). Далее: mult_div() –> begin() (здесь функция begin() помещает сохраненный символ ‘+’ в выходную строку) Состояние выходной строки: a b c – d * +
Реализация на С++ (для работы со строками и исключениями используются классы библиотеки VCL):
3. Алгоритм вычисления выражения, записанного в ОПЗ
Для реализации этого алгоритма используется стек для чисел (или для переменных, если они встречаются в исходном выражении). Алгоритм очень прост. В качестве входной строки мы теперь рассматриваем выражение, записанное в ОПЗ:
1. Если очередной символ входной строки – число, то кладем его в стек.
2. Если очередной символ – знак операции, то извлекаем из стека два верхних числа, используем их в качестве операндов для этой операции, затем кладем результат обратно в стек.
Когда вся входная строка будет разобрана в стеке должно остаться одно число, которое и будет результатом данного выражения.
Рассмотрим этот алгоритм на примере выражения:
7 5 2 – 4 * +
