Преобразование скобочных выражений в обратную польскую запись

Существует несколько методов получения обратной польской записи. Один из наиболее эффективных методов предложен в 1960 г. голландским ученым Дикстрой. Его метод основан на использовании стека с приоритетами, позволяющего изменить порядок следования знаков операций в выражении так, что получается обратная польская запись. Простейший вариант этого метода применим только к простым арифметическим и логическим выражениям, содержащим переменные, знаки арифметических и логических операций, знаки операций отношения и круглые скобки.

Каждому символу, входящему в выражение, присваивается приоритет (таблица ниже). Для знаков операций приоритеты возрастают в порядке, обратном старшинству операций. Скобки имеют низший приоритет.

Арифметическое или логическое выражение рассматривается как входная строка символов. Входная строка просматривается слева направо. Операнды переписываются в выходную строку, а знаки операций помещаются сначала в стек операций.

Если приоритет входного знака равен нулю или больше приоритета знака, находящегося в вершине стека, то новый знак добавляется к вершине стека. В противном случае из стека «выталкивается» и переписывается в выходную строку знак, находящийся в вершине, а также следующие за ним знаки с приоритетами, большими или равными приоритету входного знака. После этого входной знак добавляется к вершине стека. Особенности имеет лишь обработка скобок. Открывающая круглая скобка, имеющая приоритет нуль, просто записывается в вершину стека и не выталкивает ни одного знака. В то же время ее не может вытолкнуть ни один знак, кроме закрывающей скобки. Закрывающая скобка имеет приоритет 1, не превосходящий приоритета любой операции. Поэтому появление закрывающей скобки вызывает выталкивание всех знаков до ближайшей открывающей скобки включительно. В стек закрывающая скобка не записывается. Открывающая и закрывающая скобки как бы взаимно уничтожаются и в выходную строку не переносятся. После просмотра всех символов входной строки происходит выталкивание всех оставшихся в стеке символов и дописывание их к выходной строке.

Ниже приведены два примера преобразования инфиксных выражений в обратные польские.

Пример 1.

Пример 2.

Преобразование инфиксного выражения в префиксную запись осуществляется сканированием инфиксного выражения справа налево.

Лекция 7

План лекции:

1. Нелинейные структуры. Деревья.

2. Обходы дерева.

Не нашли, что искали? Воспользуйтесь поиском: