Разбор арифметического (и не только) выражения - Алгоритм Рутисхаузера
Данный алгоритм является одним из наиболее ранних. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявное старшинство операций при этом не учитывается. Например:
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 |
|------------|-----------------------------------|
|