Пример. Использование бинарного дерева.

Пусть задано простое арифметическое выражение вида:

(a+b)*(c+d)-e (5.1)

Представим это выражение в виде дерева, в котором узлам соответствуют операции, а листьям - операнды.

Алгоритм построения такого дерева следующий.

1. Построение начинают с корня, в качестве которого выбирается операция, выполняющаяся последней. Левой ветви соответствует левый операнд операции, а правой ветви - правый.

2. Если выражение сложное, то далее в узлах очередного уровня размещают операции по восходящей очередности их выполнения.

3. В узлы последнего уровня помещают операции, которые будут выполнены в первую очередь.

4. И наконец операнды – листья дерева.

Дерево выражения (5.1) имеет вид:

Совершим обход дерева, под которым будем понимать формирование строки символов из символов узлов и ветвей дерева. Обход будем совершать от самой левой ветви вправо и узел переписывать в выходную строку только после рассмотрения всех его ветвей (обход по алгоритму «Левое поддерево – Правое поддерево – Корень», строго по уровням, т.е. последовательно снизу вверх). Результат обхода дерева имеет вид:

ab+cd+*e- (5.2)

Характерные особенности выражения (2) состоят в следовании символов операций за символами операндов и в отсутствии скобок. Такая запись называется обратной польской записью.

Обратная польская запись - идеальный промежуточный язык при трансляции:

вычисление выражения, записанного в обратной польской записи, проводится путем его однократного просмотра слева направо, что является весьма удобным при генерации объектного кода программ.

Алгоритм вычислений «ПОЛИЗ» следующий:

1. Если текущий элемент записи – операнд. То переходим к следующему элементу.

2. Если же текущий элемент записи – символ операции, то эта операция выполняется над ближайшими двумя операндами, расположенными слева от этой операции. Полученный результат размещают на месте самого левого операнда а сами операнды и символ операции из «ПОЛИЗа» вычеркивают.

В результате последовательно будут выполнены все операции а сама запись сократится до одного элемента: конечного результата.

Например, вычисление выражения (2) может быть проведено следующим образом:

Здесь r1и r2 - вспомогательные переменные.

r1 на пятом уровне – конечный результат

“Польская запись”

Получить выражение в постфиксной форме и вычислить по полученному ПОЛИЗу значение выражения.

Пример: R=(a+b)*(c-d)/e –вводимое выражение;

а=3 b=5 c=6 d=9 е=7 –значения операндов.

Результат выполнения программы:

R=ab+cd-*e/

R=-3.42857

Задания по вариантам

1)R=a/(b-c)*(d+e) a=8.6 b=2.4 c=5.1 d=0.3 e=7.9 R=-26.12

2)R=(a+b)*(c-d)/e a=7.4 b=3.6 c=2.8 d=9.5 e=0.9 R=-81.89

3)R=a-(b+c*d)/e a=3.1 b=5.4 c=0.2 d=9.6 e=7.8 R=2.16

4)R=a/b-((c+d)*e) a=1.2 b=0.7 c=9.3 d=6.5 e=8.4 R=-131.006

5)R=a*(b-c+d)/e a=9.7 b=8.2 c=3.6 d=4.1 e=0.5 R=168.78

6)R=(a+b)*(c-d)/e a=0.8 b=4.1 c=7.9 d=6.2 e=3.5 R=2.38

7)R=a*(b-c)/(d+e) a=1.6 b=4.9 c=5.7 d=0.8 e=2.3 R=-0.413

8)R=a/(b*(c+d))-e a=8.5 b=0.3 c=2.4 d=7.9 e=1.6 R=1.151

9)R=(a+(b/c-d))*e a=5.6 b=7.4 c=8.9 d=3.1 e=0.2 R=0.666

10)R=a*(b+c)/(d-e) a=0.4 b=2.3 c=6.7 d=5.8 e=9.1 R=-1.091

11)R=a-(b/c*(d+e)) a=5.6 b=3.2 c=0.9 d=1.7 e=4.8 R=-17.51

12)R=(a-b)/(c+d)*e a=0.3 b=6.7 c=8.4 d=9.5 e=1.2 R=-0.429

13)R=a/(b+c-d*e) a=7.6 b=4.8 c=3.5 d=9.1 e=0.2 R=1.173

14)R=a*(b-c)/(d+e) a=0.5 b=6.1 c=8.9 d=2.4 e=7.3 R=-0.144