Стек. Формы записи арифметических и логических выражений. Применение стека для компиляции выражений
Язык: Borland Pascal 7.0
Курс: Трансляторы и интерпретаторы
В данной статье рассматривается:
- Стек
- Формы записи арифметических и логических выражений
- Применение стека для компиляции выражений
- Тестирование и преобразование инфиксного выражения в обратную польскую запись
- Результаты преобразования
- Вычисление выражения
Program Massive_stack_statich; { Make 01.10.1998 }
Uses { All rights reserved }
Crt;
Const
n = 20;
Type
T_elem = Char;
Var
stack : array [1..n] of T_elem;
top : 0..n;
S_in,S_out : string[n];
R,z,i,y : Integer;
key,s,t : char;
q,q1,q2 : Boolean;
{--------------------------------------------------------------------------}
{ Вычисление выражения в обратной польской записи }
procedure solve;
var
k,l,m,i,j : integer;
tt : array[1..n] of real;
zz : array[1..n] of char;
s1,s2 : char;
r1,r2,rez : real;
q3 : boolean;
s_out2 : string[n];
begin
textcolor(0);
clrscr;
textcolor(15);
Writeln('Входное выражение : ',S_in);
Writeln('Выходное выражение : ',S_out);
s_out2:=s_out;
q3:=true;
k:=0;
l:=0;
for i:=1 to n do
begin
zz[i]:=' ';
tt[i]:=0;
end;
for i:=1 to length(s_out) do
begin
if s_out2[i] in ['+','-','*','/']
then
k:=k+1;
if s_out2[i] in ['a'..'z','A'..'Z']
then
begin
l:=l+1;
zz[l]:=s_out2[i]
end
end;
for i:=1 to l do
begin
textcolor(15);
write('Введите значение для переменной ',zz[i],' : ');
textcolor(11);
readln(tt[i])
end;
rez:=tt[1];
textcolor(14);
for i:=1 to k do
for j:=1 to length(s_out2) do
begin
if (s_out2[j] in ['*','-','+','/']) and q3
then
begin
s1:=s_out2[j-2];
s2:=s_out2[j-1];
for m:=1 to n do
begin
if zz[m] = s1
then
begin
r1:=tt[m];
l:=m
end;
if zz[m] = s2
then
r2:=tt[m];
end;
case s_out2[j] of
'+' :rez:=r1+r2;
'-' :rez:=r1-r2;
'*' :rez:=r1*r2;
'/' : if r2 <> 0
then
rez:=r1/r2
else
q3:=false
end;
tt[l]:=rez;
for m:=l+1 to n-1 do
begin
zz[m]:=zz[m+1];
tt[m]:=tt[m+1]
end;
Delete(s_out2,l+1,2);
Break
end;
end;
if q3
then
begin
write('Результат выражения равен ');
textcolor(10);
writeln(rez:10:4);
end
else
begin
textcolor(11+blink);
writeln('Деление на ноль !!!');
textcolor(15);
end;
readkey;
textcolor(0);
clrscr
end;
{--------------------------------------------------------------------------}
{ HELP , он и в Африке - хэлп }
Procedure Help;
begin
textcolor(0);
clrscr;
textcolor(10);
gotoxy(30,4);
writeln('Внимание !');
writeln;
writeln;
writeln;
writeln;
textcolor(15);
Writeln(' Во входном выражении могут использоваться следующие символы :');
writeln;
textcolor(14);
writeln(' ':10,'1-Cтрочные и прописные латинские буквы : A..Z , a..z ;');
writeln(' ':10,'2-Знаки операций : + , - , * , / ;');
writeln(' ':10,'3-Открывающая и закрывающая скобки : ( , ) .');
textcolor(11);
gotoxy(1,17);
writeln(' ':19,'Любые другие символы запрещены !');
writeln;
readkey;
textcolor(0);
clrscr
end;
{--------------------------------------------------------------------------}
Function NextChar:char;
begin
if z<=length(S_in)
then
Nextchar:=S_in[z]
else
NextChar:='#';
z:=z+1
end;
{--------------------------------------------------------------------------}
Function Pr(t:char):integer;
begin
case t of
'+','-' : pr:=1;
'*','/' : pr:=2;
'#','(' : pr:=0
else
pr:=3
end
end;
{--------------------------------------------------------------------------}
Function Rang(t:char):integer;
begin
case t of
'+','-','*','/' : rang:=-1;
'#',')' : rang:=0
else
rang:=1
end
end;
{--------------------------------------------------------------------------}
Procedure Results;
begin
Textcolor(0);
clrscr;
textcolor(15);
Writeln('Входное выражение : ',S_in);
Writeln('Выходное выражение : ',S_out);
readkey;
textcolor(0);
clrscr
end;
{--------------------------------------------------------------------------}
{ Процедура тестирования и преобразования инфиксного выражения в обратную
польскую запись }
Procedure Morfolog;
var
a1 : Char;
a2 : String[3];
begin
textcolor(15);
clrscr;
textcolor(15);
S_out:='';
write('Введите входное выражение :');
readln(S_in);
{------- Через этот тест не пройдёт ни один глюк -------}
q:=false;
for i:=1 to length(s_in) do
if not(s_in[i] in ['a'..'z','A'..'Z','+','-','*','/','(',')'])
then
q:= true;
for i:=2 to length(s_in) do
begin
if (s_in[i] in ['+','-','*','/']) and (s_in[i-1] in ['+','-','*','/'])
then
q:= true;
if (s_in[i] in ['a'..'z','A'..'Z']) and (s_in[i-1] in ['A'..'Z','a'..'z'])
then
q:= true
end;
y:=0;
for i:=1 to length(s_in) do
begin
if s_in[i] in ['+','-','*','/']
then
y:=y-1;
if s_in[i] in ['a'..'z','A'..'Z']
then
y:=y+1;
if y < 0
then
q:=true
end;
if y = 0
then
q:=true;
y:=0;
for i:=1 to length(s_in) do
begin
if s_in[i] = '('
then
y:=y+1;
if s_in[i] = ')'
then
y:=y-1;
if y < 0
then
q:=true
end;
if y > 0
then
q:=true;
y:=0;
for i:=1 to length(s_in) do
begin
if s_in[i] in ['A'..'Z','a'..'z']
then
y:=y+1;
end;
if y = 0
then
q:=true;
for i:=2 to length(s_in) do
begin
if (s_in[i]='(') and (s_in[i-1]=')')
then
q:=true;
if (s_in[i] in['+','-','*','/']) and (s_in[i-1]='(')
then
q:=true;
if (s_in[i-1] in['+','-','*','/']) and (s_in[i]=')')
then
q:=true;
if (s_in[i-1] in['a'..'z','A'..'Z']) and (s_in[i]='(')
then
q:=true;
if (s_in[i] in['a'..'z','A'..'Z']) and (s_in[i-1]=')')
then
q:=true;
end;
q2:= not q;
{----------------- Тестирование выражения закончено ---------------}
for i:=1 to n do
stack[i]:=#0;
top:=1;
stack[top]:='#';
r:=0;
z:=1;
s:=NextChar;
while (s<>'#')and q2 do
begin
if not(s in ['(',')'])
then
while (pr(s)<=pr(stack[top])) and q2 do
begin
t:=stack[top];
top:=top-1;
S_out:=S_out+t;
r:=r+rang(t);
if r<1
then
q2:=false
end;
if s = ')'
then
begin
while stack[top]<>'(' do
begin
t:=stack[top];
top:=top-1;
s_out:=S_out+t;
r:=rang(t)+r;
if r<1
then
q2:=false
end;
if stack[top] = '('
then
top:=top-1
end;
if s <> ')' then
begin
top:=top+1;
stack[top]:=s;
end;
s:=NextChar
end;
while (stack[top]<>'#') and q2 do
begin
t:=stack[top];
top:=top-1;
S_out:=S_out+t;
r:=r+rang(t);
if r<1
then
q2:=false
end;
if r<>1 then
q2:=false;
if not q2
then
writeln('Выражение некорректно !')
else
writeln('Преобразование выражения прошло успешно !');
readkey;
textcolor(0);
clrscr
end;
{--------------------------------------------------------------------------}
BEGIN
textcolor(0);
clrscr;
q1:=true;
q2:=false;
S_in:='';
S_out:='';
while q1 do
begin
textcolor(11);
gotoxy(17,2);
writeln('Программа студента гр. ПА-97 Шарова Евгения');
gotoxy(28,23);
writeln('All rights reserved.');
textcolor(10);
gotoxy(11,6);
writeln('Стек. Формы записи арифметических и логических выражений.');
writeln(' ':18,'Применение стека для компиляции выражений.');
textcolor(15);
gotoxy(22,10);
writeln('1...Преобразовать инфиксное выражение');
write(' ':25,'в обратную польскую запись');
gotoxy(22,12);
write('2...Результаты преобразования');
gotoxy(22,13);
write('3...Вычислить выражение');
gotoxy(22,14);
write('4...Help');
gotoxy(22,15);
write('5...Выход в ДОС');
key:=readkey;
case key of
'1' : Morfolog;
'2' : if q2
then
results;
'3' : if q2
then
solve;
'4' : help;
'5' : q1:= not q1;
else
begin
Sound(160);
Delay(17);
NoSound
end
end
end;
textmode(3)
END.
JavaScript — это язык веб-программирования, работающий на стороне клиента, позволяющий автоматизировать какую-либо деятельность на странице сайта, не нагружая сервер. Вся нагрузка лежит на компьютере пользователя. В нем можно создавать функции, а также использовать базовые алгоритмы, состоящие из следования-ветвления-цикла. Чаще всего программный код на языке JavaScript обрабатывается обычными веб-браузерами. |
Интересные материалы на сайте:
|
|