<b>与/或表达式化简</b>[VC/C++编程]

1、问题的提出

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

a*[b*[c+d]*e+f]+g化简后要得到以下的表达式:

a*b*c*e+a*b*d*e+a*f+g表达式中答应的字母和算符

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

此中“[,]”表示括号,答应嵌套;“*”表示逻辑运算符“与”;“+”表示逻辑运算符“或”;并且“*”的优先级高于“+”.

2、办理办法

在编译原理中,有一种自上而下解析办法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;
}

别的的产生式对应的代码近似,具体细节就不论述了,请大家参考参考源程序.

3、运行效果图

4、完毕语

这是我第一次在VCKBASE上发表的文章,此中必定存在很多不足之处,但愿大家指出来批判指正

^-^.同时,我也感遭到深为一名学习计算机的学生,丰富的编程实际经验当然重要,但假如具有丰富的理论底子作为刚强后盾的话,那么我们在编写程序时就会游刃有余,才会感遭到写程序是一种真正的享用^-^.

本文配套源码