1

文字列式が与えられた場合、どのようにツリーを作成しますか?

私には立ち往生している課題があります。

(( 5 * 10 ) /2 - (( 2 + 3) + 6))任意のデータ構造を使用して次の式を評価する必要があります。

スタックを使用して、文字列が適切に形成されていることを確認できます。しかし、さまざまな値をツリーに追加してから、それらを順番に評価するにはどうすればよいでしょうか。

文字列の読み方のヒントがあれば教えてください ((( 490 * 9 ) / 2)/5/6 - (( 2/4 + 3) + 6 * 5))

たとえば、( -) が入力式の 15 番目の部分文字列である場合、3 つのルートの ( ) を取得するにはどうすればよいでしょうか? /( )6 式が ( /)5 などの後に発生することを確認するにはどうすればよいですか?

4

5 に答える 5

3

あなたが探しているものはここに提供されています: http://www.codeproject.com/Articles/88435/Simple-Guide-to-Mathematical-Expression-Parsing

于 2012-05-17T20:28:19.383 に答える
2

任意の文字列 [数学を表す] 式を評価する

次の 3 つのことを行う必要があります。

  • 言語を表す抽象構文ツリーの型を定義する
  • 構文の再帰降下パーサーを作成します
  • 構文のインタープリターを作成します

これは非常に簡単に行うことができます。

簡潔なので Haskell 表記を使用しますが、必要に応じて翻訳できます。

あなたの言語のタイプ:

data Exp = Op BinOp Exp Exp
         | Lit Int

data BinOp = Plus
           | Times
           | Div
           | Sub

これで、この言語で式のインタープリターを作成できます。

eval :: Exp -> Int
eval (Lit n)      = n
eval (Op o e1 e2) = 
   let v1 = eval e1
       v2 = eval e2
   in case o of
       Plus  -> v1 + v2
       Times -> v1 * v2
       Sub   -> v1 - v2
       Div   -> v1 / v2 -- note, may fail!

Ok。これがあなたの言語の用語の評価者です。次に、再帰降下パーサーを作成します...

于 2012-05-17T22:57:59.173 に答える
1

括弧は操作の順序を示しているため、スタックを使用してすべてが一致していることを確認する方法と同様に、それらの一致を解析し、それらをツリー内の要素として使用して、演算子が各幅の子である評価用の階層を作成できます。かっこの賢明なレベルが一致します。

于 2012-05-17T20:30:08.633 に答える
1

2番目の編集：opが明確になり、他の回答を参照

于 2012-05-17T20:32:56.733 に答える
1

ここでの他の回答は、式ツリーをメモリに読み込むことをカバーしていますが、構築したツリーを評価することはカバーしていません。

ツリーを評価するための一般的な戦略は、ツリーがノードとリーフで構成されている必要があることです。ここで、ノードは子を持つ演算子であり、リーフは定数値です。たとえば、式 (((490 * 9) / 2) / 5 / 6 - ((2 / 4 + 3) + 6 * 5)) はツリーに変換されます。

                      -
                  / \
                 / \
              div +
             / \ / \
          div 6 + *
         / \ / \ / \
      区分 5 区分 3 6 5
     / \ / \
    * 2 2 4
  / \
450 9

このツリーを評価するには、ルートから始めます。最初に左のサブツリーと右のサブツリーを再帰的に評価し、次に 2 つのサブツリー評価の結果に演算子を適用します。各リーフ (数値) はそれ自体に評価されます。

この場合、ルート (-) から開始し、左のサブツリーを 73.5 まで評価し、右のサブツリーを 33.5 まで評価し、減算して最終結果 40 を取得します。

より正確な例として、再帰呼び出しのいくつかのレイヤーが作成された後、ツリーの左端にあるノードを見てみましょう。リーフ 450 は 450 に評価され、リーフ 9 は 9 に評価され、ノード(* 450 9)(ツリーのノードを Lisp のようなプレフィックス表記で記述) は 4050 に評価されます。したがって、ノード(/ (* 450 9) 2)から、左の再帰呼び出しは 4050 に評価され、右の再帰呼び出しは 2 に評価されます。つまり、ノード全体が 2025 に評価されます。値を結合する前にノードから再帰呼び出しを行い、各リーフがそれ自体に評価されることを確認する限り、ツリーの評価は簡単です。

于 2012-05-17T20:58:59.057 に答える