第4章栈与队列 第4章栈和队列 4-1改写顺序栈的进栈成员函数Push(x),要求当栈满时执行一个 stackFull()操作进行栈满处理。其功能 是:动态创建一个比原来的栈数组大二倍的新数组,代替原来的栈数组,原来栈数组中的元素占据新数组 的前 MaxSize位置。 【解答】 template< class Type> void stack<Iype>:push( const Type&iem){ if( isFull ()stack 栈满,做溢出处理 ∥进栈 mplate<class Type> void stack<Type>: stack Full ()i Type*temp= new Type[3* maxSize I;m建体积大二倍的数组 for( int i=0; i<= top; i++) ∥传送原数组的数据 temp[= elements[]; delete ∥删去原数组 maxSize *=3 ∥数组最大体积增长二倍 elements =temp ∥新数组成为栈的数组空间 4-2铁路进行列车调度时,常把站台设计成栈式结构的站台,如右图所示。试问 (1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能 的出栈序列有多少种? 234 (2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641, 154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何 得到即写出"进栈"或"出栈"的序列) 【解答】 (1)可能的不同出栈序列有(1/(6+1)*C2=132种 (2)不能得到435612和154623这样的出栈序列。因为若在4,3,5,6之后再将1,2出栈,则1,2必须 直在栈中,此时1先进栈,2后进栈,2应压在1上面,不可能1先于2出栈。154623也是这种情况。 出栈序列325641和135426可以得到。 32 32 325 3256 2564 325641 13 1354 1354213542135426 4-3试证明:若借助栈可由输入序列1,2,3,…,n得到一个输出序列pi,p2,p3,…,pn(它是输入序列的某 种排列),则在输出序列中不可能出现以下情况,即存在i<j<k,使得p<p<p。(提示:用反证法)
第 4 章 栈与队列 36 (1/(6 1)) 132 6 + C12 = 第 4 章 栈和队列 4-1 改写顺序栈的进栈成员函数 Push (x )，要求当栈满时执行一个 stackFull ( )操作进行栈满处理。其功能 是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组 的前 MaxSize 位置。 【解答】template<class Type>void stack<Type> :: push ( const Type & item ) { if ( isFull ( ) ) stackFull ( ); //栈满，做溢出处理 elements [ ++top ] = item; //进栈 } template<class Type> void stack<Type> :: stackFull ( ) { Type * temp = new Type [ 3 * maxSize ]; //创建体积大二倍的数组 for ( int i = 0; i <= top; i++ ) //传送原数组的数据 temp[i] = elements[i]; delete [ ] elements; //删去原数组 maxSize *= 3; //数组最大体积增长二倍 elements = temp; //新数组成为栈的数组空间 } 4-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问： (1) 设有编号为 1,2,3,4,5,6 的六辆列车, 顺序开入栈式结构的站台, 则可能 的出栈序列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到 435612, 325641, 154623 和 135426 的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何 得到(即写出"进栈"或"出栈"的序列)。 【解答】 (1) 可能的不同出栈序列有 种。 (2) 不能得到 435612 和 154623 这样的出栈序列。因为若在 4, 3, 5, 6 之后再将 1, 2 出栈，则 1, 2 必须 一直在栈中，此时 1 先进栈，2 后进栈，2 应压在 1 上面，不可能 1 先于 2 出栈。154623 也是这种情况。 出栈序列 325641 和 135426 可以得到。 3 5 6 2 2 4 4 4 4 1 1 1 1 1 1 1 1 3 32 32 325 325 3256 32564 325641 5 3 4 4 1 2 2 2 2 6 1 1 13 135 1354 13542 13542 135426 4-3 试证明：若借助栈可由输入序列 1, 2, 3, …, n 得到一个输出序列 p1, p2, p3, …, pn (它是输入序列的某一 种排列)，则在输出序列中不可能出现以下情况，即存在 i < j < k，使得 pj < pk < pi。(提示：用反证法)
第4章栈与队列 【解答】 因为借助栈由输入序列1,2,3,…n,可得到输出序列pl,p,p,…,pa,如果存在下标i,jk,满足i< j<k,那么在输出序列中,可能出现如下5种情况: ①i进栈,i出栈,j进栈,j出栈,k进栈,k出栈。此时具有最小值的排在最前面p位置,具有中间 值的排在其后p位置,具有最大值的排在p位置,有p<p<pk,不可能出现p<pk<p的情形; ②i进栈,i出栈,j进栈,k进栈,k出栈,j出栈。此时具有最小值的排在最前面p;位置,具有最大 值的排在p位置,具有中间值的排在最后p位置,有p<pk<p,不可能出现p<pk<p的情形 ③i进栈,j进栈,j出栈,i出栈,k进栈,k出栈。此时具有中间值的排在最前面p位置,具有最小 值的排在其后p位置,有p<p<pk,不可能出现p<pk<p1的情形 ④i进栈,j进栈,j出栈,k进栈,k出栈,i出栈。此时具有中间值的排在最前面p位置,具有最大 值的排在其后p位置,具有最小值的排在p位置,有pk<p<p,也不可能出现p<pk<p的情形 ⑤i进栈,j进栈,k进栈,k出栈,j出栈,i出栈。此时具有最大值的排在最前面pi位置,具有中间 值的排在其后p位置,具有最小值的排在p位置,有p<p<p,也不可能出现p<pk<p的情形; 4-4将编号为0和1的两个栈存放于一个数组空间Ⅴm]中,栈底分别处于数组的两端。当第0号栈的栈顶 指针top0]等于-1时该栈为空,当第1号栈的栈顶指针top[l等于m时该栈为空。两个栈均从两端向中间 增长。当向第0号栈插入一个新元素时,使top0增1得到新的栈顶位置,当向第1号栈插入一个新元素 时,使top[1]减1得到新的栈顶位置。当top[O]+1==top[]时或topo]==top[l-1时,栈空间满,此时不 能再向任一栈加入新的元素。试定义这种双栈( Double stack)结构的类定义,并实现判栈空、判栈满、插入、 删除算法。 【解答】 top[o topl] bot[1] 双栈的类定义如下: #include <assert. h> template <class Type> class DblStack ∥双栈的类定义 nt top[2], bot[2]: ∥双栈的栈顶指针和栈底指针 Type *elements ∥栈数组 ∥栈最大可容纳元素个数 public: ∥始化双栈,总体积m的默认值为10 -DblStack (i delete elements; 3 ∥析构函数 void DblPush( const Type& x, int 1 ); ∥把ⅹ插入到栈i的栈顶 int DblPop(inti片; ∥退掉位于栈i栈顶的元素 Type* DblGetTop( int 1) ∥返回栈i栈顶元素的值 int IsEmpty(inti) const{ return top=bot;}/判栈i空否,空则返回1,否则返回0 int IsFull ()const i return top[0+1 p: ∥判栈满否,满则返回1,否则返回0 void Make Empty int 1 ) ∥清空栈i的内容 template <class Type> DblStack<Type> DblStack( int sz ): m(sz), top[o](-1), bot[o(-1), top[1I(sz), bot(l](sz)i ∥建立一个最大尺寸为sz的空栈,若分配不成功则错误处理
第 4 章 栈与队列 37 【解答】 因为借助栈由输入序列 1, 2, 3, …, n，可得到输出序列 p1, p2, p3, …, pn ，如果存在下标 i, j, k，满足 i < j < k，那么在输出序列中，可能出现如下 5 种情况： ① i 进栈，i 出栈，j 进栈，j 出栈，k 进栈，k 出栈。此时具有最小值的排在最前面 pi 位置，具有中间 值的排在其后 pj 位置，具有最大值的排在 pk 位置，有 pi < pj < pk, 不可能出现 pj < pk < pi 的情形； ② i 进栈，i 出栈，j 进栈，k 进栈，k 出栈，j 出栈。此时具有最小值的排在最前面 pi 位置，具有最大 值的排在 pj 位置，具有中间值的排在最后 pk 位置，有 pi < pk < pj , 不可能出现 pj < pk < pi 的情形； ③ i 进栈，j 进栈，j 出栈，i 出栈，k 进栈，k 出栈。此时具有中间值的排在最前面 pi 位置，具有最小 值的排在其后 pj 位置，有 pj < pi < pk, 不可能出现 pj < pk < pi 的情形； ④ i 进栈，j 进栈，j 出栈，k 进栈，k 出栈，i 出栈。此时具有中间值的排在最前面 pi 位置，具有最大 值的排在其后 pj 位置，具有最小值的排在 pk 位置，有 pk < pi < pj, 也不可能出现 pj < pk < pi 的情形； ⑤ i 进栈，j 进栈，k 进栈，k 出栈，j 出栈，i 出栈。此时具有最大值的排在最前面 pi 位置，具有中间 值的排在其后 pj 位置，具有最小值的排在 pk 位置，有 pk < pj < pi, 也不可能出现 pj < pk < pi 的情形； 4-4 将编号为 0 和 1 的两个栈存放于一个数组空间 V[m]中，栈底分别处于数组的两端。当第 0 号栈的栈顶 指针 top[0]等于-1 时该栈为空，当第 1 号栈的栈顶指针 top[1]等于 m 时该栈为空。两个栈均从两端向中间 增长。当向第 0 号栈插入一个新元素时，使 top[0]增 1 得到新的栈顶位置，当向第 1 号栈插入一个新元素 时，使 top[1]减 1 得到新的栈顶位置。当 top[0]+1 == top[1]时或 top[0] == top[1]-1 时，栈空间满，此时不 能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、 删除算法。 【解答】 双栈的类定义如下： #include <assert.h> template <class Type> class DblStack { //双栈的类定义 private: int top[2], bot[2]; //双栈的栈顶指针和栈底指针 Type *elements; //栈数组 int m; //栈最大可容纳元素个数 public: DblStack ( int sz =10 ); //初始化双栈, 总体积 m 的默认值为 10 ~DblStack ( ) { delete [ ] elements; } //析构函数 void DblPush ( const Type& x, int i ); //把 x 插入到栈 i 的栈顶 int DblPop ( int i ); //退掉位于栈 i 栈顶的元素 Type * DblGetTop ( int i ); //返回栈 i 栈顶元素的值 int IsEmpty ( int i ) const { return top[i] == bot[i]; } //判栈 i 空否, 空则返回 1, 否则返回 0 int IsFull ( ) const { return top[0]+1 == top[1]; } //判栈满否, 满则返回 1, 否则返回 0 void MakeEmpty ( int i ); //清空栈 i 的内容 } template <class Type> DblStack<Type> :: DblStack ( int sz ) : m(sz), top[0] (-1), bot[0](-1), top[1](sz), bot[1](sz) { //建立一个最大尺寸为 sz 的空栈, 若分配不成功则错误处理。 0 m-1 bot[0] top[0] top[1] bot[1]
第4章栈与队列 elements = new Type[m] ∥创建栈的数组空间 assert( elements =NULL 断言:动态存储分配成功与否 template <class Type> void DblStack<Type>:: DblPush( const Type& x, int i)i 如果 IsFull(),则报错:否则把x插入到栈i的栈顶 ssert(!sFull () ∥断言:栈满则出错处理,停止执行 if(i==0)elements[ ++top(O]=x 栈0情形:栈顶指针先加1,然后按此地址进栈 else elements[--top[=x; 栈1情形:栈顶指针先减1,然后按此地址进栈 plate <class Type> int DblStack<Typ bIPop( int 1)& 如果 IsEmpty(i),则不执行退栈,返回0:否则退掉位于栈i栈顶的元素,返回1 if( IsEmpty(i))return 0; ∥判栈空否,若栈空则函数返回0 if(i==0)top[o]-; ∥栈0情形:栈顶指针减1 lse top[ 1]++; 俄栈1情形:栈顶指针加1 return I template <class Type> Type* DblsStack<Type> DblGetTop( int i)( ∥若栈不空则函数返回该栈栈顶元素的地址。 if IsEmpty int i))return NULL ∥判栈i空否,若栈空则函数返回空指针 return& elements[ top ∥返回栈顶元素的值 template <class Type> void Make Empty int i)& if(i=0)top[0]=bot[0]=-1; else top[ 1]= bot[1]=m; 4-5写出下列中缀表达式的后缀形式: (1)A*B*C (2)-A+B-C+D (3)A*-B+C 4)(A+B)*D+E/(F+A*D)+C (5)A&&B||!(E>F)体注:按C+的优先级* (6)!(A&&!(B<C)|C>D))!C<E) 【解答】 (AB*C (3)AB-*C (4)AB+D*EFAD*+/+C+ (5)AB&&EF>! (6)ABC<CD>‖|!&&!CE<
第 4 章 栈与队列 38 elements = new Type[m]; //创建栈的数组空间 assert ( elements != NULL ); //断言: 动态存储分配成功与否 } template <class Type> void DblStack<Type> :: DblPush ( const Type& x, int i ) { //如果 IsFull ( )，则报错；否则把 x 插入到栈 i 的栈顶 assert ( !IsFull ( ) ); //断言: 栈满则出错处理，停止执行 if ( i == 0 ) elements[ ++top[0] ] = x; //栈 0 情形：栈顶指针先加 1, 然后按此地址进栈 else elements[--top[1] ] = x; //栈 1 情形：栈顶指针先减 1, 然后按此地址进栈 } template <class Type> int DblStack<Type> :: DblPop ( int i ) { //如果 IsEmpty ( i )，则不执行退栈，返回 0；否则退掉位于栈 i 栈顶的元素，返回 1 if ( IsEmpty ( i ) ) return 0; //判栈空否, 若栈空则函数返回 0 if ( i == 0 ) top[0]--; //栈 0 情形：栈顶指针减 1 else top[1]++; //栈 1 情形：栈顶指针加 1 return 1; } template <class Type> Type * DblStack<Type> :: DblGetTop ( int i ) { //若栈不空则函数返回该栈栈顶元素的地址。 if ( IsEmpty ( int i ) ) return NULL; //判栈 i 空否, 若栈空则函数返回空指针 return& elements[ top[i] ]; //返回栈顶元素的值 } template <class Type> void MakeEmpty ( int i ) { if ( i == 0 ) top[0] = bot[0] = -1; else top[1] = bot[1] = m; } 4-5 写出下列中缀表达式的后缀形式： (1) A * B * C (2) - A + B - C + D (3) A* - B + C (4) (A + B) * D + E / (F + A * D) + C (5) A && B|| ! (E > F) /*注：按 C++的优先级*/ (6) !(A && !( (B < C)||(C > D) ) )||(C < E) 【解答】 (1) A B * C * (2) A - B + C - D + (3) A B - * C + (4) A B + D * E F A D * + / + C + (5) A B && E F > ! || (6) A B C < C D > || ! && ! C E < ||
第4章栈与队列 4-6根据课文中给出的优先级,回答以下问题: (1)在函数 postfix中,如果表达式e含有n个运算符和分界符,问栈中最多可存入多少个元素? (2)如果表达式e含有n个运算符,且括号嵌套的最大深度为6层,问栈中最多可存入多少个元素? 【解答】 (1)在函数 postfix中,如果表达式e含有n个运算符和分界符,则可能的运算对象有n+1个。因此在 利用后缀表达式求值时所用到的运算对象栈中最多可存入n+1个元素。 (2)同上。 4-7设表达式的中缀表示为a*x-b/x↑2,试利用栈将它改为后缀表示ax*bx2↑/-。写出转换过程中栈 的变化。 【解答】 若设当前扫描到的运算符ch的优先级为icp(ch),该运算符进栈后的优先级为isp(ch),则可规定各个 算术运算符的优先级如下表所示。 运算符 isp也叫做栈内( (in stack priority)优先数,icp也叫做栈外( in coming priority)优先数。当刚扫描到的 运算符ch的icp(ch)大于isp( stack)时,则ch进栈;当刚扫描到的运算符ch的icp(ch)小于isp( stack)时 则位于栈顶的运算符退栈并输出。从表中可知,icp(“()最高,但当“(”进栈后,isp(“()变得极低。其它 运算符进入栈中后优先数都升1,这样可体现在中缀表达式中相同优先级的运算符自左向右计算的要求 运算符优先数相等的情况只出现在括号配对“)”或栈底的“;”号与输入流最后的“;”号配对时。前者将 连续退出位于栈顶的运算符,直到遇到“(”为止。然后将“(”退栈以对消括号,后者将结束算法 步序扫描项项类型 栈的变化 操作数直接输出、读下一符号 操作符「isp(;')<ip(*),进栈,读下一符号 操作数直接输出,读下一符号 操作符isp('*')>icp(-'),退栈输出 isp(";")<icp(-'),进栈,读下一符号 操作数 直接输出,读下一符号 操作符 ),进栈,读下一符号 操作符wisp(/')<icp(↑'),进栈,读下一符号;-/↑ axs bx 92操作数一直接输出,读下一符号 /↑ 橾作符wisp(↑')>icp(;),退栈输出 ax*bx2↑ 4-8试利用运算符优先数法,画出对如下中缀算术表达式求值时运算符栈和运算对象栈的变化 ↑f/ 【解答】 设在表达式计算时各运算符的优先规则如上一题所示。因为直接对中缀算术表达式求值时必须使用两 个栈,分别对运算符和运算对象进行处理,假设命名运算符栈为OPTR( operator的缩写),运算对象栈为
第 4 章 栈与队列 39 4-6 根据课文中给出的优先级，回答以下问题： (1) 在函数 postfix 中，如果表达式 e 含有 n 个运算符和分界符，问栈中最多可存入多少个元素？ (2) 如果表达式 e 含有 n 个运算符，且括号嵌套的最大深度为 6 层，问栈中最多可存入多少个元素？ 【解答】 (1) 在函数 postfix 中，如果表达式 e 含有 n 个运算符和分界符，则可能的运算对象有 n+1 个。因此在 利用后缀表达式求值时所用到的运算对象栈中最多可存入 n+1 个元素。 (2) 同上。 4-7 设表达式的中缀表示为 a * x - b / x↑2，试利用栈将它改为后缀表示 ax * bx2↑/ -。写出转换过程中栈 的变化。 【解答】 若设当前扫描到的运算符 ch 的优先级为 icp(ch)，该运算符进栈后的优先级为 isp(ch)，则可规定各个 算术运算符的优先级如下表所示。 运算符 ; ( ^ *,/, % +, - ) isp 0 1 7 5 3 8 icp 0 8 6 4 2 1 isp 也叫做栈内(in stack priority)优先数，icp 也叫做栈外(in coming priority)优先数。当刚扫描到的 运算符 ch 的 icp(ch)大于 isp(stack)时，则 ch 进栈；当刚扫描到的运算符 ch 的 icp(ch)小于 isp(stack)时， 则位于栈顶的运算符退栈并输出。从表中可知，icp(“(”)最高，但当“(”进栈后，isp(“(”)变得极低。其它 运算符进入栈中后优先数都升 1，这样可体现在中缀表达式中相同优先级的运算符自左向右计算的要求。 运算符优先数相等的情况只出现在括号配对“)”或栈底的“;”号与输入流最后的“;”号配对时。前者将 连续退出位于栈顶的运算符，直到遇到“(”为止。然后将“(”退栈以对消括号，后者将结束算法。 步序 扫描项 项类型 动 作 栈的变化 输 出 0 ';' 进栈, 读下一符号 ; 1 a 操作数 直接输出, 读下一符号 ; A 2 * 操作符 isp ( ' ; ' ) < icp ( ' * ' ), 进栈, 读下一符号 ; * A 3 x 操作数 直接输出, 读下一符号 ; * a x 4 - 操作符 isp ( ' * ' ) > icp ( ' - ' ), 退栈输出 ; a x * isp ( ' ; ' ) < icp ( ' - ' ), 进栈, 读下一符号 ; - a x * 5 b 操作数 直接输出, 读下一符号 ; - a x * b 6 / 操作符 isp ( ' - ' ) < icp ( '/' ), 进栈, 读下一符号 ; -/ a x * b 7 x 操作数 直接输出, 读下一符号 ; -/ a x * b x 8 ↑ 操作符 isp ( ' / ' ) < icp ( '↑' ), 进栈, 读下一符号 ; -/↑ a x * b x 9 2 操作数 直接输出, 读下一符号 ; -/↑ a x * b x 2 10 ; 操作符 isp ( '↑' ) > icp ( ' ; ' ), 退栈输出 ; -/ a x * b x 2↑ isp ( ' / ' ) > icp ( ' ; ' ), 退栈输出 ; - a x * b x 2↑/ isp ( ' - ' ) > icp ( ' ; ' ), 退栈输出 ; a x * b x 2↑/ - 结束 4-8 试利用运算符优先数法，画出对如下中缀算术表达式求值时运算符栈和运算对象栈的变化。 a + b * (c - d) - e↑f / g 【解答】 设在表达式计算时各运算符的优先规则如上一题所示。因为直接对中缀算术表达式求值时必须使用两 个栈，分别对运算符和运算对象进行处理，假设命名运算符栈为 OPTR (operator 的缩写)，运算对象栈为
第4章栈与队列 OPND(operand的缩写),下面给出对中缀表达式求值的一般规则 (1)建立并初始化OPIR栈和OPND栈,然后在OPTR栈中压入一个“;” (2)从头扫描中缀表达式,取一字符送入ch (3)当ch不等于“;”时,执行以下工作,否则结束算法。此时在OPND栈的栈顶得到运算结果 ①如果ch是运算对象,进OPND栈,从中缀表达式取下一字符送入ch: ②如果ch是运算符,比较ch的优先级icp(ch)和OPTR栈顶运算符isp(OPIR)的优先级 若icp(ch)>ip(OPIR),则ch进OPIR栈,从中缀表达式取下一字符送入ch 若icp(ch)<isp(OPIR,则从OPND栈退出一个运算符作为第2操作数a2,再退出一个运算符 作为第1操作数a1,从OPR栈退出一个运算符θ形成运算指令(a)0(a2),执行结果进OPND栈 若icp(ch)==isp(OPTR)且ch==“)”,则从OPIR栈退出栈顶的“(”,对消括号,然后从中缀表 达式取下一字符送入ch: 根据以上规则,给出计算a+b*(c-d)-e↑f/g时两个栈的变化。 步序扫描项项类型 OPND栈变化OPTR栈变化 OPIR栈与OPND栈初始化,“;进OPTR栈 取第一个符号 操作数 a进OPND栈,取下一符号 操作符 进OPIR栈,取下一符号 b操作数|∝b进OPND栈,取下一符 操作符一icp(*”)>isp(+'),进OPIR栈,取下一符号ab 操作符一 )>isp(“*”),进OPIR栈,取下一符号 进OPND栈,取下一符号 操作符|→ >sp(“(,进OPTR栈,取下一符号 进OPND栈,取下一符 )操作符-p()”)<ip(-”),退OPND栈d,退 OPND abs1 栈‘c,退OPIR栈‘-,计算c-d→st,结果进 OPND栈 10同上同上 ip()”)=psp((),退OPTR栈Y,对消括号,abs1 取下一符号 操作符ip(-)<ip(*”)退OPND栈‘s,退 OPND as2 栈“b',退OPTR栈‘*’,计算b*s1→s2,结果进 up(-”)<sp(+”),退OND栈s;,退OPND|s 栈‘a,退OPTR栈“+,计算a*s2→s3,结果 进OPND栈 同上同上|ip(-”)>sp(;”)进OPIR栈,取下一符号 e进OPND栈,取下 操作符一 ↑’)>is ),进OPTR栈,取下一符号 操作数一f进OPND栈,取下一符号 set 操作符|icp(/)<isp(↑”),退OPND栈f,退 OPNDs3s 栈‘e,退OPIR栈‘↑’,计算e↑f→s4,结果 进OPIR栈,取下一符号 OPND栈,取下一符号 20 操作符ip(;")<isp(/),退OPND栈'g,退OPND 栈‘s,退OPTR栈‘/,计算s4/g→s,结果 进OPND栈
第 4 章 栈与队列 40 OPND(operand 的缩写)，下面给出对中缀表达式求值的一般规则： (1) 建立并初始化 OPTR 栈和 OPND 栈，然后在 OPTR 栈中压入一个“;” (2) 从头扫描中缀表达式，取一字符送入 ch。 (3) 当 ch 不等于“;”时，执行以下工作，否则结束算法。此时在 OPND 栈的栈顶得到运算结果。 ① 如果 ch 是运算对象，进 OPND 栈，从中缀表达式取下一字符送入 ch； ② 如果 ch 是运算符，比较 ch 的优先级 icp(ch)和 OPTR 栈顶运算符 isp(OPTR)的优先级： 若 icp(ch) > isp(OPTR)，则 ch 进 OPTR 栈，从中缀表达式取下一字符送入 ch； 若 icp(ch) < isp(OPTR)，则从 OPND 栈退出一个运算符作为第 2 操作数 a2，再退出一个运算符 作为第 1 操作数 a1，从 OPTR 栈退出一个运算符θ形成运算指令 (a1)θ(a2)，执行结果进 OPND 栈； 若 icp(ch) == isp(OPTR) 且 ch == “)”，则从 OPTR 栈退出栈顶的“(”，对消括号，然后从中缀表 达式取下一字符送入 ch； 根据以上规则，给出计算 a + b * (c - d) - e↑f / g 时两个栈的变化。 步序 扫描项 项类型 动作 OPND 栈变化 OPTR 栈变化 0 OPTR 栈与 OPND 栈初始化, ‘;’ 进 OPTR 栈, 取第一个符号 ; 1 a 操作数 a 进 OPND 栈, 取下一符号 a ; 2 + 操作符 icp (‘ + ’ ) > isp (‘ ; ’ ), 进 OPTR 栈, 取下一符号 a ; + 3 b 操作数 b 进 OPND 栈, 取下一符号 a b ; + 4 * 操作符 icp (‘ * ’ ) > isp (‘ + ’ ), 进 OPTR 栈, 取下一符号 a b ; + * 5 ( 操作符 icp (‘ ( ’ ) > isp (‘ * ’ ), 进 OPTR 栈, 取下一符号 a b ; + * ( 6 c 操作数 c 进 OPND 栈, 取下一符号 a b c ; + * ( 7 - 操作符 icp (‘ - ’ ) > isp (‘ ( ’ ), 进 OPTR 栈, 取下一符号 a b ; + * ( - 8 d 操作数 d 进 OPND 栈, 取下一符号 a b c d ; + * ( - 9 ) 操作符 icp (‘ ) ’ ) < isp (‘ - ’ ), 退 OPND 栈 ‘d’, 退 OPND 栈 ‘c’, 退 OPTR 栈 ‘-’, 计算 c – d → s1, 结果进 OPND 栈 a b s1 ; + * ( 10 同上 同上 icp (‘ ) ’ ) == isp (‘ ( ’ ), 退 OPTR 栈‘(’, 对消括号, 取下一符号 a b s1 ; + * 11 - 操作符 icp (‘ - ’ ) < isp (‘ * ’ ), 退 OPND 栈 ‘s1’, 退 OPND 栈 ‘b’, 退 OPTR 栈 ‘*’, 计算 b * s1 → s2, 结果进 OPND 栈 a s2 ; + 12 同上 同上 icp (‘ - ’ ) < isp (‘ + ’ ), 退 OPND 栈 ‘s2’, 退 OPND 栈 ‘a’, 退 OPTR 栈 ‘+’, 计算 a * s2 → s3, 结果 进 OPND 栈 s3 ; 13 同上 同上 icp (‘ - ’ ) > isp (‘ ; ’ ), 进 OPTR 栈, 取下一符号 s3 ; - 14 e 操作数 e 进 OPND 栈, 取下一符号 s3 e ; - 15 ↑ 操作符 icp (‘↑’ ) > isp (‘ - ’ ), 进 OPTR 栈, 取下一符号 s3 e ; -↑ 16 f 操作数 f 进 OPND 栈, 取下一符号 s3 e f ; -↑ 17 / 操作符 icp (‘ / ’ ) < isp (‘↑’ ), 退 OPND 栈 ‘f’, 退 OPND 栈 ‘e’, 退 OPTR 栈 ‘↑’, 计算 e↑f → s4, 结果 进 OPND 栈 s3 s4 ; - 18 同上 同上 icp (‘ / ’ ) > isp (‘ - ’ ), 进 OPTR 栈, 取下一符号 s3 s4 ; - / 19 g 操作数 g 进 OPND 栈, 取下一符号 s3 s4 g ; - / 20 ; 操作符 icp (‘ ; ’ ) < isp (‘ / ’ ), 退 OPND 栈 ‘g’, 退 OPND 栈 ‘s4’, 退 OPTR 栈 ‘/’, 计算 s4 / g → s5, 结果 进 OPND 栈 s3 s5 ; -