式をバイナリツリーに変換するアルゴリズム

Question

私は式が得られたので、x+(y*z)としましょう。バイナリツリーに変換する必要があります。私はオンラインで見て、infixとpostfixのようなキーワードを見てきました。正規表現をさらにバイナリツリーに簡単に変換できる形式に変換するのに役立ちます。

私の唯一の問題は、このinfixまたはpostfixメソッドを学んだことがないということです。変換する方法は他にありますか、それとも唯一の方法ですか？私は検索してみましたが、これが私が得た唯一の結果でした。

オンラインリソースを使用せずに解決するのは難しい問題です。

Answer 1

インフィックスとポストフィックスは、それ自体では表記法と同じではなく、同じ数式を表現する方法でもありません。 x+(y*z)は、既に演算子がのの方程式であるため、中置表記になっています。他の2つの表記法は、オペレータがオペランドの前にあるので（x+(y*z)が+ x * y z）、オペランドがオペランドの後ろにあるので（後者はy x * x +）、接頭辞（またはポーランド表記）です。あなたがスタック上にyとxを入れy x * x +それが簡単にスタックを介して実施することができるので、後置記法が有用である（ので、我々は、我々は入れて、スタックからxとyをポップし、スタックに戻しx*yを置く*を参照してください、計算しますあなたはShunting-yard algorithm（ウィキペディア経由中置記法からのpostfixに変換することができますスタックにxし、我々は、スタックからz*yとxをポップし、あなたの計算がありますスタックとブームに戻しx+(z*y)を置く+を参照してください）

は、より良い、それを説明します私よりも）

したがって、方程式を通り、スタックにオペランドを葉として追加するので、バイナリツリーを使って後置式表記の方程式を簡単に表すことができます。演算子を取得すると、スタックから最初の2つのノードがポップされ、オペレータが親で、オペランドが子としてポップされた新しいノード。次に、このツリーをスタックに戻します。方程式の終わりに達するまで繰り返す。

Answer 2

この種の作業には、多くの解析ライブラリが用意されています。

from pyparsing import * 

def rearrange(tks): 
    T=tks[0] 
    T[0],T[1] = T[1],T[0] 
    return tks 

expr = Forward() 
arithOp = Word("+-*/", max=1) 
terminal = (Word(alphas, alphanums) 
      | Word(nums) 
      | Suppress("(") + expr + Suppress(")")) 
expr << Group(terminal + arithOp + terminal).setParseAction(rearrange) 

parseTree = expr.parseString("x+(y*z)") 
print parseTree 

が印刷されます：

[['+', 'x', ['*', 'y', 'z']]]