3

実行時にifステートメントを受け取ることができる関数を作成する必要があります（たとえば、ユーザー入力、またはデータファイルから）。理想的には、次の式と同じくらい複雑な式を解くことができるはずです。

a && ( b || !c || ( d && e ) )

必要なのは再帰関数（自分自身を呼び出す関数）だと思います。もちろん、関数はtrueまたはfalseを返す必要があります。

上記の例は複雑であるため、関数は個々の条件をループするだけでなく、演算子を理解し、それらを評価する順序を理解し、できれば速度の優先順位を付ける必要があります（たとえば、falseの場合、ステートメントの残りの部分を評価する必要はありません）。

誰かアイデアはありますか？

4

1 に答える 1

3

1 つの解決策は、分流場アルゴリズムを使用して式を RPN に変換し、それを RPN として評価することです (RPN は infix よりも評価がはるかに簡単であるため)。最初の部分、RPN への変換 (疑似コード):

while (tokens left) {
  t = read_token();
  if (t is number) {
    output(t);
  } else if (t is unary operator) {
    push(t);
  } else if (t is binary operator) {
    r = pop();
    if (r is operator and precedence(t)<=precedence(r)) {
       output(r);
    } else {
       push(r);
    }
    push(t);
  } else if (t is left parenthesis) {
    push(t);
  } else if (r is right parenthesis) {
    while ((r = pop()) is not left parenthesis) {
        output(r);
        if (stack is empty) {
          mismatched parenthesis!
        }
    }
    if (top() is unary operator) {
        output(pop());
    }
  }
}
while (stack is not empty) {
  if (top() is parenthesis) {
     mismatched parenthesis!
  }
  output(pop());
}
  • read_token入力キューからトークンを読み取ります
  • output出力キューに値を挿入します
  • push値をスタックにプッシュします (必要なのは 1 つだけです)。
  • popスタックから値をポップします
  • topポップせずにスタックの一番上にある値をピークします

RPN 評価はより単純です。

while (tokens left) {
  t = read_token();
  if (t is number) {
    push(t);
  } else if (t is unary operator) {
    push(eval(t, pop()));
  } else if (t is binary operator) {
    val1 = pop();
    val2 = pop();
    push(eval(t, val1, val2));
  }
}
result = pop();
  • read_token()前のステップで生成された RPN キューから値を読み取ります
  • eval(t, val)tオペランドで単項演算子を評価しますval
  • eval(t, val1, val2)tオペランドを持つ二項演算子を評価しval1、val2
  • result式の最終値です

この単純化されたアルゴリズムは、すべての演算子が左結合で、関数が使用されていない場合に機能するはずです。独自のスタック実装を使用しているため、再帰は必要ありません。例と詳細については、Shunting-yardの Rosetta Code およびRPNの Rosetta Code を参照してください。

于 2012-06-27T11:40:38.627 に答える