逆ポーランド記法演算をpythonワンライナーで
TLで逆ポーランド記法の話題が流れてたので「ワンライナーでどう書こうかな」と思って書いてみました。
縛りは
- ワンライナーで書く
- セミコロン(;)は使わない
- なるべくゴルフ
できたのがこちら
globals().__setitem__('c',(lambda x,y:globals().__setitem__(x,y)))or c('p',lambda:globals()['s'].pop())or c('i',__import__('itertools'))or c('e',lambda x:x in'+-*/'and eval('%(a)d%(b)s%(c)d'%{'c':p(),'b':(x=='/'and'//'or x),'a':p()}))or i.dropwhile(lambda x:True,(c('l',[y for y in raw_input('> ').split(' ')if y])or c('s',[])or [s.append(c('t',e(x))or t is False and int(x)or t)for x in l]==[]or __import__('sys').stdout.write(str(s)+'\n')for x in i.count())).next()
仕様は、
- +-*/と整数を逆ポーランド記法で表しスペースで区切ったものを入力値
- 演算したものの入ったリストを出力
動作環境はpython2.7です
よくあるようにスタックに入れて演算しています。
なので、きちんとした入力値であれば1個のリスト、そうでなければ2個以上リストもしくはエラーになります。
自分の考えてる逆ポーランド記法なので、たぶんできてるであろうと。
まだ簡単なfizzbuzzワンライナーに関して前に書いたものがあるので興味ある人はどぞ。
http://cocu.hatenablog.com/entry/2013/09/01/093642
考えたこと
まず処理を大きく分けると
- 入力を受け付けリスト化
- リストの先頭から調べ、「記号でなければintに変換してスタックへ、記号であればスタックから2回popして演算結果をpush」を最後まで繰り返す
- スタックを出力(正規な入力であれば１つのみのリストになる)
- 1.に戻る(無限ループ)
となります。
ここで1はraw_inputとsplitで、2はリスト内包表現とラムダの辞書で、3はsys.stdout.writeでできそうだなと考えました。
解説
コードを前から解説していきます。
改行は使えないので関数をorでつないでいますが、読みにくいので改行とインデントをつけたのがこちらです。
#代入関数定義 globals().__setitem__('c',(lambda x,y:globals().__setitem__(x,y)))or #pop関数定義 c('p',lambda:globals()['s'].pop())or #itertoolsをimport c('i',__import__('itertools'))or #演算関数を定義 c('e',lambda x:x in'+-*/'and eval('%(a)d%(b)s%(c)d'%{'c':p(),'b':(x=='/'and'//'or x),'a':p()}))or #主処理無限ループ i.dropwhile( lambda x:True, ( c('l',[y for y in raw_input('> ').split(' ')if y])or c('s',[])or [s.append(c('t',e(x))or t is False and int(x)or t)for x in l]==[]or __import__('sys').stdout.write(str(s)+'\n') for x in i.count()) ).next()
初期化
pythonは代入が文となっており、改行が必要です。
これを何とかするためにglobal変数の辞書を弄って代入します。
globals().__setitem__('pi',3) # pi = 3 # 返り値はNone
このままでは長いので、名前と値を代入するとグローバル変数に代入してくれる関数cを定義します。
関数というよりメソッドに近いですが。
# 1行目 # c(key, value) globals().__setitem__('c',(lambda x,y:globals().__setitem__(x,y)))
2行目はスタックからpopする関数p、3行目では使うライブラリをimportしています。
pythonのimportも代入と同様に改行が必須なので__import__という組み込み関数を使っています。
# 2行目 c('p',lambda:globals()['s'].pop()) # 3行目 c('i',__import__('itertools')) # import itertools as i と同じ
4行目が記号の演算をする関数の定義です。
文字列を受け取り、記号に含まれていればeval内部で演算をします。
# 4行目 c('e',lambda x:x in'+-*/'and eval('%(a)d%(b)s%(c)d'%{'c':p(),'b':(x=='/'and'//'or x),'a':p()}))
最初はevalを使わずラムダ式の辞書を使って書いていたのですが単調だったのとゴルフしたかったのでevalを使いました。
python2で'/'単体だと切り捨て、python3では少数であれば少数が戻るので、どちらでも同じ結果になるように切り捨てで統一しました。(でもイテレータの仕様でpython3では動かないんだけども)
数字であればFalseが返り、記号であればpopしたもの2つを記号で挟んでevalした結果が返ります。
本来ならばx in['+','-',(略)]とすべきところなのですが、
スタック内はすべて数字であることとx in "+-*/"を満たす想定されていない文字列がevalでエラーを起こすためたぶん大丈夫だろうと考えました。
任意のコードが実行可能な方法があったらぜひ教えてください！
主処理
無限ループについて
itertoolsではいくつかのイテレータを使えます。その中のdropwhile関数は条件がTrueである限りイテレータを進め、Falseになるとその後のイテレータを返す関数です。
t=itertools.dropwhile(lambda x: x<5, [1,3,9,2,6]) t.next() # 9 t.next() # 2 t.next() # 6 t.next() # StopIteration
ここで条件が常にTrueとなるようにすると内部のイテレータがエラーになるまで無限に呼び出されます。
イテレータの代わりに標準出力に数字を出力し自身はNoneを返すジェネレータを入れてみました。
print_int = lambda x:__import__('sys').stdout.write(str(x)+', ') # intをあげると標準出力に出力し、Noneを返す関数 t=itertools.dropwhile(lambda x: True, (print_int(x) for x in range(10))) t.next() # 標準出力: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, # 戻り値: StopIteration
rangeの代わりに一種の無限リストであるitertools.countを入れるとジェネレータが無限に呼び出され続け無限ループと同じ意味になります。
先ほどの1.2.3の処理をジェネレータとして書いてあります。
ループ内処理
先ほどのジェネレータのみを抜き出しました。
(
c('l',[y for y in raw_input('> ').split(' ')if y])or # 入力値をリスト化
c('s',[])or #スタック初期化
[s.append(c('t',e(x))or t is False and int(x)or t)for x in l]==[]or # リスト先頭から演算を実施
__import__('sys').stdout.write(str(s)+'\n') # 演算結果表示
for x in i.count())
1行目でraw_inputとsplitをしてリストにして変数lに代入しています。
リスト内包表現なのは空文字列が入っていた場合を弾くためです。
2行目でスタックの初期化をしています。
3行目はリスト内包表現を使って各要素を処理しています。
c('t',e(x))or t is False and int(x)or t
要素xを先ほどの関数eを呼び出し、戻り値をtに代入しています。
そのあとは遅延評価ifを使っています。
関数eはxが数字であればFalseを・記号であれば演算結果を返すので、
tがFalseならばint(x)が、tがFalseでない,つまり演算結果の場合はtを返します。
この結果をappendでスタックにpushしてるので演算されるという感じです。
最後の行で処理後のスタックの状態を表示しています。
すごく長くなってしまいましたが、
楽しみながら書けたので良かったです。
