2

後置記法から中置記法へのコンバーターを作成しようとしていますが、助けが必要です。infix-to-postfix conversion に関する質問が既にあります。これは、変換に失敗している例を示しています。(注: マイナス記号がありません!)

以下は私のコンバーターの出力です。1 番目の「列」は後置入力、2 番目は中置出力、3 番目はおそらく取得すべきもの (?) です。

2 -                      =   - 2                           =?    - 2                       true
1 + 2 +                  =   + 1 + 2                       =?    + 1 + 2                   true
1 + 2 + +                =   + (+ 1 + 2)                   =?    + 1 + + 2                 false
1 + 2 + + 3 - - 4 - -    =   - (- (+ (+ 1 + 2) - 3) - 4)   =?    + 1 + + 2 - - 3 - - 4     false

この問題を解決できると思いますか、それとも最後の 2 行は実際に正しく変換されていますか? この問題を解決するアルゴリズムをどのように記述しますか?

+より多くの演算子 ( andだけでなく) を単項演算子と 2 項演算子の両方として設定できると仮定してください-。単項演算子は 2 項演算子よりも優先されます。

参考文献

  1. Ruby クイズ #148: Postfix から Infix へ、これもGoogle グループから
  2. LiteratePrograms で単項演算子をサポートする分流場アルゴリズム (C、Python、Perl )
4

1 に答える 1

1

後置記法には優先順位の概念がありません。どの演算子のオペランドも常にスタックの上位 N 個の値になるためです (その後、演算子の結果に置き換えられます)。

後置記法の問題の 1 つは、オペランドの数に応じて異なる演算子を参照できる演算子記号 (単項または 2 進数のマイナスを表す - など) をうまく処理できないことです。それを回避する唯一の方法は、各オペレーターがそれを表す一意のシンボルを持つようにすることです。

于 2010-08-25T14:58:43.613 に答える