![](https://csdnimg.cn/release/download_crawler_static/86355719/bg5.jpg)
【解答】
(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-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 ( ' ; ' ) < icp ( ' * ' ), 进栈, 读下一符号
isp ( ' * ' ) > icp ( ' - ' ), 退栈输出
isp ( ' ; ' ) < icp ( ' - ' ), 进栈, 读下一符号
isp ( ' - ' ) < icp ( '/' ), 进栈, 读下一符号
isp ( ' / ' ) < icp ( '↑' ), 进栈, 读下一符号