Romeo_sh
Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Цитата:| Строим бинарное дерево, корень и вершины - операции (+, -, ...), листья - числа, обходим его рекурсивно начиная с корня, или в цикле начиная с вершин с листьями, пока не останется только корень, в нем и будет результат |
Цитата:| При "(" заталкываешь предыдущее в стек, при ")" - возвращаешся на предыдуший уровень. |
А можно, пожалуйста, поподробнее. Не совсем понимаю, что значит загнать в стек или построить бинарное дерево. На входе у нас строка вида "15*(48+29*(-55))-(23+67)/(88-58)"
простую задачу без скобок решаю вот так:
Код:
program test;
uses strings, strutils, sysutils;
var
str,newstr: string;
numbers: array[1..10] of real;
operators: array[1..9] of string;
posx,pos1,pos2,pos3,pos4,i,j:integer;
sum: real;
BEGIN
str:='4*2+9/3-5';
posx:=1;
i:=1;
{формируем из строки два массива - числа и операции}
while posx>0 do
begin
pos1:=pos('+',str);
pos2:=pos('-',str);
pos3:=pos('*',str);
pos4:=pos('/',str);
posx:=pos1;
if ((posx>pos2) and (pos2>0)) or (posx=0) then
posx:=pos2;
if ((posx>pos3) and (pos3>0)) or (posx=0) then
posx:=pos3;
if ((posx>pos4) and (pos4>0)) or (posx=0) then
posx:=pos4;
if (posx>0) then
begin
numbers[i]:=StrToInt(copy(str,1,posx-1));
operators[i]:=copy(str,posx,1);
inc(i);
str:=copy(str,posx+1,999);
end;
end;
numbers[i]:=StrToInt(str);
{Сначала выполняем операции умножения и деления}
for i:=1 to 9 do
begin
if (operators[i]='*') then
begin
operators[i]:='+';
numbers[i+1]:=numbers[i]*numbers[i+1];
numbers[i]:=0;
end;
if (operators[i]='/') then
begin
operators[i]:='+';
numbers[i+1]:=int(numbers[i]/numbers[i+1]);
numbers[i]:=0;
end;
end;
{потом вычитание}
for i:=1 to 9 do
begin
if (operators[i]='-') then
begin
operators[i]:='+';
numbers[i+1]:=numbers[i]-numbers[i+1];
numbers[i]:=0;
end;
end;
{складываем что получилось}
for i:=1 to 10 do
sum:=sum+numbers[i];
i:= round(sum);
writeln(i);
END.
|
|
