 |
|||||||||||||
 |
|||||||||||||
|
|||||||||||||
|
|||||||||||||||||||||||||||||||||||
第三节 栈“栈”是一种先进后出(First In Last Out)或后进先出(Last In First Out)的数据结构。日常生活中也常能见到它的实例，如压入弹夹的子弹，最先压进去的子弹最后射出，而最后压入的子弹则最先发射出来。 “栈”是一种只能在一端进行插入和删除的特殊的线性表，进行插入和删除的一端称为“栈顶”，而不动的一端称为栈底(如下图)。插入的操作也称为进栈(PUSH)，删除的操作也称为出栈(POP)。 出栈 ←─┐ ┌──进栈 │ │ ↓│ ├───┤ 栈顶→│ an │ ├───┤ │ ... │ ├───┤ │ a2 │ ├───┤ 栈底→│ a1 │ └───┘ 例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 clrscr； 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.
练习三 1、假设一个算术表达式中可包含三种括号：圆括号“(”和“)”；方括号“[”和“]”以及花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用，试利用栈的运算，判别给定的表达式中所含括号是否正确配对出现。 分析：如果括号只有一种，比如说是“(”和“)”，则判断是否正确匹配可以这样进行： 用一个计数器T来记录左括号与右括号比较的情况，初始时T=0，表达式从左向右扫描，如果遇到左括号则T←T+1，遇到右括号则T←T-1，中间如果出现T<0的情况，说明右括号的个数大于左括号的个数，匹配出错；扫描结束时，如果T<>0，说明左右括号的个数不相等，匹配出错。 但本题的括号有三种，这里用栈可以较好地解决，方法如下： (1)将“(”，“[”，“{”定为左括号，“)”，“]”，“}”定为右括号，建一个栈来存放左括号，初始时，栈为空； (2)从左向右扫描表达式，如果是左括号，则将其压入栈中；如果是右括号则 （a）栈顶是与该右括号匹配的左括号，则将它们消去，重复(2) （b）栈顶的左括号与该右括号不匹配，则匹配错误； (3)扫描结束时，若栈非空，则匹配错误。 2、计算四个数：由键盘输入正整数A，B，C，D(1<=A，B，C，D<=10)；然后按如下形式排列： A□B□C□D=24；在四个数字之间的□处填上加，减，乘，除四种运算之一(不含括号)，输出所有满足条件的计算式子。若不能满足条件，则打印“NORESULT!“。 分析：A，B，C，D四个数的位置已经固定，因此只需将+，-，*，/四种运算符依次放入三个□中，穷举所有可能的情况，再计算表达式的值即可。 |