使用 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 

我的问题是解析 、 和 来自表达式。我怎样才能做到这一点？

注意：我不是要求代码。我所需要的只是一个想法来做到这一点。

Answer 1

我的问题是解析<表达式1>，
<运算符> <表达式2>从
表达方式

那么不要这样做:) 当您看到左括号时，请对表达式进行递归调用。在表达式的末尾，您要么找到另一个运算符（因此您毕竟不在表达式的末尾），要么找到右括号，在这种情况下，您从评估中返回。

Answer 2

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

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

自己执行此操作的“hacky”方法是查找第一个 ) 回溯到最接近的 ( 查看之间的括号自由表达，只需拆分运算符符号并求值即可。

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;
}

它需要更好地处理无效输入，但您明白了...

Answer 4

我建议将中缀输入更改为后缀，然后对其进行评估，而不是逐个减少中缀表达式。已经有明确定义的算法，并且它不存在固有的多重嵌套括号解析问题。

查看 Shunting Yard Algorithm 以转换为 postfix/RPN，然后使用使用 Postfix 操作 的堆栈。这是快速 (O(n)) 且可靠的。

Answer 5

我建议采取一种更类似于this中描述的方法，但（在我看来）有关编译器设计的相关系列文章。我发现使用小函数/方法来解析部分表达式的方法非常有效。

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

Answer 6

也许为表达式和<创建正则表达式 em>operator，然后使用匹配来识别和分解您的内容。