Будучи дилетантом в области разработки приложений, я испытал сложности с пониманием алгоритма работы обратной польской нотации, а если быть точнее — алгоритма подготовки стека. Делу так же мало помогли статьи в «интернетах».
Все началось с того, что я затеял создание несложного интерпретатора для собственного проекта. Для решения сложных выражений на выбор было два алгоритма: рекурсивный спуск и обратная польская запись. Очевидная простота и подход к решению задачи (а может и само название) позволили последнему стать предметом для изучения.
Делу помогли две статьи. Одна из них на википедии, а вторая была написана замечательным пользователем хабра, GORKOFF, который объяснил все буквально «на пальцах».
Однако до конца я так и не понял тот важный вопрос: как же построить стек?
Не буду больше ходить вокруг да около, начнем по порядку. Представим, что у нас имеется некий массив с операциями и операндами, в который записано следующее выражение: 5*2+10. Переведем это выражение в тот вид, который «скушает» алгоритм обратной польской нотации. Для этого нам понадобится стек операций и массив выхода. Далее важно определить приоритет операций. Это необходимо для правильного распределения порядка математических действий, чтобы, например, отдавать предпочтение умножению перед сложением.
Высокий приоритет (1): здесь, следуя законам математики, разместим умножение и деление.
Низкий приоритет (2): сюда попадают сложение и вычитание.
После того, как мы определились с приоритетами, перейдем к самому строительству. Перед тем как начать, я должен кое-что пояснить:
все числа являются операндами. Они всегда записываются в массив выхода. Знаки сложения, вычитания и так далее — являются операциями. Но они могут находиться как в стеке операций, так и в массиве выхода. Куда они отправятся — зависит от того, что находится последним в стеке. Идем по порядку, слева направо:
Читаем «5».
Операнд, кладем в массив выхода.
Добавляем 5 в массив выхода.
Массив выхода: 5.
Стек операций: пусто.
Читаем "*".
Операция. В стеке операций нет ничего, поэтому мы кладем его в стек операций
Добавляем * в стек операций.
Массив выхода: 5.
Стек операций: *.
Читаем «2».
Операнд, кладем в массив выхода.
Добавляем 2 в массив выхода.
Массив выхода: 5, 2.
Стек операций: *.
Читаем "+".
Операция. Последний символ в стеке операций (*) имеет приоритет выше, чем текущий знак (+). Поэтому последний знак из стека операций мы перемещаем в массив выхода.
Перемещаем * в стек выхода. Добавляем + в стек операций.
Массив выхода: 5, 2, *.
Стек операций: +.
Читаем «10».
Операнд, кладем в массив выхода.
Добавляем 2 в массив выхода.
Массив выхода: 5, 2, *, 10.
Стек операций: +.
Так как все символы у нас закончились, мы просто выталкиваем всё из стека операций в массив выхода.
Массив выхода: 5, 2, *, 10, +.
Теперь уже можно решать полученную строку согласно алгоритму обратной польской нотации (слева-направо):
В результате мы имеем решение поставленной задачи:
5*2+10=20
Всей картины этот пример не демонстрирует. Попробуем более сложное выражение:
(6+10-4)/(1+1*2)+1
Читаем "(".
Не смотря на то, что алгоритм ОПН считается бесскобочным, мы все равно считаем скобку за операцию. Так как это открывающая скобка, мы просто добавляем ее в стек.
Добавляем ( в стек операций.
Массив выхода: пусто.
Стек операций: (.
Читаем «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, +.
Снова считаем.
Итог: (6+10-4)/(1+1*2)+1=5
Вывод: если текущий знак является операцией, а последний знак из стека операций имеет приоритет ниже или равный, то последний знак из стека уходит в массив выхода, а текущий добавляется в стек. В ином случае все добавляется как обычно. Проще говоря: операции — это кандидаты на добавление в массив выхода, но чтобы им туда попасть, нужен знак с меньшим, или с таким же приоритетом на входе.
Таким образом, я могу доверять этому алгоритму построения стека. Следует заметить, что я явно не использовал знаки приоритета еще выше, такие как возведение в квадрат или вычисление корня. С этим, думаю, сложностей не возникнет, так как алгоритм не изменится.
Тему, затрагивающую плюсы и минусы алгоритма ОПН, а так же его оптимизации я затрагивать не стану. Здесь я старался объяснить все буквально для тех, кто так же как я ищет решение этого вопроса.
Все началось с того, что я затеял создание несложного интерпретатора для собственного проекта. Для решения сложных выражений на выбор было два алгоритма: рекурсивный спуск и обратная польская запись. Очевидная простота и подход к решению задачи (а может и само название) позволили последнему стать предметом для изучения.
Делу помогли две статьи. Одна из них на википедии, а вторая была написана замечательным пользователем хабра, GORKOFF, который объяснил все буквально «на пальцах».
Однако до конца я так и не понял тот важный вопрос: как же построить стек?
Не буду больше ходить вокруг да около, начнем по порядку. Представим, что у нас имеется некий массив с операциями и операндами, в который записано следующее выражение: 5*2+10. Переведем это выражение в тот вид, который «скушает» алгоритм обратной польской нотации. Для этого нам понадобится стек операций и массив выхода. Далее важно определить приоритет операций. Это необходимо для правильного распределения порядка математических действий, чтобы, например, отдавать предпочтение умножению перед сложением.
Высокий приоритет (1): здесь, следуя законам математики, разместим умножение и деление.
Низкий приоритет (2): сюда попадают сложение и вычитание.
После того, как мы определились с приоритетами, перейдем к самому строительству. Перед тем как начать, я должен кое-что пояснить:
все числа являются операндами. Они всегда записываются в массив выхода. Знаки сложения, вычитания и так далее — являются операциями. Но они могут находиться как в стеке операций, так и в массиве выхода. Куда они отправятся — зависит от того, что находится последним в стеке. Идем по порядку, слева направо:
Читаем «5».
Операнд, кладем в массив выхода.
Добавляем 5 в массив выхода.
Массив выхода: 5.
Стек операций: пусто.
Читаем "*".
Операция. В стеке операций нет ничего, поэтому мы кладем его в стек операций
Добавляем * в стек операций.
Массив выхода: 5.
Стек операций: *.
Читаем «2».
Операнд, кладем в массив выхода.
Добавляем 2 в массив выхода.
Массив выхода: 5, 2.
Стек операций: *.
Читаем "+".
Операция. Последний символ в стеке операций (*) имеет приоритет выше, чем текущий знак (+). Поэтому последний знак из стека операций мы перемещаем в массив выхода.
Перемещаем * в стек выхода. Добавляем + в стек операций.
Массив выхода: 5, 2, *.
Стек операций: +.
Читаем «10».
Операнд, кладем в массив выхода.
Добавляем 2 в массив выхода.
Массив выхода: 5, 2, *, 10.
Стек операций: +.
Так как все символы у нас закончились, мы просто выталкиваем всё из стека операций в массив выхода.
Массив выхода: 5, 2, *, 10, +.
Теперь уже можно решать полученную строку согласно алгоритму обратной польской нотации (слева-направо):
Решение
1) {5, 2, *, 10, +} {Пусто}
2) {2, *, 10, +} {5}
3) { *, 10, +} {5, 2}
4) {10, +} {10}
5) {+} {10, 10}
6) {} {20}
2) {2, *, 10, +} {5}
3) { *, 10, +} {5, 2}
4) {10, +} {10}
5) {+} {10, 10}
6) {} {20}
В результате мы имеем решение поставленной задачи:
5*2+10=20
Всей картины этот пример не демонстрирует. Попробуем более сложное выражение:
(6+10-4)/(1+1*2)+1
Читаем "(".
Не смотря на то, что алгоритм ОПН считается бесскобочным, мы все равно считаем скобку за операцию. Так как это открывающая скобка, мы просто добавляем ее в стек.
Добавляем ( в стек операций.
Массив выхода: пусто.
Стек операций: (.
Читаем «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) {6,10, +, 4, -, 1, 1, 2, *, +, /, 1, +} {Пусто}
2) {10, +, 4, -, 1, 1, 2, *, +, /, 1, +} {6}
3) {+, 4, -, 1, 1, 2, *, +, /, 1, +} {6,10}
4) {4, -, 1, 1, 2, *, +, /, 1, +} {16}
5) {-, 1, 1, 2, *, +, /, 1, +} {16,4}
6) {1, 1, 2, *, +, /, 1, +} {12}
7) {1, 2, *, +, /, 1, +} {12, 1}
8) {2, *, +, /, 1, +} {12, 1, 1}
9) {*, +, /, 1, +} {12, 1, 1, 2}
10) {+, /, 1, +} {12, 1, 2}
11) {/, 1, +} {12, 3}
12) {1, +} {4}
13) {+} {4, 1}
13) {} {5}
2) {10, +, 4, -, 1, 1, 2, *, +, /, 1, +} {6}
3) {+, 4, -, 1, 1, 2, *, +, /, 1, +} {6,10}
4) {4, -, 1, 1, 2, *, +, /, 1, +} {16}
5) {-, 1, 1, 2, *, +, /, 1, +} {16,4}
6) {1, 1, 2, *, +, /, 1, +} {12}
7) {1, 2, *, +, /, 1, +} {12, 1}
8) {2, *, +, /, 1, +} {12, 1, 1}
9) {*, +, /, 1, +} {12, 1, 1, 2}
10) {+, /, 1, +} {12, 1, 2}
11) {/, 1, +} {12, 3}
12) {1, +} {4}
13) {+} {4, 1}
13) {} {5}
Итог: (6+10-4)/(1+1*2)+1=5
Вывод: если текущий знак является операцией, а последний знак из стека операций имеет приоритет ниже или равный, то последний знак из стека уходит в массив выхода, а текущий добавляется в стек. В ином случае все добавляется как обычно. Проще говоря: операции — это кандидаты на добавление в массив выхода, но чтобы им туда попасть, нужен знак с меньшим, или с таким же приоритетом на входе.
Таким образом, я могу доверять этому алгоритму построения стека. Следует заметить, что я явно не использовал знаки приоритета еще выше, такие как возведение в квадрат или вычисление корня. С этим, думаю, сложностей не возникнет, так как алгоритм не изменится.
Тему, затрагивающую плюсы и минусы алгоритма ОПН, а так же его оптимизации я затрагивать не стану. Здесь я старался объяснить все буквально для тех, кто так же как я ищет решение этого вопроса.