Умова задачі
Побудувати абстрактне синтаксичне дерево, кожна з вершин якого відображає операцію (+,-,*,/), кожний лист - значення числа. Підрахувати результат арифметичних операцій.
Алгоритм
1. Формування масивів вузлових та термінальних вершин дерева. Повторювати дії, поки не натиснута клавіша 'n' :
1.1.1. Ввід значень елементів дерева;
1.1.2. Якщо елемент рядка - це арифметична операція, то формувати значення вузлів дерева;
1.1.3. Якщо елемент рядка - це число, то занести його до масиву;
1.1.4. Ввід ознаки кінця вводу даних.
2. Вивід вхідного дерева:
2.1. Вивід термінальних вершин;
2.2. Циклічний вивід проміжних вершин.
3. Виконання арифметичних дій, що задані в вузлах дерева:
3.1. Виділення пам'яті для правого листка дерева, визначення значення листка;
3.2. Вибір та виконання операцій відповідно до вузлових вершин дерева, формування масиву результатів операцій;
3.3. Виділення пам'яті для кожного лівого листка дерева, визначення значення лівого листка;
3.4. Виділення пам'яті для кожної нової вершини, занесення результату виконання операцій до пам'яті;
3.5. Переадресування покажчиків на праву та ліву вершини дерева.
4. Вивід дерева результатів:
4.1. Вивід кореня дерева;
4.2. Циклічний вивід проміжних вершин від кореня до термінальних вершин.
5. Кінець.
Приклад: Вираз 5+12*4. Дерево + . Кількість рівнів визначається при /\ вводі виразу. На екран виводиться
5 * відображення дерева.
/\
12 4
uses crt;
type maintree=^tree; {покажчик на структуру "дерево"}
tree=record
a:real; {елемент дерева}
left:maintree; {покажчик на лiву гiлку дерева}
right:maintree; {покажчик на праву гiлку дерева }
end;
charset=set of char; {множина символiв}
var sym:char; {визначення кiнця вводу}
s:charset; {множина арифметичних операцiй}
l,k,p:maintree; {покажчики на елементи дерева }
result,i,j,n:integer; {робочi змiннi}
m:real; {розрахунок виразу}
str:string; {рядок вхiдних даних}
ms:array [1..10] of integer; {масив значень листкiв дерева}
mc:array [1..10] of char; {масив вершин}
{формування масивiв вузлових та термiнальних вершин дерева}
procedure form_ar;
begin
repeat
readln(str); {ввiд значень елементiв дерева}
for i:=1 to length(str) do {аналiз рядка даних}
begin
if str[i] in s then {якщо елементом рядка є арифметична
операцiя}
begin
n:=n+1; {лiчильник рiвнiв дерева}
mc[n]:=str[i]; {формування значень вузлiв дерева}
end
else {якщо елемент рядка не операцiя}
begin
j:=j+1; {лiчильник термiнальних вершин-листкiв}
val(str[i],ms[j],result); {перетворення символа в число,
занесення до масиву чисел}
end;
end; {end for}
sym:=readkey; {ввiд ознаки кiнця вводу даних}
until sym='n'; { кiнець вводу}
end;
{-----вiдображення вхiдного дерева------- }
procedure enter_tree;
begin
gotoxy(12,20-2*n-1); write('lnput tree :');
gotoxy(20,20); write(ms[2],' ',ms[1]);{термiнальнi вершини}
gotoxy(20,19); write(' / \ ');
for i:=1 to n-1 do {промiжнi вершини дерева}
begin
gotoxy(20-i,20-2*i); write(ms[i+2],' ',mc[i]);
gotoxy(20-i,19-2*i); write(' / \');
end;
gotoxy(20-n+2,20-2*n);write(mc[n]);
end;
{виконання арифметичних дiй, що заданi в вузлах дерева}
procedure solution;
begin new(l); {видiлення пам'ятi для правого листка дерева}
l^.a:=ms[1]; {значення листка - перший елемент масива}
l^.left:=nil; l^.right:=nil;{покажчики на лiвий та правий листки
порожнi}
for i:=1 to n do {перебiр вершин та аналiз дiй}
begin
case mc[i] of {вибiр та виконання операцiй вiдповiдно до
вузлових вершин}
'+': m:=l^.a+ms[i+1]; {якщо операцiя +, то знайти суму двох
елементiв,}
'-': m:=l^.a-ms[i+1]; {що знаходяться на термiнальних вершинах
одного рiвня}
'*': m:=l^.a*ms[i+1];
'/': m:=l^.a/ms[i+1];
end;
new(k); {видiлення пам'ятi для кожного лiвого листка
дерева}
k^.a:=ms[i+1]; {визначення значення лiвого листка}
k^.left:=nil; {покажчики порожнi}
k^.right:=nil;
p:=l; {покажчик на поточний правий лист}
new(l); {пам'ять для кожної нової вершини}
l^.a:=m; {значення вершини-результат виконання
операцiй}
l^.right:=p; {правий покажчик на поточну вершину}
l^.left:=k; {лiвий покажчик на поточну лiву вершину}
end;
end;
{вiдображення дерева результатiв обчислення}
procedure print_tree;
begin
p:=l; {покажчик на корiнь дерева}
gotoxy(35,20-2*n-1); write('Building tree:');
gotoxy(42,20-2*n); write(l^.a:3:1);{вивiд значення кореня дерева}
for i:=1 to n do {вивiд n-рiвневого дерева}
begin
gotoxy(40+2*i,20-2*n+2*i);
l:=l^.left; {перемiщення покажчика лiворуч вiд поточної
вершини}
write(l^.a:3:1); {вивiд значення лiвої вершини}
gotoxy(45+2*i,20-2*n+2*i);
p:=p^.right; {перемiщення покажчика праворуч вiд
поточної вершини}
write(p^.a:1:1); {вивiд значення правої вершини}
gotoxy(40+2*i,20-2*n+2*i-1);write(' / \');
l:=p; {перепризначення покажчика}
end;
gotoxy(1,23);
end;
{--------------------головна програма----------------------}
begin clrscr;
n:=0; {початкове значення рiвнiв дерева}
j:=0; {початкове значення листкiв дерева}
s:=['+','-','*','/']; {множина вузлiв дерева}
writeln('enter syntax tree, press n to finish:');
form_ar; {формування масивiв вузлових та термiнальних
вершин дерева}
enter_tree; {вивiд вхiдного дерева}
solution; {виконання арифметичних дiй,що заданi в
вузлах дерева}
print_tree; {вивiд дерева результатiв}
readln;
end.
