Алгоритм, использующий дерево
Данный алгоритм основан на представлении математического выражения в виде дерева и использовании третьего способа его обхода (см. п. 15.5.6). Напомним его на примере арифметического выражения (A+B)*(C+D)–E.
Представим это выражение в виде дерева, в котором узлам соответствуют операции, а листьям – операнды. Построение начинается с корня, в качестве которого выбирается последняя выполняемая операция. Левой ветви соответствует левый операнд операции, а правой ветви – правый. Дерево выражения имеет вид:
Совершим обход дерева, под которым понимается формирование строки из символов узлов и ветвей дерева. Обход будем совершать от самой левой ветви вправо и узел переписывать в выходную строку только после рассмотрения всех его ветвей. Обход совершаем строго по уровням:
1) уровень 2: АВ+CD+
2) поднялись на уровень 1: *Е
3) и, наконец, корень: –
В результате такого обхода получили обратную польскую запись:
AB+CD+*E– (15.1)
Дата добавления: 2015-09-11; просмотров: 1011;