Вычисление значения выражения в суффиксной записи

Порядок выполнения операций в суффиксной записи определён порядком следования операндов и операций в выражении.

Алгоритм вычисления значения выражения можно описать так:

1. Просматриваем запись выражения слева направо. При условии, что не все операции выполнены над соответствующими операндами, идём на шаг 2, иначе на шаг 3.

2. Если встретится одноместная операция и предшествующий ей операнд, то применяем эту операцию к операнду и заменяем последовательность «операнд – операция» их значением, т.е. операндом. Если встретится двуместная операция и предшествующие ей два операнда, то применяем операцию к операндам и заменяем последовательность «операнд – операнд – операция» их значением, т.е. операндом. Далее переходим к шагу 1.

3. Значение выражения найдено, процесс вычисления закончите.

Вычислить значение алгебраического выражения, записанного в польской суффиксной записи, достаточно легко, поэтому обратная польская запись широко используется при вычислениях на компьютере.

Задача. Создайте компьютерную модель процесса преобразования алгебраического выражения, записанного в традиционной инфиксной форме, в запись этого выражения в польской (бесскобочной) суффиксной форме.

Решение

Разработаем алгоритм преобразования алгебраического выражения, записанного в традиционной инфиксной форме, в польскую бесскобочную суффиксную форму.

Алгоритм:

1. Организуйте ввод алгебраического выражения, записанного в традиционной инфиксной форме. Запись выражения закончите знаком «=».

2. Для реализации процесса преобразования организуйте два стека: стек X, стек Y.

3. Пока не встретите символ «=», выполняйте шаги алгоритма 4, 4.1, 4.2.

4. Выбирайте последовательно, по одному символу слева направо, символы из исходного выражения. Операнды складывайте в стек X, а операции и левые скобки – в стек Y.

4.1. Если встретите правую скобку, то все символы стека Y до первой левой скобки последовательно выталкивайте из стека Y и складывайте в стек X. Далее выталкивайте левую скобку из стека Y. Вытолкнутую из стека Y левую скобку и просматриваемую правую скобку в стеки не помещайте.

4.2. Выбрав из исходного выражения очередную операцию, помещайте её в стек Y, если приоритет очередной выбранной операции меньше или равен приоритету операции, лежащей в вершине стека. В противном случае выталкивайте элементы из стека Y и помещайте их в стек X, до тех пор, пока не встретится левая скобка или дно стека.

Компьютерная модель1 процесса преобразования алгебраического выражения, записанного в традиционной инфиксной форме, в польскую суффиксную форму. Компьютерная модель реализована в системе Turbo Pascal с использованием указателей и динамических переменных. Алгебраическое выражение посимвольно вводится с клавиатуры в процессе работы с моделью, последний символ выражения «=».

program exspression;

type

tptr=^item;

item=record inf:char; next:tptr; end;

tfile=file of char;

var x,y,tmp,tmp1:tptr; ch,ch1:char; fl:boolean;f,f1:tfile;

procedure instek(var head:tptr; ch:char); {процедура занесения элемента сh в стек, на который указывает указатель Head (стек Х или стек Y или TMP1)}

var tmp:tptr;

begin

new(tmp); tmp^.inf:=ch; tmp^.next:=head; head:=tmp;

end;

procedure fromstek(var head:tptr; var ch:char);

{процедура чтения элемента из стека, определяемого указателем Head}

var tmp:tptr;

begin

tmp:=head; ch:=head^.inf; head:=head^.next;

end;

function priorit(ch:char):byte;

{функция задания приоритетов выполняемых операций}

begin

case ch of

'*','/': priorit:=3;

'+','-': priorit:=2;

'(': priorit:=1;

'=': priorit:=0;

end; end;

procedure print1(x1:tptr);

var ch3:char;

begin {вывод на экран элементов стеков X или Y или TMP1}

while x1<>Nil do

begin {запись элементов стека X1 (X или Y или TMP1)в стек tmp }

fromstek(x1,ch); instek(tmp,ch);

end;

while tmp<>Nil do

begin {вывод на экран элементов стека X1 }

fromstek(tmp,ch); write(ch,' ');

end;

writeLn;

end;

Begin {начало основной программы}

x:=Nil; y:=Nil; tmp1:=Nil;

repeat

write('Введите символ: '); readln(ch);instek(tmp1,ch);{ занесение элемента ch в стек tmp1, стек хранит запись введённого выражения в инфиксной форме)

{далее введённый символ записывается либо в стек X, либо в стек Y. Стек X – стек для первоначального занесения операндов и по определенным правилам знаков операций из стека Y; стек, в котором хранится суффиксная форма записи выражения, записанная в обратном порядке. Стек Y – стек, в который заносятся по определенным правилам знаки операций и левые скобки, а затем переписываются в стек X}

if ch in ['a'..'z'] then instek(x,ch);{занесение элемента в стек X}

