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> を解析することです

そうしないでください :) 開き括弧が表示されたら、expression を再帰的に呼び出します。式の最後に、別の演算子を見つけるか (つまり、結局式の最後にいるわけではありません)、または右括弧を見つけます。この場合、評価から戻ります。

于 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

自分でそれを行う「ハッキーな」方法は、最初の)バックトラックを探して、間にある括弧のない式を最も(よく見て、単純に演算子記号で分割して評価することです。

于 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

式を中置ごとに減らすのではなく、中置入力を後置に変更してから評価することをお勧めします。これにはすでに明確に定義されたアルゴリズムがあり、固有の複数のネストされた括弧の解析問題はありません。

Shunting Yard Algorithmを見て、 postfix/RPN に変換し、 Postfix Operationsを使用してスタックを使用して評価します。これは高速 (O(n)) で信頼性があります。

HTH

于 2010-11-01T21:51:32.080 に答える
1

この古いが (私の意見では) コンパイラー設計に関する一連の関連記事で説明されているものに、よりよく似たアプローチを取ることをお勧めします。式の一部を解析する小さな関数/メソッドを使用するアプローチが非常に効果的であることがわかりました。

このアプローチにより、解析メソッドを多くのサブメソッドに分解できます。サブメソッドの名前と実行順序は、解析する式を記述するために使用する可能性があるEBNFに厳密に従います。

于 2010-11-01T21:15:38.900 に答える
-2

おそらく、式と演算子の正規表現を作成し、マッチングを使用してコンテンツを識別して分割します。

于 2010-11-01T21:23:37.010 に答える