問題タブ [parse-tree]

私は記号代数システムに取り組んでいます。現在、バイナリ解析ツリーから多項式の加算/乗算を実行する方法を検討しています。後でこれを一般的なリングと見なします。

ここでは解析は関係ありません。これは、解析の出力を意図したものです。形成される構文木。ここで何か改善できることがあれば、それについても教えていただければ幸いです。

私は、このツリー構造を折りたたむ/つぶすことができると「感じています」が、それをどのように行うかについてはあまり明確ではありません. 一緒に何かをハックできると信じていますが、まだ Haskell を学んでいるので、より上級のユーザーが何をするかを知りたいと思いました。

以下は、関連するコードの背景です。

関連する 2 つのデータ宣言は次のとおりです。

これが私のテスト例の1つです：

これは典型的な再帰的なツリー タイプで、操作と左右のツリーのリストを保持するノードがあります。以下の操作で計算が進みます。注: 現在のところ、これらはすべて文字列操作です。可能な限り一般的である必要があります (ただし、乗法可換性など、後でさらに構造を追加します)。

の変数名はひどいと思いますoperateが、最初にそれが機能することを確認したかったのです。それをすべて恐ろしいものにすることは、それをより際立たせます。より良い方法を見つけるように私に怒鳴っています。

ここで、fold または foldMap を使用したいと思いますが、各操作で個別のモノイドがあるという問題に遭遇します (つまり(*)、 and (+)。これはほんの始まりにすぎません。他のいくつかの操作を追加します。したがって、必要になります。 「可変モノイド」のようなものか、または最初にモノイドを取得する操作を行う別のマップかもしれません。

クエリ: このバイナリ ツリーと、各ノードでの複数の操作が与えられた場合、構造を折りたたむにはどうすればよいでしょうか? これを Foldable のインスタンスまたはその他の構造として記述するより良い方法はありますか? また、他にもいくつかの二項演算を追加することを目指しています。理想的には、無期限に拡張可能な構造が必要です。2 について解けば、n についても効果的に解けると思います。

テスト例に対応するツリー図

a+a*b のような入力文字列を指定して、それを読み取り、解析し、抽象構文ツリーを作成するスクリプトを Python で作成しようとしています。

この時点で、AST にはトークンがあり、(Var_A, PLUS, (Var_A, MUL, Var_B)) のようなものになっているはずです。

私はここまですべてを行うことができたので、ASTを最適化し、可能な限り変数の少ないものを出力する必要があるため、 (b+1)*a のような出力が得られます

この種の最適化を行うアルゴリズムまたはコードを知っている人はいますか?

Ps。外部ライブラリを使用できません。これをゼロから実装する必要があります

Pythonを使用してtxtファイルを解析しています。私のテキストファイルは次のようになります。

ここの下のテキスト:

マスター：000000スレーブ：000001 000002
マスター：000003スレーブ：000004 000005
マスター：000006スレーブ：000007 000008
マスター：000010スレーブ：
マスター：000012奴隷：
マスター：000014スレーブ：マスター：000018スレーブ：
000018
マスター：000018マスター：000021
マスター : 000024 スレーブ : 000025 000026
マスター : 000028 スレーブ : 000029 000030
マスター : 000032 スレーブ : 000033 000034
マスター : 000036 スレーブ : 000037 000038

マスターをキーとして、スレーブを値として持つディクショナリ内のこれらすべての値が必要です。

{マスター 1: [スレーブ 1、スレーブ 2]、マスター 2: [スレーブ 1、スレーブ 2]}

キー値

00000 00001 , 00002

00003 00004 , 00005...

私はpython初心者です。助けてください。ありがとうございました