Java 递归数学表达式求值

Question

我有一个学校布置的问题让我很困惑。基本上，在类里面我们正在学习递归。作为家庭作业和相互递归的介绍，我们应该编写一个使用相互递归的数学表达式求值器。 getExpressionValue、getTermValue 和 getFactorValue 这三个方法需要相互调用才能获得结果。我们应该支持加法、减法、乘法、除法和带括号的表达式。在寻找如何做到这一点的想法时，我不断遇到递归下降解析，但我不确定这个想法是否适合这个问题。

如果有人可以为我提供指导或可能提供指向解释如何进行这样的解析的文章的链接，我将不胜感激。谢谢。

Answer 1

递归下降解析确实适用于此。 The Wikipedia article on the subject包含一个很好的 C 示例，它与您想要执行的操作非常相似。

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