金山中学计算机竞赛班教程·数据结构
的算符优先级大于栈顶算符的优先级，这时才将欲进栈的算符入栈。若遇到‘)’时，将栈中算符退出送入A中，直至退出‘( ’为止。若遇表达式结束符‘#’，则依次退出栈中算符送入A中。
根据上述算法，将中缀表达式B * (D-C) + A转换成后缀表达式BDC-*A+ 的过程图3_1所示。
扫描E 栈S B * ( D -
* * ( * ( * ( - * ( -
转换至A B B B BD BD
C * BDC
) + BDC-
+ + BDC-*
【参考程序段】
A BDC-*A
const m=100;
# BDC-*A+ var E , A , S : array [1..m] of char;
图3_1 { E中为中缀式，A中为后缀式，S为栈}
i , j , t : integer; procedure postexp; begin
i:=1; j:=1; t:=0;
while E[ i ]<>’#’ do begin case E[ i ] of
‘a’.. ‘z’, ‘A’.. ‘Z’ : begin
A[ j ]:=E[ i ]; j:=j+1; end; ‘(’ : begin
t:=t+1; S[ t ]:= ‘(’; end; ‘)’ : begin
while s[ t ]< > ‘(’ do begin
A[ j ]:=s[ t ]; j:=j+1; t:=t-1; end; t:=t-1; end; ‘+’, ‘-’ : begin
while (t< >0) and (s[t]< > ‘(’) do begin A[ j ]:=S[ t ]; j:=j+1; t:=t-1; end;
t:=t+1; s[ t ]:=E[ i ]; end; ‘*’, ‘/’ : begin
while (t< >0) and (S[ t ]= ‘*’ or S[ t ]= ‘/’) do begin
A[ j ]:=S[ t ]; j:=j+1; t:=t-1;
3－6
金山中学计算机竞赛班教程·数据结构
end; {while}
t:=t+1; S[ t ]:=E[ i ]; end; end; {case} i:=i+1; end; {while}
while t< >0 do begin
A[ j ]:=S[ t ]; j:=j+1; t:=t-1; end;
A[ j ]:= ‘#’; end;
(二)、对后缀表达式求值
计算一个后缀表达式的值，在算法上比中缀表达式要简单得多，这是因为后缀表达式有两个优点：表达式无括号，也不需考虑运算符的优先级。 【算法思想】
对后缀表达式求值要使用一个栈来实现。
自左至右扫描后缀表达式，若遇数就入栈，若遇到运算符就从栈中退出两个数进行运算，并把计算结果入栈。如此下去，直至遇到结束符“#”为止。最后栈底元素值为所求得的结果。
【练习】将一个中缀表达式转换成后缀表达式，并对后缀表达式求值。 输入格式： （输入文件 bds.in）
第一行：中缀表达式，运算数均为大写字母，运算符含乘方‘^’
第二行开始： 每行为表达式中字母，及其对应的值，输入顺序按字典排序 输出格式： （输入文件 bds.out）
第一行： 该中缀表达式所对应的后缀表达式
第二行： 该表达式的值 输入输出举例：
输入： (bds.in) B * (D - C) + A^C A 4 B 10 C 3 D 8
3－7
输出： (bds.out) B D C - * A C ^ + 114 金山中学计算机竞赛班教程·数据结构
§3.3.2 地图着色问题
对地图着色，可使用“四染色”定理，它是计算机科学中的著名定理之一，可以用不多于四色对地图着色，使相邻的行政区域不重色。应用这个定理的结论，利用回溯算法可对一幅给定的地图染色。作为地图四色的示例如图 3_3所示，图中01、02、03、04、05、06、07为行政区编号，1色、2色、3色、4色为各区域的颜色，称为色数。 【算法思想】
从编号为01的区域开始逐一进行染色，对每个区域用色数1，2，3，4依次进行试探，并尽可能取小色数。若当前所取色数与周围已染色的区域不重色，则把该区的色数入栈，否则依次使用下一色数进行试探。若从1色至4色均与相邻的某区域发生重色，则需退栈回溯，修改栈顶区域的色数。
在实现此算法时，可用一个关系矩阵R ( 1: n , 1: n )来描述各区域之间的边界关系。若 第i区与第j区相邻（有共同边界），则R[ i , j ]的值为1，否则为0。图 3_3中所示的地图关系矩阵如图 3_4所示。为了记下每个区域当前染色结果而设立一个栈S( 1 : n )，栈的下标值表示区域号，栈中的内容是色数，如S[ 6 ] = 3表示06区域当前染色的色数是3。
R i j
1 2 3 4 5 6 7 1 0 1 1 1 1 1 0 2 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 图 3_3
3 1 0 0 1 【参考程序段】 4 1 0 1 0 const n=7; {地图中区域数} 5 1 0 1 1 type adjar=array[1..n,1..n] of 0..1; 6 1 1 0 1 ads=array[1..n] of 1..4;
7 0 0 0 0 procedure mapcolor (var r:adjr; var s:ads);
begin
图3_4
s[ 1]:=1; {01区染1色}
i:=2; j:=1; { i 为区域号，j为染色号} while i while ( j< =4 ) and ( i while ( kj ) do begin k:=k+1; { 判断相邻区是否已染色} if k s[ i ]:= j; i:=i+1; j:=1; 3－8 金山中学计算机竞赛班教程·数据结构 end; { 与相邻区不重色，染色结果进栈，继续对下 一区从1色进行试探} end; if j.> 4 then begin i:= i-1; j:=s[ i ]+1; end; { 变更栈顶区域的染色色数} end; end; end; 按图3_3所示地图执行上述算法时，栈的变化情况如图3_5所示。 7 6 5 4 4 3 3 2 2 2 S 1 1 4 2 2 1 2 1 图3_5 3 2 1 2 3 2 1 4 2 3 2 1 → 1 3 4 2 3 2 1 → 3 → 3 → 4 → 2 → 3 从关系矩阵R可以看出，当i = 6时，无论色数j＝1 , 2 , 3 , 4都产生与相邻区重色问题 （因与i = 6相邻的区是1，2，4，5区，从栈S可见这四个区色数分别1，2，3，4，四种色全部用完。6区再用四种色数之一，必然重色）。因此必须变更栈顶色数，而5区当前色数为“4”，也不存在除4以外的可染色色数，则需继续退栈，变更S[ 4 ]:=4，由此S[ 5 ]:=3，然而此时仍然6区与相邻区重色，再次退栈，将S[ 3 ]改为S[ 3 ]:=3时才求得所有地区的染色解。 §3.4 栈与递归 §3.4.1 递归形式一般有两种——直接递归和间接递归，而栈是实现递归的重要手段。 (一)、直接递归——子程序自己调用自己 【例2】 fac (n) = n! = 1 n=0 n×fac (n-1) n>1 按上述递归定义形式写出fac(n) 函数如下： function fac(n:integer):integer; begin if n=0 then fac:=1 else fac:=n*fac(n-1); end; 3－9 金山中学计算机竞赛班教程·数据结构 它的执行流程如下： fac (3) fac (2) fac (1) fac (0) fac (3) 6 fac (0) = 1 3×fac (2) 2×fac (1) 1×fac (0) 一般来说，递归子程序在调用本身前应有条件语句控制何时进行递归，何时递归结束。这个条件语句就是递归边界。例如，fac函数体中的“ if n=0 then fac:=1 ”。 (二)、间接递归——子程序A调用子程序B，子程序B又调用子程序A 子程序A和B组合起来有两种结构形式： 1．B是A的局部对象 例： procedure A; procedure B; begin A 的子过程 B ? 的过程说明 A; {在B中调用A} ? end begin ? B; {在A中调用B} ? end; 2．A和B是两个地位相同的子程序 例： procedure B (形式参数表): forward; {B的完整说明在后} procedurde A; begin ? B (实参表); {在A中调用B} end; procedure B; {B的首部缩写，形式参数表不再列出} begin ? A; {在B中调用A} ? end; 3－10
信息学竞赛班数据结构专项培训教程—— 03栈和队列
