问答题
在表达式中,有的运算符要求从右到左计算,如A**B**C的计算次序应为(A**(B**C)),这在由中缀生成后缀的算法中是怎样实现的?(以**为例说明)【东南大学1993一、2(6分)1997一、1(8分)】
【正确答案】正确答案:中缀表达式转为后缀表达式的规则基本上与上面21题相同,不同之处是对运算符料优先级的规定。在算术运算中,先乘除后加减,先括号内后括号外,相同级别的运算符按从左到右的规则运算。而对料运算符,其优先级同常规理解,即高于加减乘除而小于左括号。为了适应本题中“从右到左计算”的要求,规定栈顶运算符料的级别小于正从表达式中读出的运算符料,即刚读出的运算符料级别高于栈顶运算符料,因此也入栈。下面以A**B**C为例说明实现过程。读入A,不是操作符,直接写入结果表达式。再读入*,这里规定在读入*后,不能立即当乘号处理,要看下一个符号,若下个符号不是*,则前个*是乘号。这里因为下一个待读的符号也是*,故认为**是一个运算符,与运算符栈顶比较(运算符栈顶初始化后,首先压入‘#’作为开始标志),其级别高于‘#’,入栈。再读入B,直接进入结果表达式。接着读入料,与栈顶比较,均为料,我们规定,后读入的料级别高于栈顶的料,因此料入栈。接着读入C,直接到结果表达式。现在部分结果(后缀)表达式是ABC。最后读入"#",表示输入表达式结束,这时运算符栈中从栈顶到栈底有两个料和一个"#"。两个运算符料退栈至结果表达式,结果表达式变为ABC****。运算符栈中只剩’#’,退栈,运算结束。
【答案解析】