与/或表达式化简

一、问题的提出

如果我们有如下所示的与/或表达式：

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上颁发的文章，个中必定存在很多不敷之处，但愿各人指出来品评指正

^-^。同时，我也感受到深为一名进修计较机的学生，富厚的编程实际履历当然重要，但假如具有富厚的理论基本作为坚定后援的话，那么我们在编写措施时就会游刃有余，才会感受到写措施是一种真正的享受^-^。

本文配套源码