infa_1 / 42.Прямая и обратная польская записи
..docПрямая и обратная польская записи.
Польская запись позволяет преобразовать любое арифметическое выражение, состоящее из натуральных чисел, знаков арифметических операций и скобок, равнозначных по форме выражения, не содержащего скобок, при этом арифметические операции записываются в том же порядке, в каком и выполняются.
В обратной польской записи аргументы записываются перед знаком своей операции через какой-либо разделительный знак.
Метод перевода в польскую запись заключается в том, что на каждом шаге обработки арифметического выражения работают только с двумя числами и одной операцией, при этом операции обрабатываются последовательно.
В случае элементарного арифметического выражения, состоящего из 1 операции обратная польская запись получается простым переносом знака операции перед аргументами. Требуется также учесть баланс скобок. Если на пути переносимого знака встречаются скобки, то необходимо пройти закрывающих скобок ровно столько, сколько и открывающих.
Алгоритм составления польской записи можно оформить как процесс последовательного переноса знаков за правый аргумент.
Отметим, что каждый переброшенный знак будет точками для того, чтобы его можно было отличить от еще необработанного. По завершении процесса удалить все точки и оставшиеся скобки.
Program poland_record
uses crt;
var
strok: string;
alfavit: array [1..2] of set of char;
n: integer;
procedure remove (sign1, sign2: char)
var
num, n, tek, n_skobka, st, tochka: integer;
c: string;
function prov (c: char; num: integer): boolean;
begin
if not (sin alfavit [num])
then prov:=false
else
begin
if (strok [tek-1]='.') and (strok [tek+1]-'.')
then prov:= false else prove:= true;
end;
end;
begin
if sight ='+' then num:= 2 else num:= 1;
tek=1
repeat
if (strok [tek]=sign1) or (strok [tek]=sign2) then
if(strok [tek-1]<>'.') or (strok [tek+1]<>'.') then
begin
st:=tek;
n_skobka:=0;
repeat
tek:=tek+1;
if strok [tek]='(' then n_skobka:=n_skobka+1;
if strok [tek]=')' then n_skobka:=n_skobka-1;
until (n_skobka =0 and prov (strok [tek], num)) or (n_skobka<0);
if (strok [tek]=')' and (n_skobka=0) then tek:=tek+1;
c:='.'+strok[st]+'.';
insert (c, strok, tek);
tek:=st;
strok [st]=' ';
end;
tek:=tek+1
until tek>=length (strok);
end;
begin
clrscr;
alfavit[1]=['*', '/', '+', '-'];
alfavit[2]=['+', '-'];
readln (strok);
remove ('*', '/');
remove ('+', '-');
while pos ('(', strok) >0 do delet (strok, pos ('(', strok),1);
while pos (')', strok) >0 do delet (strok, pos (')', strok),1);
while pos ('.', strok) >0 do delet (strok, pos ('.', strok),1);
writeln (strok);
readln;
end.