ポーランド記法で書かれた数式を木構造にしたい

Pythonでポーランド記法で++243のように書かれたものを二分木の木構造にするプログラムを作りたいのですが、それを行うためのライブラリはありますか？それとも自分で作る必要がありますか？
漠然とした質問ですみませんが、よろしくお願いします。

行動規範の内容に同意します

回答2件

ベストアンサー

自分でやってもしれてます。

Python
1from collections import deque
2
3deque = deque('++243')
4
5def isBinaryOperator(token):
6    if token == '+':
7        return True
8    else:
9        return False
10
11def convert():
12    token = deque.popleft()
13    if isBinaryOperator(token):
14        return (token, convert(), convert())
15    else:
16        return (token)
17
18print(convert())
19

上記コードの convert 関数は要素数三つのタプルを返します。最初の要素が親、次の要素が左の子、最後の要素が右の子です。
実行結果は次のようになります。

('+', ('+', '2', '4'), '3')

ルートが '+' で、その左の子が ('+', '2', '4') 右の子が '3' です。
('+', '2', '4') は親が '+' で左の子が '2' 右の子が '4' です。
これをタプルでなくノードクラスを作れば木構造のできあがりです。

投稿2020/05/24 14:19

Zuishin

総合スコア28675

milano

2020/05/24 23:21

ありがとうございます。このように表すことを考えてもいませんでした。タプルで木構造を表すことについてもっと詳しくお聞きしたいことがあります。++243においての木構造のノードのleftとrightとparentはどのように調べればよいですか？つまり++243の２番めの+のparentは+,leftは2,rightは4という感じでです。よろしくお願いいたします。

Zuishin

2020/05/24 23:24

まずその前に、私の書いたコードの意味が全部わかりますか？

milano

2020/05/25 01:04

分かります

Zuishin

2020/05/25 01:20

だとすると、何を聞かれているのかよくわからないんですが、どういうことでしょう？

Zuishin

2020/05/25 01:45

(A, B, C) は A の子として B と C があるという意味です。 ('+', ('+', '2', '4'), '3') では '+' が A にあたり、('+', '2', '4') が B にあたり、'3' が C にあたります。こういうことですか？

milano

2020/05/25 03:09

何回も親切にコメントをしていただき本当にありがとうございます。再帰をすることはわかるのですが、例えば二番目の+について[node.parent,node.left,node.right]を出力するにはタプルで表された木構造ではどうすればいいですか？

Zuishin

2020/05/25 03:12

回答にも書きましたが、タプルではなくクラスを作ってください。出力に関してもそうですが、その他の使い勝手も上がるでしょう。

Zuishin

2020/05/25 03:41 編集

もし「出力」ではなく「解析」のことだとすれば、御覧の通り解析のできる非常に短いコードを示したので、それを追ってみれば、言葉で説明されるよりもわかりやすいのではないかと思います。 > まずその前に、私の書いたコードの意味が全部わかりますか？に対して > 分かりますという返事が返ってきたので、解析のことではないと思いますが、念のため。

milano

2020/05/25 03:51

要するに、クラスでやるしか方法がないということですね。ありがとうございます。

Zuishin

2020/05/25 03:53

できないことはありませんが、タプルでは機能が足りていないので作りにくいと思います。ここでタプルを使ったのは単にロジックを示すだけならタプルで十分だったからです。

milano

2020/05/25 05:44

わかりました。丁寧にしていただきありがとうございます。

行動規範の内容に同意します