C で数式文字列をツリー構造に変換するために、操車場アルゴリズムをどのように使用できますか?

シャントヤード アルゴリズムを使用した C での数学式の解析

プログラミングの領域では、複雑な数学的計算をコードで表現するには解析が必要になることがよくありますテキスト文字列を内部ツリー表現に変換します。これにより、これらの式の後続の評価と操作が容易になります。

次の数式文字列を解析するタスクを考えてみましょう: "(a b)c-(d-e)f/g"。目標は、C クラスを使用してこの式を表すツリー構造を構築することです。

操車場アルゴリズムの使用

操車場アルゴリズムは、次のような効果的な戦略を提供します。数式をツリーに解析します。このアルゴリズムは 2 つのフェーズで動作します:

1. 式をトークン化: 文字列をオペランド (例: "a"、"b")、演算子 ("a"、"b" など) を含む個々のトークンに分割します。例: " "、"-")、括弧。

2. ツリーの構築: 演算子スタックと出力スタックの 2 つのスタックを使用します。トークンを一度に 1 つずつ処理します。

   • トークンがオペランドの場合は、出力スタックにプッシュします。
   • トークンが演算子の場合は、演算子スタックから演算子をポップします。優先順位の低い演算子または開き括弧が出現するまで。現在の演算子を演算子スタックにプッシュします。
   • トークンが開き括弧の場合、演算子スタックにプッシュします。
   • トークンが閉じ括弧の場合、演算子スタックから演算子をポップします。対応する開き括弧が見つかるまで。結果の部分式を出力スタックにプッシュします。

ツリー構造の定義

ツリー構造を表すには、次の C を定義します。クラス:

• Exp (基本クラス)
• オペランドの項 (Exp から継承)
• 演算子のノード (Exp から継承)

解析プロセスの例

式「(a b)c-(d-e)f/g」の場合、解析プロセスは次のように進行します。

Operator Stack | Output Stack
--------------|--------------
               | a b
+             | a b +
               | a b + c
*             | a b + c *
               | a b + c * d
-             | a b + c * d -
               | a b + c * d - e
               | a b + c * (d - e)
*             | a b + c * (d - e) f
               | a b + c * (d - e) f /
               | (a + b) * c - (d - e) * f / g

結果のツリー構造は次の形式になります:

            *
            / \
       (a + b) * (d - e)
            / \
           /   \
          c     / \
               f / g

以上がC で数式文字列をツリー構造に変換するために、操車場アルゴリズムをどのように使用できますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。