求free pascal 环境下编写栈求表达式,尽量加上说明,分为判断与计算两个模块,思路尽量清晰,

求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.