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

С помощью данного сервиса можно онлайн получить обратную польскую запись.

Инструкция

Для арифметических выражений

Все математические операции выражаются через общепринятые символы (+ , - , * , / , ^ ).

Для логических выражений

! Отрицание (НЕ)
| Штрих Шеффера (И-НЕ)
# Стрелка Пирса (ИЛИ-НЕ)
* Конъюнкция (И)
+ Дизъюнкция (ИЛИ)
^ Исключающее ИЛИ, сумма по модулю 2 (XOR)
@ Импликация (ЕСЛИ-ТО)
% Обратная импликация
= Эквивалентность (РАВНО)

Если в качестве исходных данных задана уже готовая обратная польская запись, то необходимо отметить этот пункт. В этом случае все символы разделяются пробелом. Например, x y z ! * x + z * +

Алгоритм разбора выражений

Предварительная обработка символьной строки (проверка на наличие ошибок, сокращение выражения).
Пока есть ещё символы для чтения:
- Читаем очередной символ.
- Если символ является числом или постфиксной функцией (например, ! — факториал), добавляем его к выходной строке.
- Если символ является префиксной функцией (например, sin — синус), помещаем его в стек.
- Если символ является открывающей скобкой, помещаем его в стек.
- Если символ является закрывающей скобкой:
  - До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется.
  - Если существуют разные виды скобок, появление непарной скобки также свидетельствует об ошибке. Если какие-то скобки одновременно являются функциями (например, [x] — целая часть), добавляем к выходной строке символ этой функции.
- Если символ является бинарной операцией о1, тогда:
  1. пока на вершине стека префиксная функция…
    - ИЛИ операция на вершине стека приоритетнее o1;
    - ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1;
    - выталкиваем верхний элемент стека в выходную строку.
  2. помещаем операцию 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 sqrt 1 2 / x 2 ^ 2 - sin * -

Пример разбора логического выражения

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

Присоединяем стек в обратном порядке к выходной строке: x y z ! * x + z * +

Список литературы