|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serg Belyaev 2:5015/166.7 01 May 2003 16:51:50
To : Sergey Krouglov
Subject : компиляторы
--------------------------------------------------------------------------------
26-Apr-03 00:25:58, Sergey Krouglov wrote to All
Subject: компиляторы
SK> Hello, All!
SK> Есть у кого может код компилятора лучше на сях из постфиксной
SK> (префиксной) в
SK> инфиксную, или хотя бы формальный разбор? Где можно побобное в инете или
SK> фиде
SK> поискать?
Может поможет:
Обратная польская нотация
При обычной записи арифметических выражений, которая называется инфиксной,
знак операции ставится между операндами, например {a+b}. При постфиксной
записи, называемой также обратной польской, знак операции ставится после
операндов, например {ab+}. При обратной польской записи нет необходимости
пользоваться скобками:
(a+b)*(c+d) соответсвует ab+cd+*
Hаписать процедуры преобразования инфиксной записи в постфиксную
и обратную - из постфиксной в инфиксную.
Решение
Разбор арифметического выражения начинающим программистам часто кажется
трудным делом, но это не совсем так. Идея подобного разбора достаточно
простая. Сначала выражение разбивается компоненты, связанные друг с
другом операциями '+' или '-'. В этом случае перевод в постфиксную
запись никакого труда не составляет:
A+B переходит в AB+
A-B переходит в AB-
Отдельно рассмотрим случай, когда выражение начинается
с символов '+', '-':
+A переходит в A
-A переходит в A(-)
Разбивка на любое количество компонент, связанных операциями
сложения и вычитания также, естественно, затруднения не вызывает.
Попробуем это записать:
procedure expression;
var a:char;
begin
if sym='+' then getsym else
if sym='-' then begin a:='-';getsym end else a:=' ';
term;
if a='-' then so:=so+' (-)';
while sym in oper1 do begin
a:=sym;getsym;term;so:=so+a
end
end;
В этой процедуре в строку {so} отправляется постфиксная запись.
С помощью {getsym} мы получаем очередной рассматриваемый символ из
исходного арифметического выражения (как это делается, нас не должно
на данном этапе интересовать). Обратим внимание на то, что до начала
работы процедуры {expression} должна отработать процедура {getsym}.
Осталась процедура {term}, которая должна произвести перевод в
постфиксную запись те части выражения, которые нельзя представить в
виде суммы или разности. Какие это части (назовем их термами)? Это
может быть отдельный идентификатор, выражение в скобках, произведение
или частное термов
<терм>::= (<выражение>)|
<идентификатор>|
<терм>*<терм>|
<терм>/<терм>
Процедура для разбора термов очевидная:
procedure term;
var a:char;
begin
if sym='(' then begin getsym;expression;getsym end
else get_var;
while sym in oper2 do begin
a:=sym;getsym;term;so:=so+a
end
end;
Здесь для получения идентификатора служит процедура {get_var}. Hа этом,
в общем то, разбор арифметического выражения и заканчивается. Остались
несущественные детали, которые могут меняться в конкретных реализациях.
Hапример, можно процедуру {get_var} использовать не только для получения
идентификаторов, но и для разборки дополнительных конструкций типа
функций (в том числе показательной). Важно заметить, что все эти
дополнительные уточнения никак не могут повлиять на основные процедуры
{term} и {expression}.
Приведем вариант решения нашей задачи
const oper1=['+','-'];
oper2=['*','/'];
symbol=['a'..'z','A'..'Z','0'..'9','.'];
var sym :char;
so,si :string;
p :word;
procedure getsym;
begin
while (p<=length(si))and(si[p] in [' ',#9]) do inc(p);
if p>length(si) then sym:=#0 else begin
sym:=si[p];inc(p)
end;
end;
procedure expression;forward;
procedure get_var;
begin
so:=so+' ';
while sym in symbol do begin so:=so+sym;getsym end
end;
procedure term;
var a:char;
begin
if sym='(' then begin getsym;expression;getsym end
else get_var;
while sym in oper2 do begin
a:=sym;getsym;term;so:=so+a
end
end;
procedure expression;
var a:char;
begin
if sym='+' then getsym else
if sym='-' then begin a:='-';getsym end else a:=' ';
term;
if a='-' then so:=so+' (-)';
while sym in oper1 do begin
a:=sym;getsym;term;so:=so+a
end
end;
begin
si:='-1.2-(-1*3.14+1/(a/b+cab*9))';so:='';p:=1;
getsym;expression;writeln(si);writeln(so);
end.
Построение инфиксной записи по заданной постфиксной можно осуществить
с использованием рекурсии. Hеявно используется механизм стека. Многие
программисты настороженно относятся к рекурсивным алгоритмам. Конечно,
возмутительно, когда факториал вычисляется с помощью алгоритма
Fact(n):=n*Fact(n-1),
но ... послушаем автора языка PASCAL H.Вирта:
"В действительности из-за того, что обычно понятие рекурсивных
алгоритмов объяснялось на неподходящих примерах, в основном и
возникло широко распространенное предубеждение против использования
рекурсии в программировании и приравнивание ее к неэффективности.
Повлиял на это и тот факт, что широко распространенный язык
программирования Фортран запрещает рекурсивное использование
подпрограмм и тем самым не допускает рекурсию, даже когда ее применение
оправданно.
...
Итак, вывод таков: следует избегать рекурсии, когда имеется очевидное
итеративное решение поставленной задачи.
Hо это не означает, что всегда нужно избавляться от рекурсии любой ценой.
Во многих случаях она вполне применима, как будет показано в следующих
разделах этой главы и в последующих главах. Тот факт, что рекурсивные
процедуры можно реализовать на нерекурсивных по сути машинах, говорит о
том, что для практических целей любую рекурсивную программу можно
преобразовать в чисто итеративную. Hо это требует явного манипулирования
со стеком рекурсий, и эти операции до такой степени заслоняют суть
программы, что понять ее становится очень трудно. Следовательно,
алгоритмы, которые по своей природе скорее рекурсивны, чем итеративны,
нужно представлять в виде рекурсивных процедур".
var str:string;
p:word;
so,si:string;
procedure getstr(var p:word);
const op=['+','-','*','/'];
var i:integer;
begin
while so[p]=' ' do dec(p);i:=p;
if so[p] in op then begin str:=so[p];dec(p);exit end;
str:=copy(so,p-2,3);
if str='(-)' then begin p:=p-3;exit end;
while (i>0) and not(so[i] in [' ']+op) do dec(i);
str:=copy(so,i+1,p-i);p:=i
end;
function inf(var p:word):string;
var i :integer;
s :string;
begin
getstr(p);
if str='(-)' then inf:='-'+inf(p) else
if (str='+')or(str='-')or(str='*')or(str='/') then
begin
s:=str;s:=s+inf(p);
inf:='('+inf(p)+s+')'
end
else inf:=str
end;
begin
so:='-2 7/ 3 5*+ (-) ';p:=length(so);
si:=inf(p);
writeln(si);
end.
С помощью процедуры getstr(p) мы определяем в строке с постфиксной
записью {so} элемент записи, находящийся слева от позиции {p}, и помещаем
этот элемент во временный буфер - строку {str}. Разбор ведем с конца
строки. Для сокращения числа скобок в выходном выражении функцию {inf}
можно немного изменить:
function inf(var p:word):string;
var i :integer;
s :string;
begin
getstr(p);
if str='(-)' then inf:='-'+inf(p) else
if (str='+') then begin
s:=inf(p);
if s[1]='-' then inf:='('+inf(p)+s+')'
else inf:='('+inf(p)+'+'+s+')'
end else
if (str='-') then begin
s:=inf(p);
if s[1]='-' then begin
s[1]:='+';inf:='('+inf(p)+s+')'
end
else inf:='('+inf(p)+'-'+s+')'
end else
if (str='*')or(str='/') then begin
s:=str;s:=s+inf(p);
inf:=inf(p)+s
end
else inf:=str
end;
Приведенные процедуры работают в предположении, что разбираемые выражения
правильно написаны. Если нам необходимо дополнительно контролировать
правильность, то требуется добавить необходимые проверки - это несложно.
Всего доброго,
<SVB> (Serg Belyaev)
--- Terminate 5.00/Pro
* Origin: (svb@sandy.ru) or (2:5015/166.7)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
