内容简介：今天要给我们的“计算器”加上乘、除和取模三种运算，并且加上对括号的优先级处理。如果不是采用递归方式解析表达式的话，可以参考下用递归方式解析的话，只要深刻理解了上一章的知识，这一章的都是小意思，那么我们开始。
今天要给我们的“计算器”加上乘、除和取模三种运算，并且加上对括号的优先级处理。
如果不是采用递归方式解析表达式的话，可以参考下 调度场算法 ，这是一个利用队列和堆栈来解决计算优先级的经典算法。
用递归方式解析的话，只要深刻理解了上一章的知识，这一章的都是小意思，那么我们开始。
产生式的优先级
首先我们列出乘除法的文法：
term -> term '*' num | term '/' num | num num -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
这里的 term 是项的意思，是指在加减法里运算符左右的两个项，先不要纠结具体是什么意思，一会就会用到了。
我们以几个例子来人肉分析一下，这个文法和加减法的文法怎么结合，才能获得正确的优先级：
expr(1+2*3) = num(1) '+' term(2*3) expr(1*2+3) = term(1*2) '+' num(3) expr(1*2+3*4) = term(1*2) '+' term(3*4)
而在上面乘除法的文法里可以看到，实际上 term 是可以推导为 num 的，所以上述例子又可以变成：
expr(1+2*3) = term(1) '+' term(2*3) expr(1*2+3) = term(1*2) '+' term(3) expr(1*2+3*4) = term(1*2) '+' term(3*4)
是不是写到这里就豁然开朗了，如果乘除法的优先级更高，则让乘除法的解析先进行，乘除法的结果当做加减法的项就可以了。在文法里的表现就是，优先级越高的产生式会越靠后，结果是这样：
expr -> expr '+' term | expr '-' term | term term -> term '*' num | term '/' num | num num -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
具体的验证大家自己试试就可以了，绝对可以按照正确的优先级进行解析。
前一章代码的隐患
文法已经准备好了，本来可以开始写递归逻辑了，但是我们得先解决前一章代码的隐患。先看看之前的代码：
int expr(const char *expStr)
{
解析number，读取expStr下一个字符
while(expStr是加减号) {
解析加减号，读取expStr下一个字符
解析number，读取expStr下一个字符
}
}
看上去逻辑是没什么问题的，但是这是因为 number 肯定是单个字符的，如果按照之前的代码继续实现本章的文法，就会得到这样的难题：
int expr(const char *expStr)
{
解析term，该读取expStr后的第几个字符？
while(expStr是加减号) {
解析加减号，读取expStr下一个字符
解析term，该读取expStr后的第几个字符？
}
}
所以将字符串指针后移的操作，应该交给解析了字符或者说消化掉字符的角色来做，那么我们要用指针的指针来先改进一下上一章的代码：
int number(const char **expStr)
{
int result = **expStr - '0';
(*expStr)++;
return result;
}
int expr(const char **expStr)
{
int result = number(expStr);
while (**expStr == '+' || **expStr == '-') {
char op = **expStr;
(*expStr)++;
if (op == '+') {
result += number(expStr);
} else {
result -= number(expStr);
}
}
return result;
}
实现乘除法和取余
大家有了文法，也掌握了消除左递归的方法，还知道怎么转换成递归代码，我感觉其实都不太需要把代码给大家贴出来了。:joy:
乘除法的实现思路和上一章加减法的思路完全一致，我们顺带把取余也加上就好了：
int term(const char **expStr)
{
int result = number(expStr);
while (**expStr == '*' || **expStr == '/' || **expStr == '%') {
char op = **expStr;
(*expStr)++;
if (op == '*') {
result *= number(expStr);
} else if (op == '/') {
result /= number(expStr);
} else {
result %= number(expStr);
}
}
return result;
}
下一步就是把加减法里的 number 解析都换成 term 解析，换完之后的 expr 函数会长这样：
int expr(const char **expStr)
{
int result = term(expStr);
while (**expStr == '+' || **expStr == '-') {
char op = **expStr;
(*expStr)++;
if (op == '+') {
result += term(expStr);
} else {
result -= term(expStr);
}
}
return result;
}
实验下，确认我们的表达式解析器可以按照正确的优先级计算加减乘除了。
加入括号的处理
括号的运算优先级是比乘除法还要高的，所以我们新增一个非终结符 factor （因子），用来在文法中描述它：
expr -> expr '+' term | expr '-' term | term
term -> term '*' factor | term '/' factor | factor
factor -> number | '(' expr ')'
number -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
嘿嘿，这次就真的不给大家贴代码了，相信这次大家应该可以熟练的搞定代码，毕竟已经是个成熟的程序猿了。
完整的代码存放在 SlimeExpressionC ，需要的同学可以自取，今天的入门课就到这里。
其它章节
（二）递归解析中怎么处理运算符优先级
（三）简单错误处理逻辑以及负数的解析
（四）用词法解析处理多位数字和空白符
（五）解析ID型词法和函数调用语法
（六）用函数表来优化函数解析的逻辑
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- JavaScript阴沟里翻船之运算符优先级
- C/C++三元运算符实际上是否具有与赋值运算符相同的优先级？
- 如何确定需求的优先级？
- RabbitMQ之优先级消息队列
- [译]HTTP/2的优先级
- Thymeleaf 模板布局和属性优先级
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
