Например: входная строка: (1+2)-(1+2)
выходная строка: 0
Для реализации данного алгоритма я использовал польскую запись.
Вот алгоритм которым я пользовался:
______________
Рассматриваем поочередно каждый символ:
1. Если этот символ - число (или переменная), то просто помещаем его в выходную строку.
2. Если символ - знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3). Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка.
Получив один из этих символов, мы должны проверить стек:
а) Если стек все еще пуст, или находящиеся в нем символы (а находится в нем могут только знаки операций и открывающая скобка) имеют меньший приоритет, чем приоритет текущего символа, то помещаем текущий символ в стек.
б) Если символ, находящийся на вершине стека имеет приоритет, больший или равный приоритету текущего символа, то извлекаем символы из стека в выходную строку до тех пор, пока выполняется это условие; затем переходим к пункту а).
3. Если текущий символ - открывающая скобка, то помещаем ее в стек.
4. Если текущий символ - закрывающая скобка, то извлекаем символы из стека в выходную строку до тех пор, пока не встретим в стеке открывающую скобку (т.е. символ с приоритетом, равным 1), которую следует просто уничтожить. Закрывающая скобка также уничтожается.
Если вся входная строка разобрана, а в стеке еще остаются знаки операций, извлекаем их из стека в выходную строку.
Рассмотрим алгоритм на примере простейшего выражения:
Дано выражение:
a + ( b - c ) * d
Результат:
a b c - d * +
------------------------------------------------------
Я попробовал реализовать данный алгоритм, но у меня возникли проблемы (выражение никак не хочет переводиться в польскую запись). Уважаемы программисты помогите пожалуйста найти ошибки в моем коде.
Код
const
max=1000;
type
STACK = record
top:integer;
elem:array [1..max] of char;
end;
{---------------------------------------}
procedure MakeNull (var S:STACK);
begin
S.top:=max + 1;
end;
{---------------------------------------}
function Empty (var S:Stack):boolean;
begin
if S.top > max then
Empty:=true
else
Empty:=false;
end;
{----------------------------------------}
function Top( s : stack) : char;
begin
if Empty(s) then exit
else
Top := s.elem[s.top];
end;
{---------------------------------------}
procedure OutStack (var s:stack; symv:char; var output:string);
begin
if Empty (s) then exit
else
begin
symv:= s.elem[s.top];
s.top:=S.top + 1;
output:=output+symv;
end;
end;
{---------------------------------------}
procedure Instack (var S:Stack;x:char);
begin
if S.top = 1 then exit
else
begin
s.top:=s.top-1;
s.elem[s.top]:=x;
end;
end;
{----------------------------------------}
function Prior(f : char) : Byte;
begin
case f of
'+','-' : prior := 2;
'*','/' : prior := 3;
'(' , ')' : prior := 1;
else
prior := 0;
end;
end;
{----------------------------------------}
procedure opz (s:stack; var output:string);
var
i: integer; input:string;
t: boolean;
elem:char;
begin
Makenull(s);
write ('Inp = ');
readln (input);
for i:=1 to length (input) do
case input[i] of
'0'..'9': output:=output+input[i];
'+','-','*','/': begin
t:=Empty(s);
if (t=true) or (prior(input[i]) > prior(top(s))) then instack(s,input[i]);
if prior(top(s))>=prior(input[i]) then
while (prior(top(s))>=prior(input[i])) do
begin
outstack(s,elem,output);
end;
instack (s,input[i]);
end;
end;
for i:=max downto s.top do
output:=output+s.elem[i];
writeln ('out = ',output);
end;
var
outp,inp:string;
s1:stack;
begin
OPZ (s1,outp);
writeln ('---------------------------');
readln;
end.