使用Java的递归表达式求值器

Question

我打算编写一个只执行加法和减法的表达式求值器，我有一个简单的算法可以实现这个功能；但是，我遇到了一些实现问题。

我把表达式看作一个字符串。

"(" <expression1> <operator> <expression2> ")"

这是我的算法

String evaluate( String expression )

   if expression is digit
      return expression

   else if expression is "(" <expression1> <operator> <expression2> ")"
      cut the brackets out of it
      expression1 = evaluate( <expression1> )
      operator = <operator>
      expression2 = evaluate( <expression2> )

   if operator is +
      expression1 + expression2

   else if operator is -
      expression1 - expression2 

我的问题是从表达式中解析出<expression1>、<operator>和<expression2>。我该如何做？

注意：我不是在寻求代码，我只需要思路。

谢谢，

- Ali

- 629

---

如果您对使用这种方式编写的小型Java数学求值器的工作示例感兴趣，我在我的网站上有一个：http://www.softwaremonkey.org/Code/MathEval - Lawrence Dol

Answer 1

我的问题是从表达式中解析出<expression1>, <operator>和<expression2>。不要这样做，当你看到一个左括号时，递归调用表达式。在表达式的结尾，你会发现另一个运算符（因此你并没有到达表达式的结尾），或者一个右括号，在这种情况下，你将从求值中返回。

- The Archetypal Paul

---

嗯，要对表达式1进行递归调用，他基本上需要计算括号以确定表达式1的结束位置，但除此之外，我喜欢你的答案。 - aioobe

不完全是。递归为您进行计数。如果您在表达式可能结束的位置遇到“)”，那么这就是该递归调用的结尾。这就是递归下降解析器的工作原理... - The Archetypal Paul

啊，所以即使字符串不平衡，您还是对其尾进行递归调用？ - aioobe

我认为是这样，如果我理解你的意思正确的话。如果你看到一个（，你就会递归。要么你到达了输入的末尾（在这种情况下，出现错误），要么你看到了平衡的）并从这个递归中返回。如果你在返回到顶层后看到一个），那也是一个错误。这就是（递归下降）解析器生成器将产生的内容，但自己实现一个解析器也是很有教育意义的。事实上，这就是它们被称为递归下降的原因！ - The Archetypal Paul

你不必做任何额外的工作。你的term()、factor()和prime()方法只需要在下一个标记不是它们可以处理的内容时返回即可。因此，当expression()由于'('而返回到调用它的代码中时，下一个标记应该是')'。如果不是，则表示缺失。 - user207421

Answer 2

您可以使用解析器生成器，例如JavaCUP或ANTLR。编写表达式的BNF并生成解析器。以下是一个示例语法，可帮助您入门：

Expression ::= Digit
            |  LeftBracket Expression Plus Expression RightBracket
            |  LeftBracket Expression Minus Expression RightBracket
            |  LeftBracket Expression RightBracket

一种“不够优雅”的自己完成的方法是寻找第一个)，回溯到最近的(，查看两者之间没有括号的表达式，然后只需在操作符符号上分割并计算。

- aioobe

---

我认为你在语法中漏掉了“Number”。 - clstrfsck

这是一个含糊不清的语法，因为括号不是必需的。 - Josh Lee

好的观点。而且，原帖似乎需要括号，所以我加上了 :-) - aioobe

Answer 3

使用StringTokenizer将您的输入字符串拆分为括号、运算符和数字，然后遍历您的标记，在每个开括号处进行递归调用，并在每个闭括号处退出方法。

我知道您没有要求代码，但对于有效的输入，以下代码可以工作：

public static int eval(String expr) {
    StringTokenizer st = new StringTokenizer(expr, "()+- ", true);
    return eval(st);
}

private static int eval(StringTokenizer st) {
    int result = 0;
    String tok;
    boolean addition = true;
    while ((tok = getNextToken(st)) != null) {
        if (")".equals(tok))
            return result;
        else if ("(".equals(tok))
            result = eval(st);
        else if ("+".equals(tok))
            addition = true;
        else if ("-".equals(tok))
            addition = false;
        else if (addition)
            result += Integer.parseInt(tok);
        else
            result -= Integer.parseInt(tok);
    }
    return result;
}

private static String getNextToken(StringTokenizer st) {
    while (st.hasMoreTokens()) {
        String tok = st.nextToken().trim();
        if (tok.length() > 0)
            return tok;
    }
    return null;
}

需要更好地处理无效输入，但你已经明白了思路...

- Luke Hutteman

---

我不明白为什么你使用了getNextToken()而不是使用nextToken()？ - 629

它不能正确处理括号或运算符优先级，除非您引入递归或操作数堆栈，否则它永远无法解决这个问题。 - user207421

括号被正确处理，由于加法和减法（唯一需要的两个操作）具有相同的优先级，因此不需要添加任何额外的逻辑。如果您想要乘法和除法，那么是的，您需要一个操作数栈。 - Luke Hutteman

@ECP：我错了 - 我看到你关于括号处理的问题是正确的；我的不必要的递归调用对简单的加减法有所影响...这就是我试图在5分钟内拼凑代码的结果:p 我修复了代码以消除这种不必要的递归。 - Luke Hutteman

@alicozgo getNextToken() 用于跳过空格，不过回想起来 eval() 本身也可以忽略它。而且你说得对，这本质上是 Paul 建议的相同解决方案。 - Luke Hutteman

Answer 4

我建议将中缀输入转换为后缀，然后进行评估，而不是逐个降低表达式的中缀方式。已经有了这方面的明确定义算法，而且不会出现内在的多重嵌套括号解析问题。

请查看Shunting Yard Algorithm以将其转换为后缀/RPN，然后使用Postfix Operations使用堆栈进行评估。这很快（O(n)）和可靠。

希望对你有所帮助。

- Callum Rogers

---

这个很简单和直接。+1。 - Dr. belisarius

Answer 5

我建议采用更接近this编译器设计相关的一系列旧但（在我看来）仍然有价值的文章所描述的方法。我发现使用解析表达式部分的小函数/方法的方法非常有效。

这种方法允许您将解析方法分解为许多子方法，其名称和执行顺序紧密遵循您可能用于描述要解析的表达式的EBNF。

- Martin Törnwall

Answer 6

或许可以为表达式和运算符创建正则表达式，然后使用匹配来识别和分解您的内容。

- jarmod

---

您无法为 expression 创建正则表达式，因为它涉及到平衡的括号。 - aioobe

这不是一种常规语言，它是上下文无关的，因此不能通过正则表达式进行解析。 - Callum Rogers