Java递归数学表达式求值

Question

我有一个学校布置的问题，让我感到困惑。基本上，在课堂上我们正在学习递归。作为作业和互递归简介，我们应该编写使用互递归的数学表达式求值器。 getExpressionValue，getTermValue和getFactorValue这三个方法需要相互调用以获得结果。我们应该支持加法，减法，乘法，除法和括号表达式。在寻找如何解决这个问题的思路时，我一直在遇到递归下降解析，但我不确定这个想法是否适用于此问题。

如果有人能为我提供指导或可能解释如何进行此类解析的文章链接，我将非常感激。谢谢。

- Michael Smith

---

要理解递归，你必须先理解递归。 - Mike Christensen

你是不是想说“递归”？(http://www.google.com.ng/search?hl=en&sa=X&ei=zBOTTvuND5KGhQe43bj5Dw&ved=0CCEQBSgA&q=recursion&spell=1) - Mob

@Mob 那些疯狂的谷歌小子真是太有趣了。 - Waylon Flinn

Answer 1

递归下降分析确实适用于此。维基百科关于该主题的文章中包含了一个很好的C语言示例，与您想要做的非常相似。

基本思路是：假设您得到的文本是有效的表达式，则它必须以左括号或数字开头。因此，通过查看第一个字符，您就知道它是否为带括号的表达式。如果不是，则该文本必须是由一个或多个用+或-分隔的项组成的序列。因此，您开始将文本开头视为一项。什么是项？它是由一个或多个用*或/分隔的因子组成的序列。因此，您开始将文本开头视为一个因子。什么是因子？它可以是数字或带括号的表达式，通过查看第一个字符，您可以确定它是什么。如果是数字，则消耗所有后续数字，以便找出数字是多少。现在，试图确定因子值的方法可以将此数字返回给试图确定项值的方法。这种方法现在知道第一个数字是什么，并且可以检查下一个字符以查看它是*还是/（编辑：它也可能是右括号、+或-，这意味着该项只由一个数字组成），然后要求提取下一个因子，以此类推。

- Aasmund Eldhuset

---

希望你的教练已经讲解了递归下降解析，并且也可能在你的书中有相关内容。;-> - Jeff Grigg

@Jeff 实际上，完全不是这样。我们也不使用书籍。有点奇怪。 - Michael Smith

Answer 2

这里的基本思想是数学表达式的各个部分只是更小的数学表达式。您可以开发一个函数（或一组函数），将表达式分解为较小的子表达式，并将这些子表达式传递给自身进行进一步处理。您可以一直这样做，直到将它们全部分解成基本元素（在这种情况下，即数字本身）。此时，您评估基本表达式并返回结果。值通过调用链向上渗透以产生链顶的整个表达式的值。

递归看起来像这样：

double getValue(expression){

    if(expression.isBasic)
        return expression.LHS + expression.RHS 
    else
        return getValue(expression.LHS) + getValue(expression.RHS)
}

你问题的转折在于，不是一个函数调用自身，而是可能有4或5个函数相互调用。哪个函数被调用将取决于您当前在表达式中处理的操作：加法、乘法、除法等。

- Waylon Flinn