递归下降算法

递归下降算法

算法模型：

Term = Term + Expr

Expr=Expr+Factor

Factor =单个元素。最小单位。

实现原理：

一个程式进入算法及被看作是一个项，分解成项加表达式的形式，表达式被分解成 表达式加因子的形式，因子是这个算法中的最小单位。

上一级调用比自己小一级的自己。这里三层分离，越下层模型中所形成的优先级就会越高。

我用递归下降算法写了个简单的计算器，递归算法为我的运算符号+ – * / 等基础运算符号形成优先级。在使用的过程中发现了递归下降算法很容易产生的一个问题，左递归问题。接下来详细描述这个问题，以及解决方案。

什么叫左递归？

举个例子：1-2+1  正确答案应该是0，如果出现左递归答案将会是-2。

所谓的左递归其实就是算式在进行同等级运算符的运算的时候强行从右至左进行了运算解析，因为递归下降法中越是后生成的运算符其优先级越高，在同等级运算中，就无法确保优先级了，在这里的体现就是算式从右至左进行了解析。

简单点说，就是虽然是应该为相同优先级的东西，因为生成的先后顺序让它从右至左残生了优先级。

左递归很容易被忽略掉，不测试特定会出BUG的算式，这个BUG是不会出现的，整个程序看上去是在完美运行，毫无破绽。但是实际上整个算式的计算顺序都出现了问题。

解决左递归的方案：

解决左递归无非就是解决算式的解析方式，让算式从左自右解析，但是依然能正确的形成符号的优先级就好了。

物理模型图对比：

左递归的时候生成的Node：

算式1-2+4，越是后面生成的优先级就会高于前面生成的，所以左递归，会先计算2+4。从而导致错误。

解决方案：

将运算符号抽象出来单独成立一层，将数值节点统统存入Vector，这样的话，在实际生成到内存中需要判断优先级的只有+ – * / 四个了，因为递归下降算法，所以只要让 * /在+ –的下一级子类中生成，就可以确保他们的优先级是正确的。

物理模型如下：

这样就用编程的手法解决了符号的优先级问题，当然也可以通过算法的优化来解决这系列问题，哈哈~！我不会。。。。

在来说明下这个解决方案：

内存中只new出+ – * / 四个运算符号，NumberNode统统存入到Vector当中，在调用STL算法将NumberNode依次取出，计算就可以了。

思路是这个思路，实现代码以后更新。

今天的文章递归下降算法分享到此就结束了，感谢您的阅读。