Как построить бинарное дерево с помощью "Тривиев"

← →
Серый (2005-06-05 15:55) [0]

Люди, кто знает как сделать это дерево?
Вообщем так: пользователь вводит арефметическое выражение, оно проверяеться на правильность и если правильно строиться бинарное дерево где предки операция, а нащадок это число..
вот все выходит до построения..а дальше не как.
Если кто знает - помогите. За мной не засохнет:)

← →
Tihas © (2005-06-05 20:35) [1]

Вопрос не понятен? Он не однозначен!
Вырази свой вопрос более ясней!!!

← →
Серый (2005-06-05 23:36) [2]

Мне надо построить дерtво с помощью компоненты TreeView, а точнее используя ф-ии add и addchild...
У меня не выходит нечего. Может надо что другое...
А программа такая: Построить абстрактное синтаксическое дерево, каждая из вершин которого отображает операцию (+, –, *, /), каждый лист – значение числа. Вычислить результат арифметического выражения с помощью этого дерева.
извеняюсь за не понятность вопроса.

← →
Lenka © (2005-06-05 23:39) [3]

ну как.....кто-нибудь видел синтаксическое дерево в паскале? вот его нужно реализовать в делфи. не подскажете, что нужно переделать? вот листинг для паскаля

program Plagiat;
uses Crt;
type
ptr=^node;
node=record
name:string[5];
level: integer;
left,right:ptr;
end;
var
root:ptr;
key: string[5];
setofoper,setofnum:set of char;
opa:string;
i:integer;
count:integer;
suma:integer;
sum:real;
lb1:integer;

function rez(t:ptr;sum1,sum2:real):real;
var
ch:char;
code:integer;
x:real;
begin
if t^.name[1] in setofoper then
begin
ch:=t^.name[1];
case ch of
"+":x:=sum1+sum2;
"-":x:=sum1-sum2;
"*":x:=sum1*sum2;
"/":x:=sum1/sum2;
end;
end
else val(t^.name,x,code);
rez:=x;
end;

procedure postorder(t:ptr;var sum:real; var lv: integer);
var sum1,sum2:real;
begin
sum1:=sum;
sum2:=sum;
if t<> nil then
begin
postorder(t^.left,sum1,lv); postorder(t^.right,sum2,lv);
sum:=rez(t,sum1,sum2);
if lv < t^.level then lv := t^.level;
end;
end;

procedure Inorder(t:ptr;lb:integer;var suma:integer);
begin
if t<> nil then
begin
inorder(t^.left,lb,suma); inorder(t^.right,lb,suma);
if lb = t^.level then inc(suma);
end;
end;

procedure PrintTree(t:ptr; h: integer; c:integer);
var i: integer;
begin
if t<>nil then
with t^ do
begin
printtree(right,h+5,c+1);
for I:=1 to h do write(" ");
write(name); level := c;
writeln;
printtree(left,h+5,c+1);
end;
end;

procedure create(key:string;var t : ptr);
var st:string[10];
tmp:ptr;

begin
if t=nil then
begin
new(t);
with t^ do
begin
name:=key;
left:=nil;
right:=nil;
end;
end
else begin
if (t^.right<>nil) and (t^.right^.name[1] in setofnum) and
((((t^.name[1]="*") or (t^.name="/")) and {((t^.name="(") or (t^.name=")")) and}
((key[1]="+") or (key[1]="-"))) or
((t^.name[1]="-") and (key[1]="+"))) then
begin
new(tmp);
tmp^.name:=t^.name;
tmp^.left:=t^.left;
tmp^.right:=t^.right;
t^.name:=key;
t^.left:=tmp;
t^.right:=nil;
end
else begin
if (key[1] in setofoper) and (t^.name[1] in setofnum) then
begin
st:=t^.name;
t^.name:=key;
key:=st;
end;
if key[1] in setofoper then begin
create(key,t^.right);
end
else if t^.left<>nil then
create(key,t^.right)
else create(key,t^.left);
end;
end;
end;

BEGIN
textcolor(10);
clrscr;
root:=nil;
setofoper:=["+","-","*","/"];
setofnum:=["0","1","2","3","4","5","6","7","8","9"];
writeln("Введите арифм выражение без пробелов");
readln(opa);
key:="";
i:=length(opa);
if opa[i] in setofoper then
begin
writeln("Неправильное выражение");readln;
halt(1);
end;
for i:=1 to length(opa) do
begin
if (not (opa[i] in setofoper+setofnum)) or
((opa[i] in setofoper) and (opa[i+1] in setofoper)) then
begin
writeln(""Неправильное выражение"); readln;
root:=nil;
halt(1);
end;
if opa[i] in setofoper then
key:=opa[i]
else key:=key+opa[i];
if (opa[i] in setofoper) or (opa[i+1] in setofoper) or (i=length(opa)) then
begin
create(key,root);
key:="";
end;
end;
clrscr;
suma:=0;
count := 0;
printTree(root,0,0);
writeln;
writeln(opa);
write("Vod urovnya ");
readln(lb1);
writeln;
postorder(root,sum,count);
inorder(root,lb1,suma);
writeln(Результат работы: ",sum:3:3);
writeln("Счетчик уровней: ", count+1);
writeln(Счетчик вершин: ", suma);
readkey;
end.

← →
Ega23 © (2005-06-06 09:23) [4]

Если кто знает - помогите. За мной не засохнет:)

Хотелось бы знать - насколько не засохнет? Каков размер? Градус?

← →
Серый (2005-06-07 01:23) [5]

Хоть подсказку, или ссылки(((..
Может тут поможет рекурсия?

← →
Серый (2005-06-07 18:08) [6]

Пробовал рекурсию....мало что выходит..

Тут вопрос надо разделить на 2 части - синтаксический разбор выражения и засовывание всего этого в TreeView. С чем конкрено проблема - непонятно.
Можно использовать, например, алгоритм Дейкстры, при этом каждое запихивание в стек - это добавление Child"а, а каждое доставание из стека - подъем на один уровень вверх. Этот алгоритм можно посмотреть, например, на сайте algolist.manual.ru

TUser © (07.06.05 18:35) [7]
Не говори, вот я читаю и удивляюсь. Оказывается, для человека построить дерево сложнее, чем осуществить синтаксический разбор...

Послушайте, автор. А если я вам дам свою грамматику, вы мне напишете программу разбора? Я вам за это напишу хоть 100 деревьев.

← →
Серый (2005-06-07 19:47) [9]

pasha_golub ©
Оказывается, для человека построить дерево сложнее, чем осуществить синтаксический разбор...

Просто я проги на паскале писал..а на делфи нет. Поетому я только приблизительно догадываюсь как дерево построить.. я и задал такой вопрос...

TUser © (07.06.05 18:35) [7]
Тут вопрос надо разделить на 2 части - синтаксический разбор выражения и засовывание всего этого в TreeView. С чем конкрено проблема - непонятно.

Главная моя проблема то что я не знаю как мне переделать прогу, которая изложена выше, на делфи..

Послушайте, автор. А если я вам дам свою грамматику, вы мне напишете программу разбора? Я вам за это напишу хоть 100 деревьев.

Я вот понимаю, что если я ты что знаю в паскале, то в делфи я не чего не шарю..

Как построить бинарное дерево с помощью "Тривиев" Найти похожие ветки