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

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

Указана выходная строка

Инструкция

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

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

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

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

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

  1. Предварительная обработка символьной строки (проверка на наличие ошибок, сокращение выражения).
  2. Пока есть ещё символы для чтения:
    • Читаем очередной символ.
    • Если символ является числом или постфиксной функцией (например, ! — факториал), добавляем его к выходной строке.
    • Если символ является префиксной функцией (например, sin — синус), помещаем его в стек.
    • Если символ является открывающей скобкой, помещаем его в стек.
    • Если символ является закрывающей скобкой:
      • До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется.
      • Если существуют разные виды скобок, появление непарной скобки также свидетельствует об ошибке. Если какие-то скобки одновременно являются функциями (например, [x] — целая часть), добавляем к выходной строке символ этой функции.
    • Если символ является бинарной операцией о1, тогда:
      1. пока на вершине стека префиксная функция…
        • ИЛИ операция на вершине стека приоритетнее o1;
        • ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1;
        • выталкиваем верхний элемент стека в выходную строку.
      2. помещаем операцию o1 в стек.
  3. Когда все символы входной строки пере, выталкиваем все символы из стека в выходную строку.
Приоритеты:

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

sqrt(x)-1/2*sin(x^2-2)
СимволОперацияСтекВыходная строка
sqrtпоместить в стекs
(поместить в стекs, (
xдобавить к выходной строкеs, (x
)1) присоединить содержимое стека до скобки в обратном порядке к выходной строке; 2) удалить скобку из стека.sx
-1) присоединить стек в обратном порядке к выходной строке; 2) поместить новую операцию в стек.-x, sqrt
1добавить к выходной строке-x, sqrt, 1
/поместить в стек-, /x, sqrt, 1
2добавить к выходной строке-, /x, sqrt, 1, 2
*1) присоединить стек в обратном порядке к выходной строке; 2) поместить новую операцию в стек.-, *x, sqrt, 1, 2, /
sinпоместить в стек-, *, sx, 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) удалить скобку из стека.-, *, sx, 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 * +

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

  1. Обратная польская запись
  2. Польская инверсная запись (ПолИЗ)
Задать вопрос или оставить комментарий Помощь в решении Поиск