Алгоритм Рутисхаузера

Алгоритм Рутисхаузера является одним из наиболее ранних алгоритмов разбора выражений. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявное старшинство операций при этом не учитывается. Например: 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 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home