10

我要写一个表达式求值器，它只做加法和减法。我有一个简单的算法来做到这一点；但是，我有一些实施问题。

我认为一个表达式（它是一个字符串）

"(" <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>来自表达式。我怎样才能做到这一点？

注意：我不是要代码。我所需要的只是一个想法。

谢谢，

-阿里

4

6 回答 6

7

我的问题是从表达式中解析 <expression1>、<operator> 和 <expression2>

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

于 2010-11-01T21:16:20.307 回答
3

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

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

自己做的一种“hacky”方法是寻找第一个)回溯到最接近(两者之间的括号自由表达式，只需拆分运算符符号并进行评估。

于 2010-11-01T21:16:36.420 回答
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;
}

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

于 2010-11-01T21:26:09.880 回答
3

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

看一下Shutting Yard Algorithm to convert to postfix/RPN 然后使用堆栈使用Postfix Operations对其进行评估。这是快速（O（n））且可靠的。

高温高压

于 2010-11-01T21:51:32.080 回答
1

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

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

于 2010-11-01T21:15:38.900 回答
-2

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

于 2010-11-01T21:23:37.010 回答