Shunting-yardアルゴリズムに関する質問

Question

私はShunting-yard algorithmの後にC++で式パーサーを実装しましたが、wikipediaの説明については問題があります。それは詳細にアルゴリズム "に一部です：

If the token is an operator, o1, then: 

    while there is an operator token o2, at the top of the operator stack and either 

     o1 is left-associative and its precedence is less than or equal to that of o2, or 
     o1 is right associative, and has precedence less than that of o2, 

      pop o2 off the operator stack, onto the output queue; 

    at the end of iteration push o1 onto the operator stack. 

それは私のundetstandingによる "while there is an operator token o2" は、 "while there is an operator or function token o2" であると言います。

関数は演算子として扱われ、すべての従来の演算子よりも優先順位が高くなければなりません。

Answer 1

operatorトークンとfunctionトークンの間に混乱があってはならないと私は理解しています。よく形成されたexpressionでは、各関数の引数は、左かっこの間に囲まなければなりません。他の場所の括弧は、優先順位を付けるために、または単に明瞭にするために使用されています。 この観察に基づいて、あなたの質問への答えは

関数演算子として扱われ、すべての伝統的な演算子よりも高い優先順位を持つべきである、右のことですか？それはアルゴリズムの説明でoperator言われている場合

号

、それはoperatorを意味し、function手段function言われている場合。井戸の形がexpressionの場合、右かっこを読み取ると、functionがポップアップし、右括弧が引数リストを閉じます。 functionとoperatorの間の混乱は、間違った式の解釈を与えるために実装を誤解させます。括弧は単に置き忘れれているかもしれないが、あなたがオペレータのようfunctionを扱う場合は、次の式

4 + (sin 3 + 1) 

を想像してみて、あなたはそれに意味を与えるだろう。また、これに感謝するでしょう

4 - sin() 5*6 

複数の引数を持つ関数を考えると、より微妙になります。

Answer 2

「オペレータトークンo2がありますが、私の理解していないところでは、オペレータまたはファンクショントークンo2が存在します」と表示されます。

関数は演算子として扱われ、すべての従来の演算子よりも優先順位が高くなければなりません。

本文は正しいです。演算子スタックに関数シンボルがある場合は、現在、関数の引数を解析しており、関数シンボルをそこに移動する前にすべてが出力キューに移動していることを意味します。

入力の前に演算子があり、演算子スタックの一番上に関数記号がある場合は、かっこが足りないことを意味します。どちらの場合も（スタックの一番上にsinを持つ、または上の(を持つ：あなたはsin a + bは、上記のアルゴリズムに従ってsin(a+b)の出力と同じである出力a b + sin、ますようにそれを離れて得ることができるいくつかの場合には

スタックの最上部）、上記のループ中には入力しませんが、スタックには+を押してください。