Обратная польская запись
ом команд, по сравнению с обыет количество действий, которые нужно выполнить для получения результата.
Преобразова стека приоритетнее o1
- … ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1
- … выталкиваем верхний элемент стека в выходную строку;
- 2)перации система смотрит на предыдущий символ и определяет, чем будет минус, бинарной операцией или унарной функцией. Соответственно, в стеке и ОПЗ нужны разные символы для бинарного и унарного минуса.
Сложный пример
- высокий: ^
- средний: * /
- низкий: + −
- самый низкий: ()
Вход: 3 + 4 * 2 / (1 - 5)^2 Читаем «3» Добавим «3» к выходной строке Выход: 3 Читаем «+» Кладём «+» в стек Выход: 3 Стек: + Читаем «4» Добавим «4» к выходной строке Выход: 3 4 Стек: + Читаем «*» Кладём «*» в стек Выход: 3 4 Стек: + * Читаем «2» Добавим «2» к выходной строке Выход: 3 4 2 Стек: + * Читаем «/» Выталкиваем «*» из стека в выходную строку, кладём «/» в стек Выход: 3 4 2 * Стек: + / Читаем «(» Кладём «(» в стек Выход: 3 4 2 * Стек: + / ( Читаем «1» Добавим «1» к выходной строке Выход: 3 4 2 * 1 Стек: + / ( Читаем «−» Кладём «−» в стек Выход: 3 4 2 * 1 Стек: + / ( − Читаем «5» Добавим «5» к выходной строке Выход: 3 4 2 * 1 5 Стек: + / ( - Читаем «)» Выталкиваем «−» из стека в выходную строку, выталкиваем «(» Выход: 3 4 2 * 1 5 − Стек: + / Читаем «^» Кладём «^» в стек Выход: 3 4 2 * 1 5 − Стек: + / ^ Читаем «2» Добавим «2» к выходной строке Выход: 3 4 2 * 1 5 − 2 Стек: + / ^ Конец выражения Выталкиваем все элементы из стека в строку Выход: 3 4 2 * 1 5 − 2 ^ / +
Оптимизация выражений
Если вы пишете интерпретатор, то выходная строка, полученная после преобразования исходного выражения в обратную польскую нотацию, может храниться вместо исходного выражения для последующей интерпретации. Обратная польская нотация также позволяет компьютеру упрощать выражения.
Пример алгоритма упрощения выражения
Рассмотрим алгоритм, который осуществляет предвычисление констант в выражении. Дано выражение в ОПН. Нам понадобится стек для хранения смешанных данных (чисел и операторов).
Алгоритм подобен тому, который применяется для вычисления выражений. Мы просматриваем выражение слева направо.
Пока есть символы для чтения:
- Читаем очередной символ.
- Если символ является числом, помещаем его в стек.
- Если символ является переменной, считая что переменная имеет значение null, помещаем символ в стек.
- Если символ является оператором:
- 1) (если все аргументы оператора, лежащие в стеке, имеют значение, отличное от null) выталкиваем аргументы оператора из стека и помещаем в стек результат операции;
- 2) (если хотя бы один из аргументов имеет значение null) считая что результат операции null, кладём символ оператора в стек.
После того, как всё выражение просмотрено, то, что осталось в стеке, является оптимизированым выражением (операторы выражения лежат в стеке в обратном порядке).
Пример работы алгоритма
Выражение
Инфиксная нотация: exp(-1/2*x)
Обратная Польская нотация: -1 2 / x * exp
Читаем: «-1»
Кладём «-1» в стек
Стек: -1
Читаем: «2»
Кладём «2» в стек
Стек: -1 2
Читаем: «/»
Вычисляем частное, результат кладём в стек
Стек: -0.5
Читаем: «x»
Кладём «x» в стек со значением null
Стек: -0.5 x(null)
Читаем: «*»
Кладём «*» в стек со значением null
Стек: -0.5 x(null) *(null)
Читаем «exp»
Кладём «exp» в стек со значением null
Стек: -0.5 x(null) *(null) exp(null)
Результат оптимизации: -0.5 x * exp
Данный метод, очевидно, не включает всех возможных способов оптимизации.
Примеры реализации
В статье «Обратная польская запись: примеры реализации» собраны примеры реализации обратной польской записи на различных языках программирования.
Практические реализации
В качестве практического применения данной методики можно привести организацию байт-кода конфигураций прикладных решений системы 1С:Предприятие. Официального подтверждения компания 1С не дает, но пользователи данной системы на специализированных форумах приводят доказательства и алгоритмы, позволяющие декомпилировать исходные тексты.
Литература
- Т. Пратт, М. Зелковиц. Языки программирования: разработка и реализация = Terrence W. Pratt, Marvin V. Zelkowitz. Programming Languages: Design and Implementation. — 4-е издание. — Питер, 2002. — 688 с. — (Классика Computer Science). — 4000 экз. — ISBN 5-318-00189-0.
Примечания
См. также
Языки программирования, использующие ОПН в качестве основной:
- Forth
- Factor
- Postscript
- Язык стилей оформления BibTeX