Алгоритм Рутисхаузера
Данный алгоритм является одним из наиболее ранних. Его особенностью является предположение о полной скобочной структуре выражения.
Под полной скобочной записью выражения понимается запись, в которой
порядок действий задается расстановкой скобок. Неявное старшинство
операций при этом не учитывается. Например:
D:=((C-(B*L))+K)
Обрабатывая выражение с полной скобочной структурой, алгоритм
присваивает каждому символу из строки номер уровня по следующему
пpавилу:
1. если это откpывающаяся скобка или пеpеменная, то значение увеличивается на 1;
2. если знак опе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 |
|-------|---------------------------------------|
Алгоритм складывается из следующих шагов:
1. выполнить расстановку уровней;
2. выполнить поиск элементов строки с максимальным значением уровня;
3. выделить тройку - два операнда с максимальным значением уровня и операцию, которая заключена между ними;
4. результат вычисления тройки обозначить вспомогательной переменной;
5. из исходной строки удалить выделенную тройку вместе с ее скобками, а на ее место поместить вспомогательную переменную, обозначающую
результат, со значением уровня на единицу меньше, чем у выделенной
тройки;
6. выполнять п.п.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 | $ | $ |Конец | |
|-------|--------|-------|-------|----------|
|
