Pythonで逆ポーランド記法プログラムを書いてみた

逆ポーランド記法というのは、たとえば

2 + 3

という式を

2 3 +

と表記する記法、つまり2つの演算対象の後ろに演算子をつけるように変換する記法のこと。Lispの逆(つまりポーランド記法？)バージョンといえるのかな。

(a+b*c)*(p-q)

なら(プログラムでは括弧をはずして）

abc*+pq-*

となる。

以下プログラム

#2007/10/17ちょっと修正しました
def reverse_polish():
    LIST = list()    #リスト作成
    read_a_line(LIST) #一行読み込む
    skip_spaces(LIST) #空欄は削除する
    #ここから逆ポーランド変換
    List1 = []    #演算数を入れるリスト&逆ポーランド記法の結果が入る
    List2 = ['@'] #演算子を入れるリスト
    import string
    i,n = 0,len(LIST)-1
    while i <= n:
        if LIST[i] == "$": #$が入力されたら終了
            break
        if not (LIST[i] in string.letters or LIST[i] in string.digits or LIST[i] in string.punctuation):
            reverse_polish(LIST)
        elif LIST[i] in string.letters or LIST[i] in string.digits:
            List1.append(LIST[i])
        elif LIST[i] == '(':
            List2.append(LIST[i])
        elif LIST[i] == ')':
            while not List2[len(List2)-1] == '(':
                List1.append(List2[len(List2)-1])
                del(List2[len(List2)-1])
            del(List2[len(List2)-1])
        elif LIST[i] in ('+','-','*','/'):
            while less_or_equal_prec(LIST[i],List2[len(List2)-1]):
                List1.append(List2[len(List2)-1])
                del(List2[len(List2)-1])
            List2.append(LIST[i])
        i = i + 1
    while not List2[len(List2)-1] == '@':
        List1.append(List2[len(List2)-1])
        del(List2[len(List2)-1])
    print List1 #逆ポーランド変換ここまで
    #ここから数字を計算する
    i,n = 0,len(List1)-1
    List3 = []  #ここに計算結果が入る
    while i <= n:
           if List1[0] in string.digits:
                List3.append(List1.pop(0))
           elif List1[0] == '+':
                temp = int(List3.pop()) + int(List3.pop())
                List3.append(temp)
                del(List1[0])
           elif List1[0] == '-':
               temp = int(List3.pop(-2)) - int(List3.pop())
               List3.append(temp)
               del(List1[0])
           elif List1[0] == '*':
               temp = int(List3.pop()) * int(List3.pop())
               List3.append(temp)
               del(List1[0])
           elif List1[0] == '/':
               temp = int(List3.pop(-2)) / int(List3.pop())
               List3.append(temp)
               del(List1[0])
           i = i + 1
    if len(List3) == 1: #1個だけの時はちゃんと計算ができた
            return List3[0]

まずLIST = list()で空リストLISTを作る。そして~~initialise(list)関数~~(は必要なーし)

def initialise(list):
    i,n = 0,len(list)-1
    while i <= n:
        del(list[0])
        i = i + 1

でリストをイニシャライズする。次にread_a_line(list)関数

def read_a_line(list):
    inp = raw_input()
    for i in inp:
        list.append(i)

で、読み込んだ1行の式をリストへ入れる。さらにその中にスペースを入れないためにskip_spaces(list)関数

def skip_spaces(list):
    i = 0
    while i <= len(list)-1:
        if list[i] == " ":
            del(list[i])
        i = i + 1

でスペースを削除する。

いま、残ったリストLISTには読み込まれた式がスペースなしに入ってる。たとえば

A　 + B * C

と入力すると、

['A', '+', 'B', '*', 'C']

という風にリストLISTに格納されてる。

ここからいよいよ逆ポーランド変換するのだけど、詳細は割愛。ちなみに
while less_or_equal_prec(a,b)については

def less_or_equal_prec(a,b):
    #aの優先順位がbの優先順位より低いか等しいとき真となる
    if a in ('*','/') and b in ('*','/'):
        return True
    elif a in ('+','-') and b in ('+','-','*','/'):
        return True
    else: return False

のような関数。つまり'+'や'-'は'*'や'/'よりも優先順位が低い(2+3*4のときは*を先に計算しなければならないということ)から、より高い優先順位の演算子が出るまでList2に入ってなければならない。

#ここから数字を計算する

のところからは、入力された式が全部数字のとき、計算結果を返すプログラム。

実行結果は

>>> reverse_polish()
3+4
['3', '4', '+']
7
>>> reverse_polish()
A + B * C
['A', 'B', 'C', '*', '+']
>>> reverse_polish()
2+3*3
['2', '3', '3', '*', '+']
11
>>> reverse_polish()
(a+b*c)*(p-q)
['a', 'b', 'c', '*', '+', 'p', 'q', '-', '*']

読みづらくて、へんてこなプログラムかもしれないけど、いい練習にはなったかな。
ただ、このプログラムは1文字単位だけしか認識しない。つまり

apple + lemmon

とすると、おかしなことになる

['a', 'p', 'p', 'l', 'e', 'l', 'e', 'm', 'm', 'o', 'n', '+']

世に出てるプログラミング言語だとvarとかp1とか任意の変数を指定できるけど、これはちっともできてない。まだよく分からないけど、これは集合という考え方を使えばうまくいくらしい・・・。もっと勉強します。