Java で算術式からツリーを解析して構築するにはどうすればよいですか?

Java で算術式を解析し、そこからツリーを構築する

この記事では、算術式を解析し、算術式を構築するタスクについて詳しく説明します。 Java の対応するツリー データ構造。目的は、「(5 2)*7」のような式を、式の構造に似たツリーに処理することです。

アプローチ: スタックの使用

式ではスタックを利用することができます。このアプローチには、次の式からのトークンを反復処理することが含まれます。

• 左括弧 "(" が見つかった場合、スタックにプッシュされます。
• 数値 (オペランド) が見つかった場合

• 演算子 ( 、 -、 *、/) が見つかった場合:

  • その優先順位が比較されます。
  • 優先順位が低いか等しい場合、式は前の "(" または式の先頭まで評価されます。
  • の結果評価はスタックにプッシュされます。

例: "(5 2)*7" の解析

式 " の解析を検討してください。 (5 2)*7":

• "(" がスタックにプッシュされます。
• "5" がリーフ ノードとしてスタックにプッシュされます。
• " " はスタックにプッシュされます。
• "2" はリーフ ノードとしてスタックにプッシュされます。

• ")" が検出されるため、式 "5 2"が評価されます:

  • リーフ ノード "5" と "2" がスタックからポップされます。
  • 2 つのリーフ ノードをそのノードとして、新しい追加ノード " " が作成されます。
  • 加算ノードがスタックにプッシュされます。
• "*" がスタックにプッシュされます。
• "7" がスタックにプッシュされます。リーフ ノードとしてのスタック。

• 「eof」(式の終わり) が検出されたため、式「(node) 7」が評価されます:

  • 乗算ノード "(*node)" とリーフ ノード "7" がスタックからポップされます。
  • 新しい乗算ノード "*" が作成され、スタックにプッシュされます。

スタックから取得された最終的なツリー構造は、元の式と一致します。

    *
   / \
  +   7
 / \
5   2

結論

使用算術式を解析するためのスタックにより、それらの式を表すツリー データ構造を効率的に構築できます。このアプローチにより、解析されたツリーに対してさらなる操作と分析を実行できるようになります。

以上がJava で算術式からツリーを解析して構築するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。