if ch ='(' then instek(y,ch);{ занесение элемента в стекY}

if ch=')' then { блок, реализующий запись операций из стека Y в стек X до символа '('}

begin

while (y^.inf<>'(') do

begin fromstek(y,ch); instek(x,ch); end;

fromstek(y,ch);

end;

if ch in ['*','/','+','-','='] then {блок анализа элементов стека Y для соответствующей процедуры занесения знака операции в стек Y или переноса знаков операций из стека Y в стек X перед вталкиванием прочитанной операции в стек Y}

begin

repeat

fl:=true;

if y<>Nil then

if priorit(ch)<=priorit(y^.inf) then

begin fromstek(y,ch1); instek(x,ch1); fl:=false; end

until fl;

instek(y,ch);

end;

write('x - '); print1(x);{ вывод элементов стека X на экран после выполнения операции записи или перезаписи}

write('y - '); print1(y);{ вывод элементов стека Y на экран после выполнения операции записи или перезаписи}

write('tmp1 - '); print1(tmp1); {вывод элементов стека TMP1 на экран после выполнения операции записи}

WriteLn('********************');

until ch='=';

WriteLn ('Инфиксная запись выражения');

print1(tmp1);

WriteLn('Суффиксная запись выражения');

print1(x);

End.

Компьютерная модель 2 процесса преобразования алгебраического выражения, записанного в традиционной инфиксной форме, в польскую суффиксную форму. Компьютерная модель реализована в системе Turbo Pascal с использованием указателей и динамических переменных. Алгебраическое выражение, записанное в обычной форме, последний символ выражения ‘=’, посимвольно вводится из текстового файла, полное имя которого вы должны ввести с клавиатуры в процессе работы с моделью.

program exspression1;

label met;

type

tptr=^item;

item=record inf:char; next:tptr; end;

tfile=file of char;

var x,y,tmp,tmp1:tptr; ch,ch1:char; fl:boolean;

f:text; name:string;

procedure instek(var head:tptr; ch:char); {процедура занесения элемента сh в стек, на который указывает указатель Head (стек Х или стек Y или TMP1)}

var tmp:tptr;

begin

new(tmp); tmp^.inf:=ch; tmp^.next:=head; head:=tmp;

end;

procedure fromstek(var head:tptr; var ch:char);

{процедура чтения элемента из стека, определяемого указателем Head}

var tmp:tptr;

begin

tmp:=head; ch:=head^.inf; head:=head^.next;

end;

function priorit(ch:char):byte;

{функция задания приоритетов выполняемых операций}

begin

case ch of

'*','/': priorit:=3;

'+','-': priorit:=2;

'(': priorit:=1;

'=': priorit:=0;

end; end;

procedure print1(x1:tptr);

var ch3:char;

begin {вывод на экран элементов стеков X или Y или TMP1}

while x1<>Nil do

begin {запись элементов стека X1 (X или Y или TMP1) в стек tmp }

fromstek(x1,ch); instek(tmp,ch); {стек TMP - стек дополнительный,

используется для вывода элементов стека X1 в привычной форме}

end;

while tmp<>Nil do

begin {вывод на экран элементов стека X1 }

fromstek(tmp,ch); write(ch,' ');

end;

writeLn;

end;

Begin {начало основной программы}

x:=Nil; y:=Nil; tmp1:=Nil;

write ('введите имя исходного текстового файла '); readln (name);

assign (f,name); reset(f);

Repeat

Repeat

Read(f,ch); if ch=' ' then goto met;{ чтение символа ch выражения из файла f в ОЗУ}

instek(tmp1,ch);{ занесение элемента ch в стек TMP1,

стек TMP1 хранит инфиксную запись введённого выражения}

{введённый символ записывается либо в стек X, либо в стек Y. Стек X – стек для первоначального занесения операндов и по определенным правилам знаков операций из стека Y; стек в котором хранится суффиксная форма за-писи выражения, записанная в обратном порядке. Стек Y – стек, в который заносятся по определенным правилам знаки операций и левые скобки, а затем переписываются в стек X}

if ch in ['a'..'z'] then instek(x,ch);{занесение элемента в стек X}

if ch ='(' then instek(y,ch);{ занесение элемента в стекY}

if ch=')' then { блок, реализующий запись операций из стека Y в стек X до символа '('}

begin

while (y^.inf<>'(') do

begin fromstek(y,ch); instek(x,ch); end; fromstek(y,ch);

end;

if ch in ['*','/','+','-','='] then {блок анализа элементов стека Y для соответствующей процедуры занесения знака операции в стек Y или переноса знаков операций из стека Y в стек X перед вталкиванием прочитанной операции в стек Y}

begin

repeat

fl:=true;

if y<>Nil then

if priorit(ch)<=priorit(y^.inf) then

begin fromstek(y,ch1); instek(x,ch1); fl:=false; end

