逆ポーランド記法の式から、式の木（２分木）を作るプログラム（再帰）

Question

###前提・実現したいこと
python3でプログラミングしています。
逆ポーランド記法の式から、式の木（２分木）を作るプログラムを作成しています。
再帰の部分の処理がうまくいっていないようなのですが、よくわかりません。よろしくおねがいします。

（入力例）ab*cd+e/-
（希望する出力）-*ab/+cde

###発生している問題・エラーメッセージ
（誤った出力）-/ee/ee

###該当のソースコード
python 3.4.3

# coding: utf-8
# Here your code !

class tnode :
    def __init__(self):
        self.left = None
        self.ope = ""
        self.right = None

def gentree(p, w):
    p = tnode()
    w_lst = list(w)
    p.ope = w_lst.pop()
    if p.ope == "-" or p.ope == "+" or p.ope == "*" or p.ope == "/" :
        w = "".join(w_lst)
        p.right = gentree(p.right, w)
        p.left = gentree(p.left, w)
    return p
    
def prefix(p):
    if p :
        yield p.ope
        yield from prefix(p.left)
        yield from prefix(p.right)

# main
f = input()
print(f)

root = None
root = gentree(root, f)

for x in prefix(root):
    print(x, end="")

Answer 1

質問中のソースコードは構造的には正しいと思います。少し修正（★箇所）するだけ期待通りの結果が得られます。

def gentree(p, w):
    p = tnode()
    p.ope = w.pop() # ★引数を直接変更
    if p.ope == "-" or p.ope == "+" or p.ope == "*" or p.ope == "/" :
        p.right = gentree(p.right, w) # ★引数を渡す
        p.left = gentree(p.left, w)   # ★引数を渡す
    return p

# main
f = input()
print(f)

root = None
root = gentree(root, list(f)) # ★str→listに変換

ちなみにgentree関数の第一引数には意味がないため、下記コードの方がすっきりしますね。

def gentree(w):
    p = tnode()
    p.ope = w.pop()
    if p.ope == "-" or p.ope == "+" or p.ope == "*" or p.ope == "/" :
        p.right = gentree(w)
        p.left = gentree(w)
    return p

root = gentree(list(f))

Comments

[退会済みユーザー]

ありがとうございます！　引数の問題だったのですね。　助かりました。