Question

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

Answer 1

方法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 <= length(s) do
begin
while s[i] = '(' do {左括号处理}
begin
push;
inc(i);
end;
j := i;
repeat {取数入操作数栈}
inc(i);
until (s[i] < '0') or (s[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.