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

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

Инструкция

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

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

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

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

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

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

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

sqrt(x)-1/2*sin(x^2-2)
СимволОперацияСтекВыходная строка
sдобавить к выходной строке sqrt
(поместить в стек(sqrt
xдобавить к выходной строке(sqrt, x
)1) присоединить содержимое стека до скобки в обратном порядке к выходной строке; 2) удалить скобку из стека.sqrt, x
-поместить в стек-sqrt, x
1добавить к выходной строке-sqrt, x, 1
/поместить в стек-, /sqrt, x, 1
2добавить к выходной строке-, /sqrt, x, 1, 2
*1) присоединить стек в обратном порядке к выходной строке; 2) поместить новую операцию в стек.-, *sqrt, x, 1, 2, /
sдобавить к выходной строке-, *sqrt, x, 1, 2, /, sin
(поместить в стек-, *, (sqrt, x, 1, 2, /, sin
xдобавить к выходной строке-, *, (sqrt, x, 1, 2, /, sin, x
^поместить в стек-, *, (, ^sqrt, x, 1, 2, /, sin, x
2добавить к выходной строке-, *, (, ^sqrt, x, 1, 2, /, sin, x, 2
-1) присоединить стек в обратном порядке к выходной строке; 2) поместить новую операцию в стек.-, *, (, -sqrt, x, 1, 2, /, sin, x, 2, ^
2добавить к выходной строке-, *, (, -sqrt, x, 1, 2, /, sin, x, 2, ^, 2
)1) присоединить содержимое стека до скобки в обратном порядке к выходной строке; 2) удалить скобку из стека.-, *sqrt, x, 1, 2, /, sin, x, 2, ^, 2, -
Присоединяем стек в обратном порядке к выходной строке: sqrtx12/sinx2^2-*-

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

СимволОперацияСтекВыходная строка
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
Присоединяем стек в обратном порядке к выходной строке: xyz!*x+z*+

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

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