Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [ 82 ] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

должны вычисляться с использованием правила приоритета, устанавливающего, что деление (/) имеет больший приоритет, чем сложение (+), а NOT имеет больший приоритет, чем AND. С учетом этих приоритетов выражение А+В/С эквивалентно выражению А+(В/С), а NOT А AND В эквивалентно выражению (NOT А) AND В. Мы ввели в этом разделе скобки во избежание подобных осложнений.

Интересно заметить, что три различных способа прохождения деревьев на рис. 5.3.2 и 5.3.4 приводят к трем различным способам записи соответствующих выражений в виде линейной последовательности символов. Рассмотрим дерево простого арифметического вы- Рис. 5.3.4. Дерево для логического ражения (А+В), приведенное на выражения,

рис. 5.3.5. Если мы начнем с корня

или верхней точки (Т) этого дерева и напечатаем +, затем перейдем к левой (L) нижней вершине и напечатаем А, а далее перейдем обратно в корень и спустимся вправо (R) и напечатаем В, мы пройдем дерево в прямом порядке. Последовательность напечатанных символов, -f-ЛВ называется префиксной формой арифметического выражения; знак операции (+) предшествует операндам А н В.



tlr Прямой +АВ Префиксная

ltr Осратный А+В* Инфиксная

lrt Концевой Ав+ Постфиксная

Рис. 5.3.5. Три различных прохода по двоичному дереву и соответствующие линейные выражения.

Более привычная форма арифметического выражения (А+В) называется инфиксной формой; она получается при прохождении дерева в обратном порядке, обозначаемом LTR. Постфиксная форма арифметического выражения - в которой знак операции следует за операндами, например получается при концевом порядке

(LRT) прохождения дерева.

Здесь будет поучительно рассмотреть снова дерево на рис. 5.3.2. Для прохождения этого дерева в прямом порядке мы начнем с самой верхней вершины ТОР (помеченной +). Затем пройдем в прямом порядке левое поддерево (с корнем, помеченньм *) и далее правое поддерево в прямом порядке (с корнем, помеченным /). Прохождение левого поддерева в прямом порядке начинается с корня (помеченного *), затем следует прямое прохождение левого его поддерева (порож-



дающее последовательность -АВ) и далее правого поддерева (последовательность С). Поэтому вся последовательность, порождаемая прохождением левого поддерева вершины ТОР, будет *-ABC. Аналогично прохождение в прямом порядке правого поддерева с корнем, помеченным /, порождает последовательность IDvEF. Таким образом, прохождение всего дерева в прямом порядке порождает последовательность

Т L R

Прохождение этого дерева в обратном и концевом порядках порождает последовательности соответственно

A-BC + DIE **F

J--i (инфиксная)

L Т R

I Jl--Jl- (постфиксная)

L R T

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

Algorithm POSTFIX. Вычислить арифметическое выражение в постфиксной форме; выражение состоит из последовательности 5(1) 5(2) .. . S(N), Nl, где S(I) - либо буква (т. е. операнд, или переменная), либо один из знаков -f, -, *, /, ** (т. е. двухместная арифметическая операция); в алгоритме используется стек STORE. Шаг 0. [Инициализация] Set / 0.

Шаг 1. [Цикл] Рог /-t- 1 to do шаг 2 od; and STOP. (Значение выражения будет на верху стека STORE.) Шаг 2. [Чему равно S (/)?] И S (/) - операнд

then [поместить S(/) на стек] set J J-\-\;

and STORE (Л S(/). else [оценка подвыражения] sei Т\ STORE {J); Г2-е- STORE (/-1) [выполнение операции S{I) над Т\ и Т2] set ТЪ <-T\-S(1)Т2; set -1; and STORE (/) ГЗН.



Рис. 5.3.6 иллюстрирует выполнение алгоритма POSTFIX над арифметическим выражением в постфиксной форме: А В-C*DEF»»/+.

Например, в строке /=5 входной символ S(5)=« вызывает перемножение значений двух самых верхних элементов стека, С и 3.0 (строка 4); эти два элемента затем удаляются со стека, а их произведение 15.0 помещается на верх стека,

Входной символ

AB-C*DEF"*/ +

Содержимое стека 12 3 4

Значения геременных В стеке или переменная операция

А=4.0

А В

В = 1.0

А-В = 3.0

С = Б.О

1Б.0

3.0*С=15.0

1Б.0 D

D = 64.0

15.0 D Е

Е = 2.0

1Б.0 D Е F"

Р = Б.О

15.0 D 32.0

E*»F = 32.0

15.0 2.0

D/32.0 = 2.0

17.0 ,

15.0 + 2.0 = 17.0

Рис. 5.3.6. Вычисление арифметического выражения в постфиксной форме с использованием алгоритма POSTFIX.

Доказательство правильности алгоритма POSTFIX можно получить индукцией по длине N постфиксного выражения S(1)S(2). . . S{N). Такое доказательство зависит от индуктивного определения арифметического выражения и от процесса трансляции арифметического выражения из инфиксной формы в постфиксную (обсуждалось ранее).

Очевидно, что алгоритм POSTFIX работает правильно на постфиксных выражениях длины N=1 или Л=3. (По определению не существует постфиксных выражений длины N=2.) Это можно проверить с помощью ручного вычисления. Поэтому предположим, что алгоритм POSTFIX правильно вычисляет все постфиксные выражения длины <Л/.

Рассмотрим произвольное постфиксное выражение S(1)S(2). .. S{N-\-l) длины N+l. Пусть k - наименьшее целое, такое, что S (k) - операция. Тогда легко видеть, что эта операция должна быть применена к 5(-1) и 5(-2); S{k-l) и S{k-2) - оба являются операндами. Вообще говоря, S(/-1) и S{I-2) не обязательно операнды.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [ 82 ] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0014