11

特定の数式を次のような解析ツリーにトークン化したい:

((3 + 4 - 1) * 5 + 6 * -7) / 2

                          '/'
                        /     \
                       +        2
                    /     \
                  *         *
                /   \     /   \
               -     5   6     -7
             /   \
            +     1
          /   \
         3     4

これを行う純粋なPythonの方法はありますか? Python に文字列として渡してから、上記のようにツリーとして返すようなものです。

ありがとう。

4

5 に答える 5

10

はい、Pythonastモジュールはこれを行うための機能を提供します。astモジュールは定期的に変更されるようであるため、Pythonのバージョンの正確なインターフェイスを検索する必要があります。

特に、このast.parse()方法はアプリケーションに役立ちます。

>>> import ast
>>> ast.parse("(1+2)*3", "", "eval")
<_ast.Expression object at 0x88950>
>>> ast.dump(_)
'Expression(body=BinOp(left=BinOp(left=Num(n=1), op=Add(), right=Num(n=2)), op=Mult(), right=Num(n=3)))'
于 2011-02-19T07:34:43.860 に答える
3

Pythonにはいくつかのパーサーフレームワークがあります。いくつかの一般的なものはPLYとpyparsingです。NedBatchelderにはかなり完全なリストがあります。

于 2011-02-19T07:35:19.483 に答える
1

このような数式を解析するための、確立された優れたアルゴリズムはたくさんあります。特に優れたものの1つは、ダイクストラの操車場アルゴリズムです。これを使用して、このようなツリーを作成できます。Pythonでの特定の実装についてはわかりませんが、アルゴリズムは特に複雑ではなく、1つを作成するのにそれほど時間はかからないはずです。

ちなみに、構築しているツリーのより正確な用語は、解析ツリーまたは抽象構文ツリーです。

于 2011-02-19T07:30:22.327 に答える
0

これを行うための「純粋なPython」の方法はわかりません。これはすでに実装されています。ただし、ANTLR（http://www.antlr.org/）をチェックする必要があります。これは、オープンソースのパーサーであり、レクサーであり、Pythonを含む多くの言語用のAPIを備えています。また、このWebサイトには、求めていることを正確に実行する方法を示す優れたビデオチュートリアルがいくつかあります。一般的な使い方を知るのにとても便利なツールです。

于 2011-02-19T07:31:45.470 に答える