数据结构考研分类复习真题 第三章 答案[9]

中缀表达式转为后缀表达式的规则基本上与上面题相同不同之处是对运算符**优先级的规定在算术运算中先乘除后加减先括号内后括号外相同级别的运算符按从左到右的规则运算而对**运算符其优先级同常规理解即高于加减乘除而小于左括号为了适应本题中从右到左计算的要求规定栈顶运算符**的级别小于正从表达式中读出的运算符**即刚读出的运算符**级别高于栈顶运算符**因此也入栈

下面以A**B**C为例说明实现过程

读入A不是操作符直接写入结果表达式再读入*这里规定在读入*后不能立即当乘号处理要看下一个符号若下个符号不是*则前个*是乘号这里因为下一个待读的符号也是*故认为**是一个运算符与运算符栈顶比较（运算符栈顶初始化后首先压入#作为开始标志）其级别高于#入栈再读入B直接进入结果表达式接着读入**与栈顶比较均为**我们规定后读入的**级别高于栈顶的**因此**入栈接着读入C直接到结果表达式现在的结果（后缀）表达式是ABC最后读入#表示输入表达式结束这时运算符栈中从栈顶到栈底有两个**和一个#两个运算符**退栈至结果表达式结果表达式变为ABC****运算符栈中只剩#退栈运算结束

（）sum=当x为局部变量时每次递归调用都要给局部变量分配存储单元故x数值和均保留其递归过程示意图如下

() sum=当x为全局变量时在程序的整个执行期间x只占一个存储单元先后读入的个数()仅最后一个起作用当递归调用结束逐层返回时sum:=sum(n)+x表达式中x就是所以结果为sum=

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []