8

Java で分流ヤード アルゴリズムを正常に実装しました。アルゴリズム自体は単純でしたが、トークナイザーに問題があります。現在、アルゴリズムは、1 つのことを除いて、私が望むすべてのもので動作します。減算 (-) と負 (-) の違いをどのように見分けることができますか?

4-3 などは引き算ですが、-4+3 はマイナスです

いつマイナスになるべきか、いつマイナスになるべきかを知る方法はわかりましたが、たとえば関数のように使用すると常に機能するとは限らないため、アルゴリズムのどこに配置する必要がありますか

3 + 4 * 2 / -( 1 − 5 ) ^ 2 ^ 3

1-5 が -4 になると、2 乗して 3 乗する前に 4 になります。

3 + 4 * 2 / cos( 1 − 5 ) ^ 2 ^ 3 と同じように、2 乗と 3 乗の前に余弦を取ります。

しかし、実際の数学では、正しい値を得るために、実際に言っているのは 3 + 4 * 2 / -(( 1 − 5 ) ^ 2 ^ 3) であるため、- は使用しません。

4

5 に答える 5

9

lex-then-parse スタイルのパーサーを実行しているように聞こえます。単項およびバイナリ マイナスの個別のトークンを取得するために、lexer に単純なステート マシンが必要になります。(PEG パーサーでは、これは気にする必要はありません。)

JavaCC では、文字が であるDEFAULTと見なす状態があります。一次式の終わりをトークン化すると (例に基づいて、閉じ括弧または整数のいずれか)、が と見なされる状態に切り替わります。中置演算子に遭遇すると、状態に戻ります。-UNARY_MINUSINFIX-INFIX_MINUSDEFAULT

自分で巻く場合は、それよりも少し簡単かもしれません。これを行う巧妙な方法については、このPython コードを参照してください。基本的に、 に遭遇する-と、前のトークンが中置演算子であったかどうかを確認するだけです。この例では"-u"、非公式のトークン化に便利な単項マイナス トークンを表す文字列を使用しています。私が知る限り、Python の例では、a-が開き括弧の後に続く場合、または入力の先頭に来る場合を処理できません。それらも単項と見なされるべきです。

分流場アルゴリズム自体で単項マイナスを正しく処理するには、どの中置演算子よりも優先順位を高くする必要があり、右結合としてマークする必要があります。(右結合を処理することを確認してください。残りの演算子は左結合であるため、省略している可能性があります。) これは Python コードで十分に明確です (ただし、2 つの別個のマップではなく、ある種の構造体を使用します)。 .

評価するときは、単項演算子を少し異なる方法で処理する必要があります。これは、スタックから 2 つではなく 1 つの数値をポップするだけでよいためです。実装がどのように見えるかによっては、リストを調べて出現するすべての を に置き換える方が簡単な場合があり"-u"ます[-1, "*"]。

Python を少しでも理解できれば、リンク先の例で私が話していることをすべて理解できるはずです。コードは、他の誰かが言及した C バージョンよりも少し読みやすいと思います。また、興味がある方のために、Rubyでshunting-yard を使用することについて少し前に少し書きましたが、単項演算子は別の非終端記号として扱ったので、それらは表示されていません。

于 2011-03-09T02:54:25.020 に答える
3

この質問への回答が役立つ場合があります。

特に、それらの回答の1つは、単項マイナスを処理するCのソリューションを参照しています。

基本的に、二項演算子ができない位置でのマイナス記号の出現に基づいて単項マイナスを認識し、優先順位が異なるため、別のトークンを作成する必要があります。

ダイクストラの元の論文は、彼がこれをどのように扱ったかをあまり明確に説明していませんが、単項マイナスは別の演算子としてリストされていました。

于 2011-03-09T01:10:24.357 に答える
1

レクサーでは、次の疑似ロジックを実装できます。

if (symbol == '-') {
    if (previousToken is a number 
     OR previousToken is an identifier 
     OR previousToken is a function) {
        currentToken = SUBTRACT;
    } else {
        currentToken = NEGATION;
    }
}

乗算および除算よりも優先順位が高く、べき乗よりも低くなるように、否定を設定できます。右結合 ('^' と同様) に設定することもできます。次に、ウィキペディアのページで説明されているように、優先順位と結合性をアルゴリズムに統合するだけです。

トークンが演算子 o1 の場合: スタックの一番上に演算子トークン o2 があり、o1 が左結合であり、その優先順位が o2 の優先順位以下であるか、または o1 がo2 よりも優先順位が低く、o2 をスタックからポップして出力キューに入れます。o1 をスタックにプッシュします。

私はこの対応するコードを実装することになりました：

} else if (nextToken instanceof Operator) {
    final Operator o1 = (Operator) nextToken;

    while (!stack.isEmpty() && stack.peek() instanceof Operator) {
        final Operator o2 = (Operator) stack.peek();

        if ((o1.associativity == Associativity.LEFT && o1.precedence <= o2.precedence)
         || (o1.associativity == Associativity.RIGHT && o1.precedence < o2.precedence)) {
            popStackTopToOutput();
        } else {
            break;
        }
    }

    stack.push(nextToken);
}

Austin Taylor は、単項演算子の 1 つの数値を取り出すだけでよいということはまったく正しいです。

if (token is operator negate) {
    operand = pop;
    push operand * -1;
}

プロジェクト例:

https://github.com/Digipom/Calculator-for-Android/

参考文献：

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

http://sankuru.biz/blog/1-parsing-object-directional-expressions-with-dijkstras-shunting-yard-algorithm

于 2012-10-03T20:29:57.190 に答える