数据结构重读 – 表达式求值

例如对如下的表达式求值:

4+2*3-10/5,注意是有优先级顺序的。

我们首先定义算符优先关系如下表:

注意这个表和我们所掌握的算数定义不同,如+和-是的优先级关系不是同等。

其中,#为终止符。

接着,我们预定义两个辅助函数:

Precede(opr1, opr2),比较两个运算符opr1和opr2,如果opr1优先级大于opr2,返回’>’,小于返回'<‘,相等返回’=’。

 

我们使用两个栈模拟:OPTR存放寄存器运算符,OPND存放寄存器操作数。

算法流程如下:

(1)将#入栈
(2)依次读入表达式字符c。
当c!=’#’ || OPTR.top()!=’#’时,执行:
(3)如果c不是运算符(是运算数),直接入OPND栈。(这里的Bug是只支持10以内数字的运算,要修正这个要做其他小的修改)
(4)如果是运算符,另opr1=optr栈顶的运算符,opr2=c运算符。
(a)如果Precede(opr1, opr2) == ‘<‘,表示栈顶运算符优先级低,将优先级更高的c压入OPND,称为新栈顶(之后最优先计算的)。
(b)如果Precede(opr1, opr2) == ‘>’,表示栈顶运算符优先级高,则弹出OPND做为b,再弹出OPND做为a,再弹出OPTR做为opr,计算x = a OPTR b,结果压入栈OPND。
(c)如果Precede(opr1, opr2) == ‘=’,这种根据表格,只有括号匹配的情况,因此弹出OPTR表示消解括号即可。

到最后,最终结果应该保存在OPND中。

伪代码如下:

注意while的条件:c!=’#’ || OPTR.top()!=’#’,后面这个是当getchar都执行完,但OPTR栈中还有非终结#运算符时使用。

Leave a Reply

Your email address will not be published.