Обратная польская запись java

Обратная польская запись java

Одной из главных п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): сюда попадают сложение и вычитание.

После того, как мы определились с приоритетами, перейдем к самому строительству. Перед тем как начать, я должен кое-что пояснить:
все числа являются операндами. Они всегда записываются в массив выхода. Знаки сложения, вычитания и так далее — являются операциями. Но они могут находиться как в стеке операций, так и в массиве выхода. Куда они отправятся — зависит от того, что находится последним в стеке. Идем по порядку, слева направо:

Читайте также:  Leagoo m8 прошивка без вирусов

Читаем «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() получает переменную, то помещает ее в выходную строку.

Читайте также:  Внутренняя программная ошибка src defaultfontmetrics cpp 55

Рассмотрим работу этих функций на примере исходного выражения:
a + ( b — c ) * d

Передачу управления от одной функции к другой (т.е. вызов функции или возвращение управления вызвавшей функции) обозначим знаком —>

  1. Текущим символом является ‘a’. Преобразование начинается с вызова функции begin(). Далее получаем цепочку вызовов begin() —> mult_div() —> symbol(). Функция symbol() помещает символ ‘a’ в выходную строку, заменяет текущий символ на ‘+’ и возвращает управление. Состояние выходной строки: a
  2. Текущим символом является ‘+’. symbol() —> mult_div() —> begin(). Функция begin() запоминает текущий символ во временной переменной и заменяет его на ‘(‘. Состояние выходной строки: a
  3. Текущим символом является ‘(‘. begin() —> mult_div() —> symbol(). Функция symbol() заменяет текущий символ на ‘b’ и вызывает функцию begin(). Состояние выходной строки: a
  4. Текущим символом является ‘b’. symbol()—> begin() —> mult_div() —> symbol(). Функция symbol() помещает символ ‘b’ в выходную строку, заменяет текущий символ на ‘-‘ и возвращает управление. Состояние выходной строки: a b
  5. Текущим символом является ‘-‘. symbol() —> mult_div() —> begin(). Функция begin() запоминает текущий символ во временной переменной (поскольку эта переменная — локальная, это, конечно, не означает потерю символа ‘+’, сохраненного ранее) и заменяет текущий символ на ‘c’. Состояние выходной строки: a b
  6. Текущим символом является ‘с’. begin() —> mult_div() —> symbol(). Функция symbol() помещает символ ‘с’ в выходную строку, заменяет текущий символ на ‘)’ и возвращает управление. Состояние выходной строки: a b c
  7. Текущим символом является ‘)’. Поскольку закрывающую скобку ни одна функция не обрабатывает, функции поочередно возвращают управление, пока оно не возвратится к функции symbol(), которая обрабатывала открывающую скобку, т.е. цепочка будет такой: symbol() —> mult_div() —> begin(). (здесь функция begin() помещает сохраненный символ ‘-‘ в выходную строку) begin() —> symbol(). Далее функция symbol() заменяет текущий символ на ‘*’ Состояние выходной строки: a b c —
  8. Текущим символом является ‘*’. symbol() —> mult_div() Функция mult_div() запоминает текущий символ во временной переменной и заменяет его на ‘d’ Состояние выходной строки: a b c —
  9. Текущим символом является ‘d’. mult_div() —> symbol(). Функция symbol() помещает символ ‘d’ в выходную строку и возвращает управление. Состояние выходной строки: a b c — d
  10. Строка разобрана. Возвращение управления: symbol() —> mult_div() (здесь функция mult_div() помещает сохраненный символ ‘*’ в выходную строку). Далее: mult_div() —> begin() (здесь функция begin() помещает сохраненный символ ‘+’ в выходную строку) Состояние выходной строки: a b c — d * +

Реализация на С++ (для работы со строками и исключениями используются классы библиотеки VCL):

3. Алгоритм вычисления выражения, записанного в ОПЗ
Для реализации этого алгоритма используется стек для чисел (или для переменных, если они встречаются в исходном выражении). Алгоритм очень прост. В качестве входной строки мы теперь рассматриваем выражение, записанное в ОПЗ:
1. Если очередной символ входной строки — число, то кладем его в стек.
2. Если очередной символ — знак операции, то извлекаем из стека два верхних числа, используем их в качестве операндов для этой операции, затем кладем результат обратно в стек.
Когда вся входная строка будет разобрана в стеке должно остаться одно число, которое и будет результатом данного выражения.

Рассмотрим этот алгоритм на примере выражения:
7 5 2 — 4 * +

Ссылка на основную публикацию
Ноутбук леново не загружается с флешки
Как загрузиться с флешки не заходя в BIOS Производители современных ноутбуков сознательно усложняют защиту BIOS от неосторожных пользователей и стараются...
Неразрывный пробел в ворде как убрать
Напечатать математические уравнения в Ворде или функции не составит особого труда. Только курсор доходит до конца строки и передвигается на...
Нет товаров доступных для отгрузки ут 11
не получается создать на основании документа «Заказ клиента» документ «Реализация товаров и услуг» и выдается ошибка: «Нет товаров доступных для...
Обнаружена незавершенная операция конвертации структуры конфигурации
В свое время столкнулся с проблемой: при обновлении конфигурации из хранилища, произошел сбой, и закрылась 1С. Как выяснилось позднее –...
Adblock detector