Обратная польская запись
С помощью данного сервиса можно онлайн получить обратную польскую запись.Инструкция
Для арифметических выражений
Все математические операции выражаются через общепринятые символы (+ , - , * , / , ^ ).Для логических выражений
! Отрицание (НЕ)| Штрих Шеффера (И-НЕ)
# Стрелка Пирса (ИЛИ-НЕ)
* Конъюнкция (И)
+ Дизъюнкция (ИЛИ)
^ Исключающее ИЛИ, сумма по модулю 2 (XOR)
@ Импликация (ЕСЛИ-ТО)
% Обратная импликация
= Эквивалентность (РАВНО)
Если в качестве исходных данных задана уже готовая обратная польская запись, то необходимо отметить этот пункт. В этом случае все символы разделяются пробелом.
Например, x y z ! * x + z * +
Алгоритм разбора выражений
- Предварительная обработка символьной строки (проверка на наличие ошибок, сокращение выражения).
- Пока есть ещё символы для чтения:
- Читаем очередной символ.
- Если символ является числом или постфиксной функцией (например, ! — факториал), добавляем его к выходной строке.
- Если символ является префиксной функцией (например, sin — синус), помещаем его в стек.
- Если символ является открывающей скобкой, помещаем его в стек.
- Если символ является закрывающей скобкой:
- До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется.
- Если существуют разные виды скобок, появление непарной скобки также свидетельствует об ошибке. Если какие-то скобки одновременно являются функциями (например, [x] — целая часть), добавляем к выходной строке символ этой функции.
- Если символ является бинарной операцией о1, тогда:
- пока на вершине стека префиксная функция…
- ИЛИ операция на вершине стека приоритетнее o1;
- ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1;
- выталкиваем верхний элемент стека в выходную строку.
- помещаем операцию o1 в стек.
- пока на вершине стека префиксная функция…
- Когда все символы входной строки пере, выталкиваем все символы из стека в выходную строку.
- высокий: ^
- средний: * /
- низкий: + −
- самый низкий: ( )
Пример разбора арифметического выражения
sqrt(x)-1/2*sin(x^2-2)| Символ | Операция | Стек | Выходная строка |
| sqrt | поместить в стек | s | |
| ( | поместить в стек | s, ( | |
| x | добавить к выходной строке | s, ( | x |
| ) | 1) присоединить содержимое стека до скобки в обратном порядке к выходной строке; 2) удалить скобку из стека. | s | x |
| - | 1) присоединить стек в обратном порядке к выходной строке; 2) поместить новую операцию в стек. | - | x, sqrt |
| 1 | добавить к выходной строке | - | x, sqrt, 1 |
| / | поместить в стек | -, / | x, sqrt, 1 |
| 2 | добавить к выходной строке | -, / | x, sqrt, 1, 2 |
| * | 1) присоединить стек в обратном порядке к выходной строке; 2) поместить новую операцию в стек. | -, * | x, sqrt, 1, 2, / |
| sin | поместить в стек | -, *, s | x, sqrt, 1, 2, / |
| ( | поместить в стек | -, *, s, ( | x, sqrt, 1, 2, / |
| x | добавить к выходной строке | -, *, s, ( | x, sqrt, 1, 2, /, x |
| ^ | поместить в стек | -, *, s, (, ^ | x, sqrt, 1, 2, /, x |
| 2 | добавить к выходной строке | -, *, s, (, ^ | x, sqrt, 1, 2, /, x, 2 |
| - | 1) присоединить стек в обратном порядке к выходной строке; 2) поместить новую операцию в стек. | -, *, s, (, - | x, sqrt, 1, 2, /, x, 2, ^ |
| 2 | добавить к выходной строке | -, *, s, (, - | x, sqrt, 1, 2, /, x, 2, ^, 2 |
| ) | 1) присоединить содержимое стека до скобки в обратном порядке к выходной строке; 2) удалить скобку из стека. | -, *, s | x, sqrt, 1, 2, /, x, 2, ^, 2, - |
Пример разбора логического выражения
x+(y*!z+x)*z| Символ | Операция | Стек | Выходная строка |
| x | добавить к выходной строке | x | |
| + | поместить в стек | + | x |
| ( | поместить в стек | +, ( | x |
| y | добавить к выходной строке | +, ( | x, y |
| * | поместить в стек | +, (, * | x, y |
| ! | поместить в стек | +, (, *, ! | x, y |
| z | добавить к выходной строке | +, (, *, ! | x, y, z |
| + | 1) присоединить стек в обратном порядке к выходной строке; 2) поместить новую операцию в стек. | +, (, + | x, y, z, !, * |
| x | добавить к выходной строке | +, (, + | x, y, z, !, *, x |
| ) | 1) присоединить содержимое стека до скобки в обратном порядке к выходной строке; 2) удалить скобку из стека. | + | x, y, z, !, *, x, + |
| * | поместить в стек | +, * | x, y, z, !, *, x, + |
| z | добавить к выходной строке | +, * | x, y, z, !, *, x, +, z |