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

Алгоритм Рутенхаузера предназначен для трансляции арифметических выражений в форму, эквивалентную машинному языку.

Выражение должно быть записано в полной скобочной структуре. Например, формула a+b*c запишется в виде a+(b*c).

Обрабатывая выражение с полной скобочной структурой, алгоритм Рутенхаузера присваивает каждому символу S_i из строки с формулой число N_i, согласно алгоритму, приведённому ниже. Здесь S(j) – j-й символ, а N(j) – j-е число и используется переменная содержащая самое большое присвоенное N(j) значение.

Алгоритм: Присвоить.

Присвоить 1: N(0)¬0; J¬0

Присвоить 2: J¬J+1; Если конец строки, то N(J)¬0 и выход;

Присвоить 3: Если S(J) это «(» или «операнд», то N(J)¬N(J-1)+1; перейти к Присвоить 2;

Присвоить 4: Иначе N(J)¬N(J-1)-1; перейти к Присвоить 2;

Первый символ S(0) является пробелом, являющимся фактически началом строки. Заметим, что конечное значение J на единицу больше длины строки. Например, пусть задана цепочка a+(b*c) тогда присвоение чисел будет происходить согласно следующей таблице:

J	0	1	2	3	4	5	6	7	8
S(J)		A	+	(	b	*	c	)
N(J)	0	1	0	1	2	1	2	1	0

Далее транслятор ищет наибольшее значение N(J). Это значение, назовем его K, появляется в структуре вида N(J): … (K-1) K (K-1) K (K-1) … Рассматриваемая структура соответствует последовательности символов следующего вида: Z операнд₁ Θ операнд₂ R.

Символ Z – либо левая скобка, либо левый конец выражения.

Точно также R – это правая скобка или правый конец выражения.

Символ Θ представляет ОПЕРАЦИЮ.

При обнаружении такой структуры значение двуместного выражения вычисляется и запоминается во временной ячейке T_i. Тройка T_i <= операнд₁ Θ операнд₂ фиксируется. Обработанные три символа вместе с Z и R (если последние являются скобками) удаляются, а на их место помещается T_i со значением N=(K-1). Если Z и R – концы строки, процесс завершен. В противном случае алгоритм повторяет поиск наибольшего числа N. Приведенный выше пример после однократной обработки имеет такой вид:

S(J)		A	+	Ti
N(J)	0	1	0	1	0

Конечно, требование полной скобочной структуры является жестким ограничением. Были трансляторы, которые в предтрансляции вставляли как скобки, так и специальные символы (есть пример, когда запись арифметического выражения в 15 символов после вставки скобок стала содержать 87 символов).

Более сложный пример применения метода Рутенхаузера, обрабатывающий арифметическое выражение (((a + b)*c) + d)¸(e + (a¸f)).

Генерация тройки	Выражение
T1=a+b	( ( ( a + b ) * c ) + d ) ¸ ( e + ( a ¸ f ) ) 0 1 2 3 4 3 4 3 2 3 2 1 2 1 0 1 2 1 2 3 2 3 2 1 0
T1=T1*c	( ( T1 * c ) + d ) ¸ ( e + ( a ¸ f ) ) 0 1 2 3 2 3 2 1 2 1 0 1 2 1 2 3 2 3 2 1 0
T2=a – f	( T1 + d ) ¸ ( e + ( a – f ) ) 0 1 2 1 2 1 0 1 2 1 2 3 2 3 2 1 0
T1=T1 + d	( T1 + d ) ¸ ( e + T2 ) 0 1 2 1 2 1 0 1 2 1 2 1 0
T2=e+T2	T1 ¸ ( e + T2 ) 0 1 0 1 2 1 2 1 0
T1=T1T2	T1 ¸ T2 0 1 0 1 0
	T1 0 1 0