Алгоритм 1. Данный алгоритм основан на представлении математического выражения в виде дерева и использовании третьего способа его обхода,
Напомним его на конкретном примере.
Алгоритм 1. Данный алгоритм основан на представлении математического выражения в виде дерева и использовании третьего способа его обхода,
Напомним его на конкретном примере.
Пусть задано простое арифметическое выражение вида:
(A+B)*(C+D)-E . (10.1)
Представим это выражение в виде дерева, в котором узлам соответствуют операции, а листьям - операнды. Построение начинается с корня, в качестве которого выбирается операция, которая выполнятся последней. Левой ветви соответствует левый операнд операции, а правой ветви - правый. Дерево выражения (10.1) имеет вид:
Совершим обход дерева, под которым понимается формирование строки из символов узлов и ветвей дерева. Обход будем совершать от самой левой ветви вправо и узел переписывать в выходную строку только после рассмотрения всех его ветвей. Обход совершаем строго по уровням.
Уровень 1: имеем АВ+CD+
Поднялись на Уровень 2: имеем *Е
И наконец Корень: имеем -
Результат обхода дерева таким образом имеет вид:
AB+CD+*E - (10.2)
Характерные особенности выражения (10.2) состоят в следовании символов операций за символами операндов и в отсутствии скобок. Такая запись и называется обратной польской записью.
Алгоритм 2. Использование стека. Получение обратной польской записи из исходного выражения может осуществляться весьма просто на основе простого алгоритма, предложенного Дейкстрой. Для этого он ввел понятие стекового приоритета операций, который приведен в таблице:
|
Операция |
Приоритет |
|
( |
0 |
|
) |
1 |
|
+ - |
2 |
|
* / |
3 |
Суть алгоритма в следующем. Просматривается исходная строка символов слева направо, операнды переписываются в выходную строку, а знаки операций заносятся в стек на основе следующих соображений:
а) если стек пуст, то операция из исходной строки переписывается в стек;
б) операция выталкивает из стека все операции с большим или равным приоритетом в выходную строку;
в) если очередной символ из исходной строки есть открывающая скобка, то он проталкивается в стек;
г) закрывающая круглая скобка выталкивает все операции из стека до ближайшей открывающей скобки, сами скобки в выходную строку не переписываются, а уничтожают друг друга.
Процесс получения обратной польской записи выражения (1) представлен в таблице:
|
Просматриваемый символ |
Входная строка |
Состояние стека |
Выходная строка | ||
|
1 |
( |
( | |||
|
2 |
A |
( |
A | ||
|
3 |
+ |
+ |
( | ||
|
4 |
B |
+ |
( |
B | |
|
5 |
) |
+ | |||
|
6 |
* |
* | |||
|
7 |
( |
( |
* | ||
|
8 |
C |
( |
* |
C | |
|
9 |
+ |
+ |
( |
* | |
|
10 |
D |
+ |
( |
* |
D |
|
11 |
) |
* |
+ | ||
|
12 |
- |
- |
* | ||
|
13 |
E |
- |
E | ||
|
14 |
- |
Получили: AB+CD+*E-
Теперь идем дальше.
Обратная польская запись обладает рядом замечательных свойств, которые превращают ее в идеальный промежуточный язык при трансляции.
Вычисление выражения, записанного в обратной польской записи, может проводиться путем однократного просмотра, что является весьма удобным при генерации объектного кода программ.
Например, вычисление полученного выражения может быть проведено следующим образом:
|
Шаг |
Анализируемая строка |
Действие |
|
1 |
AB+CD+*E- |
R1=A+B |
|
2 |
R1CD+*E- |
R2=C+D |
|
3 |
R1R2*E- |
R1=R1*R2 |
|
4 |
R1E- |
R1=R1-E |
|
5 |
R1 |
Здесь R1 и R2 - вспомогательные переменные.
Варианты заданий
При выполнении программы ввести исходное выражение и значение операндов. В результате получить выражение в постфиксной форме и значение выражения.
Пример: 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
15)R=(a+b*c)/(d-e) a=9.1 b=0.6 c=2.4 d=3.7 e=8.5 R=-2.196
Контрольные вопросы