until fl;

instek(y,ch);

end;

write('x - '); print1(x);{ вывод элементов стека X на экран после выполнения операции записи или перезаписи}

write('y - '); print1(y);{ вывод элементов стека Y на экран после выполнения операции записи или перезаписи}

write('tmp1 - '); print1(tmp1); {вывод элементов стека TMP1 на экран после выполнения операции записи}

writeLn('********************');

met:Until eoln(f);

Readln(f); { чтение метки конца строки}

until (ch='=')or (eof(f));

close(f);

WriteLn ('Инфиксная запись выражения'); print1(tmp1);

WriteLn('Суффиксная запись выражения'); print1(x);

End.

Таблица 2.

Результат исполнения программы, полученной в окне ввода-вывод системы PABC

Компьютерная модель 3 процесса преобразования алгебраического выражения, записанного в традиционной инфиксной форме, в польскую суффиксную форму. Компьютерная модель реализована в системе Turbo Delphi с использованием указателей и динамических переменных. Алгебраическое выражение посимвольно вводится с клавиатуры, последний символ выражения «=».

type

tptr=^item; item=record

inf:string; next:tptr; end;

var x,y,x1:tptr; ch,ch1,ch3:string;

fl:boolean; j:longint

A:array[1..26] of string; z:'a'..'z';

procedure instek(var head:tptr; ch:string);

{процедура занесения элемента сh в стек, на который указывает указатель Head (стек х или стек y)}

var tmp:tptr;

begin

new(tmp);

tmp^.inf:=ch;

tmp^.next:=head;

head:=tmp;

end;

procedure fromstek(var head:tptr; var ch:string);

{процедура чтения элемента из стека, определяемого указателем Head}

var tmp:tptr;

begin

tmp:=head; ch:=head^.inf; head:=head^.next;

end;

function priorit(ch:string):byte;

{функция задания приоритетов выполняемых операций}

begin

if (ch='*') or (ch='/') then priorit:=3; if (ch='+') or (ch='-') then priorit:=2;

if (ch='(') then priorit:=1; if (ch='=') then priorit:=0;

end;

procedure TForm1.Button1Click(Sender: TObject);

var s:string;i:byte; flag:boolean;

begin

x:=Nil; y:=Nil; j:=1;

Label1.Caption:='='; Label4.Caption:=''; Label5.Caption:='';

{формирование массива терминальных символов}

for z:='a' to 'z' do

begin

A[j]:=z; j:=j+1;

end;

i:=0; s:=edit1.Text;

repeat

{стек х – стек для первоначального занесения операндов и по определенным правилам знаков операций из стека y; стек, в котором хранится суффиксная форма записи, записанная в обратном порядке.

стек y – стек, в который заносятся по определенным правилам знаки операций и левые скобки, а затем переписываются в стек х}

{занесение элемента в стек х}

i:=i+1;

ch:=s[i];

showmessage('Обрабатываем символ '+ch);

flag:=false;

for j:=1 to 26 do

if ch=A[j] then flag:=true;

if flag then instek(x,ch);

if ch='(' then instek(y,ch);{занесение элемента в стек y}

if ch=')' then {блок, реализующий запись операций из стека y в стек х до символа '('}

begin

while y^.inf<>'(' do

begin

fromstek(y,ch); instek(x,ch);

end;

fromstek(y,ch);

end;

if (ch='*') or (ch='/') or (ch='+') or (ch='-') or (ch='=') then {блок выбора стека х или стека y для соответствующей процедуры: занесения знака операции в стек y или переноса знаков операций из стека y в стек х}

begin

repeat

fl:=true;

if y<>Nil then

if priorit(ch)<=priorit(y^.inf) then

begin

fromstek(y,ch1); instek(x,ch1); fl:=false;

end;

until fl;

instek(y,ch);

end;

x1:=x;

Label4.Caption:='';

while x1<>Nil do

begin

ch3:=x1^.inf; x1:=x1^.next;

Label4.caption:= Label4.caption+#13+ch3;

end;

Application.ProcessMessages;

for j:=1 to 50000000 do;

x1:=y;

Label5.Caption:='';

while x1<>Nil do

begin

ch3:=x1.inf; x1:=x1.next;

Label5.caption:= Label5.caption+#13+ch3;

end;

Application.ProcessMessages;

for j:=1 to 50000000 do;

until ch='=';

Label5.Caption:='';

while x<>Nil do

begin {блок записи элементов стека х в пустой стек y }

fromstek(x,ch); label1.Caption:=label1.Caption+ch; instek(y,ch);

end;

Label1.Caption:='=';

while y<>Nil do

begin {блок вывода суффиксной записи выражения на экран}

fromstek(y,ch);

if ch<>'=' then label1.Caption:=label1.Caption+ch;

end;

end;

end.

Date: 2015-07-17; view: 457; Нарушение авторских прав