Пример:
(a+b)*(c/a*c - c*d)
наша задача привести это выражение в постфиксный вид
ab+cac*ed*-/+
Алгоритм построения ОПЗ
В стек будут помещаться только символы операций. Символы операндов из входной строки поступают сразу в выходную. Символы операций поступают в стек и при определенных условиях выталкиваются в выходную строку.
Открывающая скобка всегда попадает в стек, закрывающая скобка ни в стек, ни в выходную строку не попадает. Когда во входной строке встречается закрывающая скобка, то из стека выталкиваются все символы(операции) до первой встречной открывающей скобки включительно, причем знаки операций выталкиваются в выходную строку, а открывающая скобка пропадает.
При переводе выражения в ОПЗ обязательно необходимо учитывать приоритеты операций. Используются следующие приоритеты:
1) ( 0
2) +, - 1
3) *,/ 2
Чем больше значение приоритета, тем сильнее операция связывает операнды. Если во входной строке текущий символ знак операции, то сравниваются приоритеты операций строки и верхушки стека.
Если приоритет операции из входной строки больше приоритета операции из верхушки стека, то операция из входной строки помещается в стек, в противном случае из стека выталкиваются все операции с приоритетом большим, либо равным приоритету операции из входной строки. После чего операция из входной строки помещается в стек.
При встрече конца входной строки содержимое стека выталкивается в выходную строку.
Пример:
Point=^elsteka;
elsteka=record
oper:char;
prior:integer;
pred:point;
end;
Var
inh, out:string;
uk_steka:point;
L, i,j, tip:integer;
Procedure push(oper:char;prior:integer);
Var
r_uk:point;
Begin
new(r_uk);
r_uk^.pred:=uk_steka;
uk_steka:=r_uk;
uk_steka^.oper:=oper;
uk_steka^.prior:=prior;
end;
Procedure pop(priznak:boolean);
Var
r_uk:point;
Begin
if priznak then out:=out+uk_steka^.oper;
r_uk:=uk_steka;
uk_steka:=r_uk^.pred;
dispose(r_uk);
end;
Function prior(oper:char):integer;
type el_t_prior=record
oper:char;
prior:integer;
end;
const tabl_prior:array[0..4] of el_t_prior=
(
(oper:'('; prior: 0),
(oper:'+'; prior: 1),
(oper:'-'; prior: 1),
(oper:'*'; prior: 2),
(oper:'/'; prior: 2)
);
Var
i:integer;
Begin
for i:=0 to 4 do
if tabl_prior[i].oper=oper then
begin
prior:=tabl_prior[i].prior;
exit;
end;
end;
BEGIN
clrscr;
tip:=-1;
writeln('Vvedite arifmeticheskoe virazhenie:');
readln(inh);
out:='';
L:=length(inh);
uk_steka:=nil;
for i:=1 to L do
case inh[i] of
'A'..'Z','a'..'z': begin
out:=out+inh[i];
if (tip=0) then begin
write(' Oshibka!!! Dve podryad iduschie bukvi!!!');
Readkey;
exit;
end
else if (tip=3) then begin
write(' Oshibka!!! Propuschen znak mezhdu ~)~ i bukvoj!');
Readkey;
exit;
end;
tip:=0;
end;
'(': begin
push('(',prior('('));
if (tip=3) then begin
write(' Oshibka!!! Net znaka mezhdu ~)~ i ~(~ skobkami!');
Readkey;
exit;
end
else if (tip=0) then begin
write(' Oshibka!!! Propuschen znak mezhdu bukvoj i ~(~!');
Readkey;
exit;
end;
tip:=2;
end;
')': Begin
if (tip=1) then begin
write(' Oshibka!!! Propuschen znak mezhdu znakom i ~)~!');
Readkey;
exit;
end
else if (tip=2) then begin
write(' Oshibka!!! Otsutstvuet virazhenie v skobkah!');
Readkey;
exit;
end;
tip:=3;
while(uk_steka<>nil) and (uk_steka^.oper<>'(') do pop(true);
if uk_steka=nil then begin
writeln(' Net otkrivayuschej skobki dlya zakrivayuschej v pozicii: ',i,' !!!');
Readkey;
halt;
end;
pop(false);
end;
'+','-','*','/': begin
if (tip=1) then begin
write(' Oshibka!!! Podryad iduschie znaki!');
Readkey;
exit;
end
else if (tip=2) then begin
write(' Oshibka!!! Posle ~(~ idyot znak!');
Readkey;
exit;
end;
tip:=1;
while (uk_steka<>nil) and (prior(inh[i])<= uk_steka^.prior) do pop(true);
push(inh[i],prior(inh[i]));
end
else begin
writeln(' Neizvestnij simvol v pozicii: ',i,' !!!');
Readkey;
halt;
end;
end;
while (uk_steka<>nil) and (uk_steka^.oper<>'(') do pop(true);
if (uk_steka<>nil) then begin
writeln(' Vo vxodyaschej stroke est lishnie otkrivayuschie skobki!');
Readkey;
halt;
end;
writeln(' Vxodyaschaya stroka: ',inh);
writeln(' Vixodyaschaya stroka: ',out);
Readkey;
end.
Программная реализация деревьев. Пример алгоритма сравнения деревьев
Дерево может быть реализовано с помощью следующей структуры данных:
type
point=^node;
node=record
info:char;
lint, rint:point;
end;
При сравнении бинарных деревьев как правило сравнение начинают с вершины (корня) дерева, сравнивая информационную часть одного дерева с информационной частью другого дерева. Если имеет место равенство, то рекурсивно вызывается сравнение левого поддерева исходного первого дерева с левым поддеревом второго исходного дерева. Аналогично правые.
function equal(P1,P2:point):boolean;
begin
equal:=false;
if P1=P2 then equal:=true
else
if (P2<>Nil)and(P1<>Nil) then
equal:=(P1^.info=P2^.info)and equal(P1^.lint, P2^.lint)and equal(P1^.rint, P2^.rint)
else
equal:=false;
end;
Эта функция в случае равных значений указателей (в том числе и нулевых) выдает значение, в противном случае результат определяется так, если оба указателя отличны от нуля, то сравниваются их информационные части и их соответственно левые и правые поддеревья, если все сравниваемые объекты совпадают, то делается вывод о совпадении сравниваемых деревьев в целом.
Рекомендации:
Процедура ввода дерева тоже рекурсивна. Нужно ввести данные в корень дерева, затем в левое поддерево, затем в правое поддерево. В том случае, когда не существует поддерева надо вводить какой-то терминальный символ, говорящий о том, что эта ветвь закончилась.
Другими словами, ввод дерева может напоминать обход дерева. Обход дерева осуществляется различными способами и носит различные названия. Существуют 3 способа:
- Префиксный (сверху-вниз)
Алгоритм:
Если дерево не пусто, то префиксный обход это: корень дерева, узлы левого поддерева в префиксном порядке, узлы правого поддерева в префиксном порядке.
- Инфиксный порядок обхода дерева
Если дерево пусто, то список узлов пуст. Если дерево не пусто, то инфиксный порядок это: узлы левого поддерева в инфиксном порядке, корень дерева, узлы правого поддерева в инфиксном порядке.
- Суффиксный порядок обхода дерева
Если дерево не пусто, то это: узлы левого поддерева в суффиксном порядке, узлы правого поддерева в суффиксном порядке, корень дерева.
Суффиксный подход может быть применен для ввода арифметических выражений в дерево из ОПЗ.
Постфиксный обход при вводе из ОПЗ данных в дерево обязательно нужно учитывать приоритет операций.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 |
