Главная Полное построение алгоритма [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 помещается на верх стека,
Рис. 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 |