求free pascal 环境下编写栈求表达式,尽量加上说明,分为判断与计算两个模块,思路尽量清晰,
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 22:30:41
求free pascal 环境下编写栈求表达式,尽量加上说明,分为判断与计算两个模块,思路尽量清晰,
求free pascal 环境下编写栈求表达式,尽量加上说明,分为判断与计算两个模块,思路尽量清晰,
求free pascal 环境下编写栈求表达式,尽量加上说明,分为判断与计算两个模块,思路尽量清晰,
方法1:
算术表达式的处理:由键盘输入一个算术表达式(含有+,-,*,/,(,)运算),且运算结果为整数),编一程序求该算术表达式的值.
分析:表达式的运算是程序设计中一个基本的问题,利用栈求解是一种简单易行的方法,下面介绍的是算符优先法.
比如:4+2*3-10/5
我们都知道,四则运算的法则是:(1)先乘除后加减,同级运算从左到右;(2)有括号先算括号.
因此上例的结果是8.
算符优先法需要两个栈:一个是操作数栈,用来存放操作数,记为SN;另一个是操作符栈用来存放运算符,记为SP.具体处理方法如下:
(1)将SN,SP置为空栈;
(2)从左开始扫描表达式,若是操作数压入SN中;若是操作符则与SP的栈顶操作符比较优先级有两种可能:
(a)优先级小于栈顶算符,此时从SN中弹出两个操作数,从SP弹出一个操作符,实施运算,结果压入SN的栈顶.
(b)优先级大于栈顶算符,此时将操作符压入SP中.
(3)重复操作(2)直至表达式扫描完毕,这时SP应为空栈,而SN只有一个操作数,即为最后的结果.
为了方便起见,可以将#作为表达式的结束标志,初始化时在SP的栈底压入#,并将其优先级规定为最低.
下面给出的是计算4+2*3-10/5#的示意图
步骤 SN SP 读入字符 │ 说明
—————————————————┼——————————
1 空 # 4 │ 将4压入SN
2 4 # + │ 将+压入SP
3 4 # + 2 │ 将2压入SN
4 4 2 # + * │ 将*压入SP
5 4 2 # + * 3 │ 将3压入SN
6 4 2 3 # + * - │ -的优先级小于*,因此将SN中的3,2弹出,
│ 将SP中的*弹出,将2*3的结果压入SN中
7 4 6 # + - │ -的优先级小于其左边的+,因此将SN中的
│ 4,6弹出,将SP中的+弹出,将4+6的结果压
│ 入SN中
8 10 # - │ -压入SP中
9 10 # - 10 │ 10压入SN中
10 10 10 # - / │ 将/压入SP中
11 10 10 # - / 5 │ 将5压入SN中
12 10 10 5 # - / # │ #优先级小于/,故SN中的10,5弹出,SP中
│ 的/弹出,将10/5的结果压入SN中
13 10 2 # - # │ #优先级小于-,故SN中的10,2弹出,SP中
│ 的-弹出,将10-2的结果压入SN中
14 8 # # │ #与#相遇,运算结束,SN中的8是最后计算
│ 的结果
Pascal程序:
Program lt7_3_1;
uses crt;
const number:set of char=['0’..'9'];
op:set of char=['+','-','*','/','(',')'];
var expr:string;
sp:array[1..100] of char;
sn:array[1..100] of integer;
t,tp,n,tn:integer;
function can_cal(ch:char):boolean;
begin
if (ch='#') or (ch=')') or ((sp[tp] in ['*','/']) and (ch in ['+','-']))
then can_cal:=true else can_cal:=false;
end;
procedure cal;
begin
case sp[tp] of
'+':sn[tn-1]:=sn[tn-1]+sn[tn];
'-':sn[tn-1]:=sn[tn-1]-sn[tn];
'*':sn[tn-1]:=sn[tn-1]*sn[tn];
'/':sn[tn-1]:=sn[tn-1] div sn[tn];
end;
dec(tn);dec(tp);
end;
begin
write('Expression : ');readln(expr);
write(expr+'=');
expr:=expr+'#';
tn:=0;tp:=1;sp[1]:='#';t:=1;
repeat
if expr[t] in number then
begin
n:=0;
repeat
n:=n*10+ord(expr[t])-48;
inc(t);
until not (expr[t] in number);
inc(tn);sn[tn]:=n;
end
else begin
if (expr[t]='(') or not can_cal(expr[t]) then
begin
inc(tp);sp[tp]:=expr[t];inc(t);
end
else if expr[t]=')' then
begin
while sp[tp]'(' do cal;
dec(tp);inc(t);
end
else cal;
end;
until (expr[t]='#') and (sp[tp]='#');
writeln(sn[1]);
end.
方法2:
通常采用运算符优先数法.
一般表达式中会遇到操作数、运算符和语句结束符等,以算术运算符为例,对每种运算赋予一个优先数,如:
运算符:× ÷ + -
优先数:2 2 1 1
(语句结束符“;”的优先数为零)
在运算过程中,优先数高的运算符应先进行运算(但遇到括号时,应另作处理).按这样的规定,对式(11.1)自左向右进行运算时,其计算顺序就被唯一地确定下来了.计算顺序确定后,在对表达式进行编译时,一般设立两个栈,一个称为运算符栈(OPS),另一个称为操作数栈(OVS),以便分别存放表达式中的运算符和操作数.编译程序自左向右扫描表达式直至语句结束,其处理原则是:
①凡遇到操作数,一律进入操作数栈;
②当遇到运算符时,则将运算符的优先数与运算符栈中的栈顶元素的优先数相比较;若该运算符的优先数大,则进栈;反之,则取出栈顶的运算符,并在操作数栈中连续取出两个栈顶元素作为运算对象进行运算,并将运算结果存入操作数栈,然后继续比较该运算符与栈顶元素的优先数.
例如式(11.1)中,当扫描到“+”和“×”时都要将运算符入栈.接着扫描到“-”号, 其优先数小于乘号所以乘号退栈,并执行8×2,将结果16再存入操作数栈.再将“-”号的优先数与运算符栈的栈顶元素“+”号的优先数相比较,两者相等,所以再将加号退栈,进行4+16,结果为20,再入栈,接着,由于运算栈已空,所以减号入栈.当扫描到“3”时,操作数入栈.当扫描到“;”时,其优先数最低, 所以减号退栈并执行20-3,结果为17并入栈.因已扫描到语句结束符,所以表达式的求值结束,结果为17.
例题模拟计算机处理算术表达式过程.从键盘上输入算术表达式串(只含+、-、×、÷运算符,充许含括号),输出算术表达式的值.设输入的表达式串是合法的.分析:建立两个栈,一个是操作数栈(number),一个是运算符栈(symbol),根据运算符的优先级对两个栈进行相应的操作.
const
max = 100;
var
number: array[0..max] of integer;
symbol: array[1..max] of char;
s, t: string;
i, p, j, code: integer;
procedure push; {算符入栈运算}
begin
inc(p);
symbol[p] := s[i];
end;
procedure pop; {运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算}
begin
dec(p);
case symbol[p + 1] of
'+': inc(number[p], number[p + 1]);
'-': dec(number[p], number[p + 1]);
'*': number[p] := number[p] * number[p + 1];
'/': number[p] := number[p] div number[p + 1];
end;
end;
function can: boolean; {判断运算符的优先级别,建立标志函数}
begin
can := true;
if (s[i] in ['+', '-']) and (symbol[p] '(') then exit;
if (s[i] in ['*', '/']) and (symbol[p] in ['*', '/']) then exit;
can := false;
end;
begin
write('String : ');
readln(s);
s := '(' + s + ')';
i := 1;
p := 0;
while i '9');
t := copy(s, j, i - j);
val(t, number[p], code);
repeat
if s[i] = ')' then {右括号处理}
begin
while symbol[p] '(' do
pop;
dec(p);
number[p] := number[p + 1];
end
else
begin {根据标志函数值作运算符入栈或出栈运算处理}
while can do
pop;
push;
end;
inc(i);
until (i > length(s)) or (s[i - 1] ')');
end;
write('Result=', number[0]);
readln;
end.