Алгоритм Рутисхаузера Данный алгоритм является одним из наиболее ранних. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявное старшинство операций при этом не учитывается. Например: D:=((C-(B*L))+K) Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему пpавилу: если это откpывающаяся скобка или пеpеменная, то значение увеличивается на 1; если знак опеpации или закpывающаяся скобка, то уменьшается на 1. Для выражения (А+(В+С)) присваивание значений уровня будет происходить следующим образом : |-------|---------------------------------------| |N симв.| 1 2 3 4 5 6 7 8 9 | |-------|---------------------------------------| |Символы| | |строки | ( A + ( B * C ) ) | |-------|---------------------------------------| |Номера | | |уровней| 1 2 1 2 3 2 3 2 1 | |-------|---------------------------------------| Алгоритм складывается из следующих шагов: выполнить расстановку уровней; выполнить поиск элементов строки с максимальным значением уровня; выделить тройку - два операнда с максимальным значением уровня и операцию, которая заключена между ними; результат вычисления тройки обозначить вспомогательной переменной; из исходной строки удалить выделенную тройку вместе с ее скобками, а на ее место поместить вспомогательную переменную, обозначающую результат, со значением уровня на единицу меньше, чем у выделенной тройки; выполнять п.п.2 - 5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения. Пример разбора : |------------|--------------------------------------| |Генерируемые| Выражение | | тройки | | |------------|--------------------------------------| | | ( ( ( ( А + В ) * С ) / D ) - E ) | | | 0 1 2 3 4 5 4 5 4 3 4 3 2 3 2 1 2 1 0| | | | |+ А В - > R | ( ( ( R * C ) / D ) - E ) | | | 0 1 2 3 4 3 4 3 2 3 2 1 2 1 0 | | | | |* R C -> S | ( ( S / D ) - E ) | | | 0 1 2 3 2 3 2 1 2 1 0 | | | | |------------|--------------------------------------| |------------|-----------------------------------| |Генерируемые| Выражение | | тройки | | |------------|-----------------------------------| |/ S D -> Q | ( Q - E ) | | | 0 1 2 1 2 1 0 | | | | |- Q E -> T | T | |------------|-----------------------------------| Алгоритм Бауэра и Замельзона Из ранних стековых методов расматривается алгоритм Бауэра и Замельзона. Алгоритм использует два стека и таблицу функций перехода. Один стек используется при трансляции выражения, а второй - во время интерпретации выражения. Обозначения: Т - стек транслятора, - стек интерпретатора. В таблице переходов задаются функции, которые должен выполнить транслятор при разборе выражения. Возможны шесть функций при прочтении операции из входной строки: - f1 - заслать операцию из входной строки в стек Т; читать следующий символ стpоки; - f2 - выделить тройку - взять операцию с вершины стека Т и два операнда с вершины стека Е; вспомогательную переменную, обозначающую результат, занести в стек Е; заслать операцию из входной строки в стек Т; читать следующий символ стpоки; - f3 - исключить символ из стека Т; читать следующий символ стpоки; - f4 - выделить тройку - взять операцию с вершины стека Т и два операнда с вершины стека Е; вспомогательную переменную, обозначающую результат, занести в стек Е; по таблице определить функцию для данного символа входной строки; - f5 - выдача сообщения об ошибке; - f6 - завершение работы. Таблица переходов для алгебраических выражений будет иметь вид(символ $ является признаком пустого стека или пустой строки): |----------|---------------------------------| | | Операция из входной строки | | |---------------------------------| | | $ ( + - * / ) | |----------|---|-----------------------------| |Операция |$ | 6 1 1 1 1 1 5 | |на вершине|( | 5 1 1 1 1 1 3 | |стека Т |+ | 4 1 2 2 1 1 4 | | |- | 4 1 2 2 1 1 4 | | |* | 4 1 4 4 2 2 4 | | |/ | 4 1 4 4 2 2 4 | |----------|---|-----------------------------| Алгоритм просматривает слева направо выражение и циклически выполняет следующие действия: если очередной символ входной строки является операндом, то он безусловно переносится в стек Е; если же операция, то по таблице функций перехода определяется номер функции для выполнения. Для выражения А+(В-С)*D ниже приводится последовательность действий алгоритма. |-------|--------|-------|-------|----------| |стек Е | стек Т |Входной|Номер | Тройка | | | |символ |функции| | |-------|--------|-------|-------|----------| |$ | $ | A | | | |$A | $ | + | 1 | | |$A | $+ | ( | 1 | | |$A | $+( | B | | | |$AB | $+( | - | 1 | | |$AB | $+(- | C | | | |$ABC | $+(- | ) | 4 |- B C ->R | |$AR | $+( | ) | 3 | | |$AR | $+ | * | 1 | | |$AR | $+* | D | | | |$ARD | $+* | $ | 4 |* R D ->Q | |$AQ | $+ | $ | 4 |+ A Q ->S | |$S | $ | $ |Конец | | |-------|--------|-------|-------|----------|  8  Комментарии к статье  8 8  Обсудить в чате