数据结构 | 每日一练（96）

数据结构

1

每日一练

1.在表达式中，有的运算符要求从右到左计算，如 A**B**C 的计算次序应为(A**(B**C))，这在由中缀生成后缀的算法中是怎样实现的?(以**为例说明)

正确答案

PS：||代表注释

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

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

读入A，不是操作符，直接写入结果表达式。再读入*，这里规定在读入*后，不能立即当乘号处理，要看下一个符号，若下个符号不是*，则前个*是乘号。这里因为下一个待读的符号也是*，故认为**是一个运算符，与运算符栈顶比较（运算符栈顶初始化后，首先压入‘#’作为开始标志），其级别高于‘#’，入栈。再读入B，直

接进入结果表达式。接着读入**，与栈顶比较，均为**，我们规定，后读入的**级别高于栈顶的**，因此**入栈。接着读入C，直接到结果表达式。现在的结果（后缀）表达式是ABC。最后读入‘#’，表示输入表达式结束，这时运算符栈中从栈顶到栈底有两个**和一个‘#’。两个运算符**退栈至结果表达式，结果表达式变为ABC****。运算符栈中只剩‘#’，退栈，运算结束。