Реализация алгоритма обратной польской записи
Обратная польская запись (ОПЗ), или постфиксная запись, представляет собой способ математической записи выражений, при котором операторы следуют за операндами. Это обеспечивает однозначность вычислений и удобство для обработки с помощью стековых структур. Алгоритм преобразования выражения из инфиксной формы в постфиксную популярен при реализации калькуляторов, компиляторов, а также при преподавании основ структур данных. Данная статья подробно рассмотрит реализацию алгоритма обратной польской записи, её правила, практическое применение и примеры кода на языке программирования Python.
История и преимущества обратной польской записи
Обратная польская запись была предложена польским математиком Янушем Лукасевичем в первой половине XX века. Его цель состояла в оптимизации записи формул для вычислительных машин, чтобы избежать лишних скобок и обеспечить быстреее и более надёжное вычисление выражений. ОПЗ активно применяется до сих пор благодаря простоте парсинга и эффективности исполнения.
Главное достоинство обратной польской записи — отсутствие необходимости в расставлении скобок при выражении приоритетов операций. Любое выражение, записанное в ОПЗ, может быть однозначно и быстро вычислено с помощью структуры данных «стек». Таким образом, реализовать парсер или вычислитель одобной записи значительно проще, чем анализировать инфиксные выражения с классической расстановкой скобок.
Основные правила преобразования выражений
Для преобразования выражения из инфиксной (обычной) формы в обратную польскую запись необходимо придерживаться определённых правил. Такое преобразование требует учёта приоритетов операций, правильного распределения скобок и порядка обхода выражения. Для этого используется специальный алгоритм, базирующийся на использовании стека.
Главные правила преобразования:
- Если токен является числом или переменной, он сразу добавляется в выходную последовательность.
- Если токен — оператор, он помещается в стек согласно его приоритету. Операторы с меньшим приоритетом в стеке вытесняются операторами с более высоким.
- Открывающая скобка всегда помещается в стек и служит разграничителем, а при встрече закрывающей скобки из стека извлекаются все операторы до соответствующей открывающей скобки.
Порядок обхода выражения слева направо позволяет соблюдать все математические правила вычислений. После прочтения всего исходного выражения все элементы, оставшиеся в стеке, последовательно добавляются в результат.
Структуры данных для реализации алгоритма
Ключевым элементом алгоритма преобразования в обратную польскую запись является стек. Стек позволяет хранить операторы и скобки, извлекая их в нужном порядке при формировании результата. Стандартная реализация стека возможна как с помощью динамического массива (списка) в большинстве современных языков программирования, так и с использованием специализированных классов.
Список входных данных разбивается на токены — числа, переменные, операторы и скобки. Для каждого токена выбирается действие в зависимости от его типа, используя стек и список вывода — результат обратной польской записи. После завершения обработки входных данных оставшиеся операторы из стека переносятся в результат.
| Тип токена | Действие |
|---|---|
| Число/переменная | Добавить в выходную последовательность |
| Оператор | Извлекать из стека операторы с более высоким/равным приоритетом, затем добавить в стек |
| ( | Добавить в стек |
| ) | Извлекать из стека до первой ( незамкнутой скобки, переносить операторы в результат |
Таким образом, для работы алгоритма требуются всего две структуры: стек для временного хранения операторов и список (или строка) для хранения результата.
Порядок работы алгоритма шунтирования (Дейкстры)
Наиболее известный алгоритм получения обратной польской записи — алгоритм шунтирования, предложенный Эдсгером Дейкстрой. Он предполагает последовательный разбор выражения и разумное управление стеком операторов. Последовательность действий является строгой и воспроизводимой, благодаря чему возможна реализация даже в языках низкого уровня.
Пошаговый порядок работы алгоритма:
- Разделить исходное выражение на отдельные токены — числа, переменные, операторы, скобки.
- Обойти все токены слева направо, для каждого применяя соответствующее действие (см. таблицу выше).
- После обработки всех токенов выгрузить оставшиеся операторы из стека в выходную последовательность.
Особое внимание уделяется приоритетам операторов. Перед помещением оператора в стек сравнивается его приоритет с вершиной стека; приоритеты реализуются в виде словаря, где каждому оператору сопоставляется числовое значение. Скобки разрушают последовательность, временно обнуляя приоритет операторов внутри них.
Пример кода на Python
Для большей наглядности рассмотрим реализацию преобразования инфиксного выражения в обратную польскую запись на языке Python. Исходное выражение предполагается в виде строки, а резльтат возвращается как список токенов.
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
stack = []
output = []
tokens = expression.split()
for token in tokens:
if token.isnumeric() or token.isalpha():
output.append(token)
elif token in precedence:
while (stack and stack[-1] != '(' and
precedence.get(stack[-1], 0) >= precedence[token]):
output.append(stack.pop())
stack.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop() # Удаляем '('
while stack:
output.append(stack.pop())
return output
expr = "3 + 4 * 2 / ( 1 - 5 ) ^ 2"
print(' '.join(infix_to_postfix(expr)))
В данном коде реализовано поэтапное чтение токенов, учёт приоритетов, обработка скобок, а также вывод результирующей последовательности. Такой подход легко модифицировать для поддержки переменных, дополнительных операторов и функций.
Особые случаи и расширения
Реализация алгоритма обратной польской записи может быть усложнена поддержкой унарных операторов, функций (например, sin, cos, log), многозначных констант, а также произвольных именованных переменных. Для этого на этапе разбиения строки на токены («лексического анализа») следует уделить внимание идентификации таких случаев.
Расширенный алгоритм учитывает разный приоритет унарных операторов, различие между функцией и переменной, а также допускает многоуровневую вложенность скобок. В некоторых языках (например, в C или JavaScript) достаточно осторожно подходить к разбору смешанных арифметических и логических выражений, разбирая каждый оператор согласно спецификациям языка.
Практическое применение
Алгоритм преобразования выражения в обратную польскую запись широко применяется при создании калькуляторов, компиляторов и интерпретаторов языков программирования. В системах автоматизации вычислений такой подход позволяет значительно упростить дальнейшую обработку выражений — для вычисления результата постфиксной записи также используется стек, что обеспечивает простоту и скорость алгоритмов.
Благодаря своей эффективности и наглядности алгоритм шунтирования входит в стандартный курс дисциплин по анализу структур данных, применению стеков, разработке парсеров и компиляторов, а также численных вычислений. Он формирует базовые навыки эффективной работы с последовательностями операций и их приоритетами.
Заключение
Реализация алгоритма обратной польской записи — мощный инструмент инженера-программиста. В работе калькуляторов, трансляторов и программ по обработке формул этот алгоритм доказал свою надёжность и практичность. Использование стеков для промежуточного хранения операторов и унификация правил преобразования выражения делают его универсальным решением для задач парсинга и вычисления.
В статье были рассмотрены основные принципы построения обратной польской записи, а также реализован пример для практического применения. Освоив этот алгоритм, вы сможете быстро и надёжно решать широкий спектр задач, связанных с анализом и вычислением выражений любой сложности.