Python(逆ポーランド記法電卓 再帰版 その1～4)
リストの各要素に対して再帰処理を利用することで、逆ポーランド記法の数式を処理するプログラム1～4です。
各プログラムではスタックと再帰処理を共通とし、各演算子へのアプローチをより拡張性の高い記述に変えています。
ポイントとなる再帰処理はcalc()で行っているリストの各要素を演算子か数値かで処理を分け、calc(xs[1:])のようにチェック済みの要素以降を再帰で繰り返し処理することでリストが空になるまで行われるようにしています。
#
# 逆ポーランド記法電卓 再帰版 その1
#
import math
_stack = []
def push(x):
_stack.append(x)
def pop():
return _stack.pop()
def clear_stack():
_stack.clear()
def stack_depth():
return len(_stack)
def calc(xs):
print(xs,_stack)
if not xs:
return pop()
operate(xs[0])
return calc(xs[1:])
def operate(x):
if isinstance(x,int):
push(x)
elif x == "+":
push(pop() + pop())
elif x == "-":
tmp = pop()
push(pop() - tmp)
elif x == "/":
tmp = pop()
push(pop() / tmp)
elif x == "*":
push(pop() * pop())
elif x == "//":
tmp = pop()
push(pop() // tmp)
elif x == "**":
tmp = pop()
push(pop() ** tmp)
elif x == "root":
push(math.sqrt(pop()))
else:
raise ValueError(f"unknown operator: {x}")
def execute(s):
def convert(elem):
if elem.isdigit():
return int(elem)
else:
return elem
parsed = s.split(" ")
elems = [convert(elem) for elem in parsed if elem != ""]
print("計算結果>",calc(elems))
while True:
s = input("後置記法の数式を入力してください> ")
if s.lower() in {"exit","quit","bye"}:
break
clear_stack()
try:
execute(s)
if stack_depth() > 0:
print("スタックに値が残っています！")
except:
print("不正な式です!")その1では各演算子の処理をoperate(x)内で個別に定義しているので冗長になり、拡張性に乏しいものとなっています。
#
# 逆ポーランド記法電卓 再帰版 その2
#
import math
_stack = []
def push(x):
_stack.append(x)
def pop():
return _stack.pop()
def clear_stack():
_stack.clear()
def stack_depth():
return len(_stack)
def calc(xs):
print(xs,_stack)
if not xs:
return pop()
operate(xs[0])
return calc(xs[1:])
op_dic = { "+":(2,lambda a,b:a+b),
"-":(2,lambda a,b:a-b),
"*":(2,lambda a,b:a*b),
"/":(2,lambda a,b:a/b),
"//":(2,lambda a,b:a//b),
"**":(2,lambda a,b:a**b),
"root":(1,math.sqrt) }
def operate(x):
if isinstance(x,int):
push(x)
elif x in op_dic:
n_args,f = op_dic[x]
if n_args == 2:
b = pop()
a = pop()
push(f(a,b))
else: # n_args == 1
push(f(pop()))
else:
raise ValueError(f"unknown operator: {x}")
def execute(s):
def convert(elem):
if elem.isdigit():
return int(elem)
else:
return elem
parsed = s.split(" ")
elems = [convert(elem) for elem in parsed if elem != ""]
print("計算結果>",calc(elems))
while True:
s = input("後置記法の数式を入力してください> ")
if s.lower() in {"exit","quit","bye"}:
break
clear_stack()
try:
execute(s)
if stack_depth() > 0:
print("スタックに値が残っています！")
except:
print("不正な式です!")その2では各演算子の処理を辞書として登録し、要素数に応じて処理を分けていますが、要素数が決めうちで処理されている点で、まだ改善できそうです。
#
# 逆ポーランド記法電卓 再帰版 その3
#
import math
_stack = []
def push(x):
_stack.append(x)
def pop():
return _stack.pop()
def clear_stack():
_stack.clear()
def stack_depth():
return len(_stack)
def calc(xs):
print(xs,_stack)
if not xs:
return pop()
operate(xs[0])
return calc(xs[1:])
def generate(n,f):
"""<高階関数かつクロージャ>
要素数分スタックからpopして関数を適用しスタックにpushする
@param n 要素数
@param f 数式関数オブジェクト
@return proc 適用処理関数"""
def proc():
args = [pop() for _ in range(n)]
args.reverse()
push(f(*args))
return proc
op_dic = { "+":generate(2,lambda a,b:a+b),
"-":generate(2,lambda a,b:a-b),
"*":generate(2,lambda a,b:a*b),
"/":generate(2,lambda a,b:a/b),
"//":generate(2,lambda a,b:a//b),
"**":generate(2,lambda a,b:a**b),
"root":generate(1,math.sqrt),
"if":generate(3,lambda a,b,c: b if a else c) }
def operate(x):
if isinstance(x,int):
push(x)
elif x in op_dic:
op_dic[x]()
else:
raise ValueError(f"unknown operator: {x}")
def execute(s):
def convert(elem):
if elem.isdigit():
return int(elem)
else:
return elem
parsed = s.split(" ")
elems = [convert(elem) for elem in parsed if elem != ""]
print("計算結果>",calc(elems))
while True:
s = input("後置記法の数式を入力してください> ")
if s.lower() in {"exit","quit","bye"}:
break
clear_stack()
try:
execute(s)
if stack_depth() > 0:
print("スタックに値が残っています！")
except:
print("不正な式です!")その3ではgenerate(n,f)という高階関数かつクロージャを定義して辞書で定義された関数を generate(n,f) 内のproc()で要素数に応じた処理をすることで様々な要素数への対応も可能となりましたが、辞書内に繰り返し generate を記述し、処理をしている点で更なる改良が可能です。
#
# 逆ポーランド記法電卓 再帰版 その4
#
import math
_stack = []
def push(x):
_stack.append(x)
def pop():
return _stack.pop()
def clear_stack():
_stack.clear()
def stack_depth():
return len(_stack)
def calc(xs):
print(xs,_stack)
if not xs:
return pop()
operate(xs[0])
return calc(xs[1:])
def generate(n,f):
"""<高階関数かつクロージャ>
要素数分スタックからpopして関数を適用しスタックにpushする
@param n 要素数
@param f 数式関数オブジェクト
@return proc 適用処理関数"""
def proc():
args = [pop() for _ in range(n)]
args.reverse()
push(f(*args))
return proc
_op_table = ( ("+",2,lambda a,b:a+b),
("-",2,lambda a,b:a-b),
("*",2,lambda a,b:a*b),
("/",2,lambda a,b:a/b),
("//",2,lambda a,b:a//b),
("**",2,lambda a,b:a**b),
("root",1,math.sqrt),
("if",3,lambda a,b,c: b if a else c) )
op_dic = dict([(name,generate(n,f)) for name,n,f in _op_table])
del _op_table
def operate(x):
if isinstance(x,int):
push(x)
elif x in op_dic:
op_dic[x]()
else:
raise ValueError(f"unknown operator: {x}")
def execute(s):
def convert(elem):
if elem.isdigit():
return int(elem)
else:
return elem
parsed = s.split(" ")
elems = [convert(elem) for elem in parsed if elem != ""]
print("計算結果>",calc(elems))
while True:
s = input("後置記法の数式を入力してください> ")
if s.lower() in {"exit","quit","bye"}:
break
clear_stack()
try:
execute(s)
if stack_depth() > 0:
print("スタックに値が残っています！")
except:
print("不正な式です!")その4のポイントは_op_tableを定義し、
op_dic = dict([(name,generate(n,f)) for name,n,f in _op_table])
のようにリスト内包処理とdictを利用して辞書を生成することで、その3で冗長と感じた generateの記述を繰り返し書く必要がなくなりました。
またdel _op_tableで不要となったグローバルな値を削除し、これ以降アクセスすることができないようにしています。
これらをふまえて前回作成したプログラムを改良したものを次回投稿します。
