Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 78 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
ся там знаки операций до ближайшей открывающей скобки, которая также
удаляется из стека. Все эти знаки в порядке их извлечения помещаются в
строку-результат. Когда же встречается знак операции, то из стека извлекают-
ся знаки операций, приоритет которых больше или равен приоритету данной
операции, и они помещаются в строку-результат, после чего рассматривае-
мый знак переносится в стек. Когда выражение заканчивается, выполняются
такие же действия, что и при встрече закрывающей скобки.
Рассмотрим алгоритм на примере простейшего выражения:
a + ( b - c ) * d
Таблица 1. Перевод выражения в постфиксную форму.
Символ Действие
Состояние
выходной
строки
Состояние стека
a
'a' – переменная. Помеща-
ем ее в строку-результат.
a Пуст
+
'+' – знак операции. Поме-
щаем его в стек (поскольку
стек пуст, приоритеты
можно не проверять).
a +
(
'(' – открывающая скобка.
Помещаем в стек.
a
(
+
b
'b' – переменная. Помеща-
ем ее в выходную строку.
a b
(
+
-
'-' – знак операции, кото-
рый имеет приоритет 2.
Проверяем стек: на верши-
не находится символ '(',
приоритет которого равен
1. Следовательно, мы
должны просто поместить
текущий символ '-' в стек.
a b
-
(
+
с
'c' – переменная. Помеща-
ем ее в выходную строку.
a b c
-
(
+
Таблица 1. Перевод выражения в постфиксную форму.
78
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                             .
ся там знаки операций до ближайшей открывающей скобки, которая также
удаляется из стека. Все эти знаки в порядке их извлечения помещаются в
строку-результат. Когда же встречается знак операции, то из стека извлекают-
ся знаки операций, приоритет которых больше или равен приоритету данной
операции, и они помещаются в строку-результат, после чего рассматривае-
мый знак переносится в стек. Когда выражение заканчивается, выполняются
такие же действия, что и при встрече закрывающей скобки.
    Рассмотрим алгоритм на примере простейшего выражения:
                                 a+(b-c)*d

                               Таблица 1. Перевод выражения в постфиксную форму.
                                                   Состояние
     Символ                    Действие            выходной     Состояние стека
                                                    строки
                     'a' – переменная. Помеща-
         a                                             a             Пуст
                     ем ее в строку-результат.

                     '+' – знак операции. Поме-
                     щаем его в стек (поскольку
         +                                             a               +
                     стек пуст, приоритеты
                     можно не проверять).

                     '(' – открывающая скобка.                         (
         (                                             a
                     Помещаем в стек.                                  +

                     'b' – переменная. Помеща-                         (
         b                                             ab
                     ем ее в выходную строку.                          +

                     '-' – знак операции, кото-
                     рый имеет приоритет 2.
                     Проверяем стек: на верши-
                                                                       -
                     не находится символ '(',
         -                                             ab              (
                     приоритет которого равен
                                                                       +
                     1.    Следовательно,    мы
                     должны просто поместить
                     текущий символ '-' в стек.

                     'c' – переменная. Помеща-                         -
         с           ем ее в выходную строку.         abc              (
                                                                       +




                               Таблица 1. Перевод выражения в постфиксную форму.
                                            78

Страницы