algorithm - 二分木に後置式を入れる方法は?

Question

だから私は二分木と後置式「6 2 * 3 /」を持っていますそれを木に入れるアルゴリズムは何ですか? お気に入り、

          [/]
          / \
        [*]  [3]
        / \
      [6] [2]

Answer 1

式からツリーを構築するには、式を直接評価するふりをしますが、数値を計算する代わりにツリーを構築します。(このトリックは、後置式よりも多くの場合に機能します。)

アルゴリズム:スタックに中間値 (ツリー) を格納し、各トークンを左から右に調べます。

• 数値の場合は葉ノードにしてスタックに積む。
• オペレーターの場合、スタックから 2 つの項目をポップし、それらの子でオペレーター ノードを構築し、新しいノードをスタックにプッシュします。

最後に、式が適切に形成されていれば、ツリー形式の式全体であるツリーが 1 つだけスタックにあるはずです。