现在的位置: 首页 > 综合 > 正文

c#实现科学计算器 设计篇之优先级表设计

2013年12月16日 ⁄ 综合 ⁄ 共 1124字 ⁄ 字号 评论关闭

为了引入优先级概念,我们首先来看一个简单的表达式,如下
#1+2*3#    (#用于开头和结尾,并作为表达式内容)
常识告诉我们,我们会先算2*3然后计算1+6,但实际上,如果直接从语法角度看,该表达式存在两种含义:
一种含义就是我们所认为的1+(2*3)
另一种含义则是(1+2)*3
这就是说表达式存在二义性,为了消除二义性,我们必须引入优先级概念。

我们来定义一种优先级运算,定义如下:
a<b        a的优先级低于b
a=b        a的优先级等于b
a>b        a的优先级大于b

使用时要注意,在这里aXb存在隐含意义,表明在表达式中,a出现在b之前,且相邻,例如表达式ab就是满足条件的。
对于运算符,我们需要注意一下相邻的概念,这里的相邻是指相对相邻,例如1+2*3中,+和*就是相邻的。
大家还要注意一点,该种运算不存在传递性,例如a<b,b<c不能推出a<c

目前的设计,实现了两种不同的优先级表,一种是相对相邻的优先级表,一种是绝对绝对的优先级表。
所谓相对相邻和绝对相邻(自己想出来的名字,如果大家有好的名字可以告诉我),举个例子大家就明白了:
#1+2*3#,+和*是相对相邻,这种相邻是运算符栈中的相邻位置,仅对于运算符有效,不包含数符(也就是数字)。
而1和+则是绝对相邻,这种相邻中包含运算符(operator)和数符(operand)。

相对相邻的优先级表既可以用于运算单元,也可以用于文法分析,而绝对相邻的优先级表仅用于文法分析。

为了帮助大家更好地理解优先级表的作用,我们来对一个简单的表达式作一次运算:
表达式:1*2+3#

步骤 运算符栈 数符栈 剩余表达式 当前输入 说明
1 # 1*2+3#    
2 # 1 *2+3# 1  
3 # * 1 2+3# * #<*,把*压入运算符栈
4 # * 1 2 +3# 2  
5 # * 1 2 3# + * > + ,对*进行运算,由于*是双目运算符,
从数符栈弹出两个数符,从运算符栈弹出*,
最后把运算结果压入数符栈
6 # + 2 3 # 3  
7 # + 2 3 # + > # ,对+进行运算,运算步骤同上,
8 # 5 结束,数符栈顶的数就是运算结果

要注意的是:对于算符优先算法,对于#的处理比较特别,一旦发现运算符栈顶是# ,而当前输入也是 # 时,马上结束循环。

由于显示原因,这里就不把该运算器的优先级表贴出来了,大家可以从这里下载优先级表的Excel文件和优先级表的c#实现(GrammerAnalyzer.Operator.cs)。 说明一下,Excel文件中的优先级是用U,1,2,3来表示的,U表示未知,1表示高于,2表示低于,3表示等于,左侧列表示前一个字符,顶行表示后一个字符,因此看起来应该先看左侧列再看顶行。

由于该表并未经过严格的验证,如果觉得优先级有问题还请指出。

抱歉!评论已关闭.