если S (/) - операция. Однако из-за того, что S (А) - первая операция в последовательности, S {k-1) и S {k-2) должны быть операндами. На шаге 2 алгоритм POSTFIX удаляет S{k-\) и S{k~2) со стека, вычисляет T=S{k-l)S{k)S{k-2) и помещает Т на стек, как если бы Т был еще одним операндом.

В этот момент конфигурация стека в точности такова, как было бы в случае, если первоначальное постфиксное выражение было более коротким: S(l) . .S{k-3)TS{k+l). . .S{N). Но, поскольку значение такого измененного выражения (можно показать, что оно правильное постфиксное выражение) равно значению первоначального выражения и так как по предположению индукции алгоритм POSTFIX правильно работает на всех постфиксных выражениях длины sN, мы заключаем, что алгоритм POSTFIX правильно вычисляет исходное выражение.

Полное доказательство правильности алгоритма POSTFIX должно было "бы включать в себя доказательства некоторых из приведенных выше утверждений. Мы опускаем эти доказательства ради краткости.

Легко видет., что постфиксное выражение можно вычислить за время 0{N) с помощью стека, так как при чтении каждого из N символов S(l), S(2), . . ., S{N) выполняется не более, чем постоянное число операций. Следует отметить несколько свойств алгоритма POSTFIX:

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

2. Алгоритм разрабатывался для обработки выражений, в которых операнды не должны состоять из нескольких букв или цифр.

3. Недопустимо появление в выражении констант или обращений к функциям.

4. В выражении не должно быть одноместных операций, например -А или +А-В.

5. Алгоритм никогда не инициализирует стек нулями и не заполняет стек нулями после того, как значения были использованы; наверное, это стоило бы делать из эстетических соображений, но не обязательно.

Можно, однако, изменить алгоритм POSTFIX так, чтобы можно было освободиться от каждого из этих ПЯТИ условий; мы оставляем это в качестве упражнения вместе с задачей реализации алгоритма POSTFIX.

Мы уже убедились, насколько легко вычисляется арифметическое выражение, как только оно переведено в постфиксную форму.

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

приоритет

i, ) б

+, - 1

*. / 2

** 3

Алгори™ работает, читая символы инфиксного выражения слева направо. Все операнды (переменные) поступают на выход по мере чтения; остальные символы помещаются на стек и либо удаляются, либо поступают на выход позже в соответствии с приведенным выше правилом приоритетов.

Algorithm IIP (Инфиксная в Постфиксную). Перевести инфиксное выражение S(l) S(2) . . . S{N), /V>1, в постфиксную форму. S{I) - либо буква (т. е. операнд, или переменная), левая или правая скобка, либо знак операции (т. е. один из символов +, -, », /, или »». Алгоритм использует стек STORE и приоритетную функцию Р, где «е», «(», «)» имеют приоритет О, Р{+)=Р{-) = 1, P(s)=P(/)=2, Р(**)=3. Шаг 0. [Инициализация] Set STORE (1)=е; and /1. Шаг 1. [Цикл] For / 1 to /V do through шаг 6 od.

Шаг 2. [Буква] If S{I) буква then PRINT S(/) fi.

Шаг 3. [Левая скобка] If S (/)=«(» then [поместить на стек]

set J J+l; STORE [J) S (/) fi. Шаг 4. [Правая скобка] If S (/)=«)». then [снять со стека] while STORE (/)=7«(» do шаг 5 od; and set / J-l fl. Шаг 5. [Печать верхнего элемента стека] PRINT STORE (/); and set JJ-1. Шаг 6. [Оператор] While P(S (/)XP(STORE (/)) do PRINT STORE (J); and set J J-1 od; [поместить на стек] set J ч- J+1; and STORE (J) ч- S (/). Шаг 7. [Печать остатка стека] While STORE {3)фг do PRINT STORE (J); and set J J-l od; and STOP.

Ha рис. 5.3.7 приведена блок-схема алгоритма ITP, а рис. 5.3.8 иллюстрирует выполнение этого алгоритма на заданном инфиксном арифметическом выражении. Например, в строке 3 знак операции помещается на стек; в строке 4 операнд В поступает на выход; в строке 5 символ «)» вызывает передачу на выход верхнего символа стека (этим символом оказался знак -).

Сложность алгоритма ITP оказывается 0{N). Это следует из таких свойств алгоритма:

1. Один проход производится над N символами последовательности.

Начала j

БукВа

щместить Хиа стек

Операция

Вывоз

STOR€(JJ;

остальной час vu стека

-fogvaHu

Рис. 5.3.7. Блок-схема алгоритма ITP,

2. На стек может попасть самое большее N12 символов (т. е. операций).

3. Все символы, остающиеся на стеке, могут быть выведены по окончании чтения не более, чем за 0{N) операций.