Java で算術式を解析してツリーを構築する方法

Java での算術式の解析とそこからのツリーの構築

はじめに

算術式の解析と等価ツリーの構築コンパイラの設計と言語処理において不可欠なタスクです。この記事では、Java で算術式を解析し、ツリー表現を作成する方法を説明します。

式の解析

式を解析するには、スタックを使用できます。ベースのアルゴリズム。式を反復処理するとき:

• 開き括弧をスタックにプッシュします。
• 数値と演算子をスタックにプッシュします。
• 閉じ括弧を見つけて、一致する左括弧に到達するまでスタックをポップしてサブツリーを作成し、結果をスタックにプッシュします。

ツリーの構築

式が解析されたら、スタックからツリー ノードを構築できます:

• リーフ ノード: 整数は LeafInt ノードになります。
• 演算子ノード: 演算子は次のようになります。 PlusOp、MinusOp、MultOp、または DivOp クラスを持つノードとその子はスタックからポップされます。

例

式 (5 2) を考えてみましょう。 *7:

<code class="java">Stack<Node> stack = new Stack<>();
stack.push(new LeafInt(5));
stack.push(new PlusOp());
stack.push(new LeafInt(2));
stack.push(new MultOp());
stack.push(new LeafInt(7));
while (stack.size() > 1) {
  Node right = stack.pop();
  Operator op = (Operator) stack.pop();
  Node left = stack.pop();
  stack.push(new OpNode(op, left, right));
}</code>

結果のツリーは次の構造になります。

    *
   / \
  +   7
 / \
5   2

負の数と括弧の処理

負の値を処理するには数値の場合は、5-2 ではなく 5 (-2) として表します。負の符号は常に単項優先です。同様に、括弧は演算の順序を強制します。

検証

正確さを確認するには、以下をチェックして式を検証します。

• 左括弧は
• 各演算子には正しい数のオペランドがあります。

結論

スタックベースのアルゴリズムを使用すると、次のようになります。算術式を解析して同等のツリー表現を構築するのが簡単です。このアプローチは、Java での算術式のさらなる分析と操作のための信頼できる基盤を提供します。

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