与/或表达式化简

王朝vc·作者佚名  2006-01-17
窄屏简体版  字體: |||超大  

与/或表达式化简

作者:袁国桃 (西安理工大学 计算机学院)

源代码下载

我在VCKBASE里面混了已有两年多的时间了。在这期间我看到了许多优秀了技术文档,我从中受益非浅。一直想为她写些什么,但总是感到心有余而力不足。现在我已经是大四学生,还有十几天就要离开校园了。在这大学的最后时刻,我决定为VCKBASE写些什么新鲜的东西来各大家分享一下。碰巧我在做毕业设计的时候,有个同学是做编译器的词法分析的,我在VCKBASE《在线杂志》第二十六期上也看到过ZF.Yi写的一篇关于表达式计算的文档《简单的表达式求值》,很值得我们学习。因此,我就决定写一篇类似的文档来和大家共同探讨和学习。

一、问题的提出

假如我们有如下所示的与/或表达式:

a*[b*[c+d]*e+f]+g

化简后要得到如下的表达式:

a*b*c*e+a*b*d*e+a*f+g

表达式中允许的字母和算符

{A-Z, a-z, [,],*,+}

其中“[,]”表示括号,允许嵌套;“*”表示逻辑运算符“与”;“+”表示逻辑运算符“或”;并且“*”的优先级高于“+”。

二、解决办法

在编译原理中,有一种自上而下分析方法LL(1),其核心算法就是“递归下降法”,其具体理论有兴趣的朋友可以参考一些编译原理书籍。首先让我们来看一个编译原理课本上用“递归下降法”进行“表达式的求值”的分析得到的产生式:

exp->exp addop term|term

addop->+|-

term->term mulop factor|factor

mulop->*

factor->(exp)|number

其中“exp”代表待求值的表达式;“addop”代表“+”和“-”运算符;“term”代表用“*”连接起来的表达式;“mulop”代表“*”;“factor”代表乘积因子,它可以是一个数,也可以是一个表达式。

按照这种思路,我得出了如下的对应于本文开头所提出问题的产生式:

exp->term { OR term }|term

OR->+

term->term AND factor|factor

AND->*

factor->[exp]|letter

letter->[A-Z]|[a-z]

去除左递归后如下所示:

exp->term { OR term }

OR->+

term->factor { AND factor }

factor->letter|[exp]

AND->*

letter->[A-Z]|[a-z]

这样,我们就很容易将其转化为代码。比如,将“exp->term { OR term }”这个表达式转化的伪代码如下:

CString exp()

{

CString temp = _T("");

try

{

temp = Term();

while( 当前还没有到输入串的末尾 && 下一个将要扫描的字符为OR )

{

temp += "+";

Match(OR);//字符匹配,用户判断将要扫描的字符是否为所期望的字符,并且推动扫描串的前进

temp += Term();

}

}

catch(CError& error)

{

throw error;

}

return temp;

}

其它的产生式对应的代码类似,具体细节就不叙述了,请大家参考参考源程序。

三、运行效果图

四、结束语

这是我第一次在VCKBASE上发表的文章,其中肯定存在许多不足之处,希望大家指出来批评指正

^-^。同时,我也感觉到深为一名学习计算机的学生,丰富的编程实际经验固然重要,但如果具有丰富的理论基础作为坚强后盾的话,那么我们在编写程序时就会游刃有余,才会感觉到写程序是一种真正的享受^-^。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航