操車場アルゴリズムとは
中置記法に属する構文に従った順序で記号が並んでいる数式等の記号列を解析する、スタックベースのアルゴリズムである。
その出力をそのまま並べれば逆ポーランド記法（RPN）になるし、あるいは抽象構文木を構築したり、数値と四則演算等の算術式のようなものであれば、直接その計算結果を得てしまっても良い。
つまり、操車場アルゴリズムとは、__中置記法__のものを__逆ポーランド記法（後置記法）__に置き換えるアルゴリズムです。
上記にもある通り、四則演算等は置き換えの段階で、そのまま計算処理を実装してもいいみたいです。
中置記法、前置記法、後置記法
まず、中置記法というのはなにかというと、__数式やプログラムを記述する方法の一種__で、__演算子を真ん中に置く__事からこう呼ばれている。つまり、小学校で習う1+1のような形式のもの。
その他の記法として、
・ポーランド記法（前置記法）
演算子を前に記述する。
1+1だったら+ 1 1になる。
・逆ポーランド記法（後置記法）
演算子を操作対象の後に記述する
1+1だったら1 1 +になる。
というものもある。
逆ポーランド記法のメリット
後置記法にする事で、
・括弧などの区切りを用いずに表現出来る事で、評価が楽になる。
・左から計算していけば正しい結果が得られる。
などの利点があります。
普段日常で使っている中置記法などだと、区切りというものが存在するためプログラム的に評価するためには、それらを考慮する必要がありますが、後置記法にする事で、それらを考えなくて良くなります。
操車場アルゴリズムの流れ
操車場アルゴリズムによって、逆ポーランド記法で並べ替えようとすると、次の順番で処理が進んでいきます。
まず最初に、アルゴリズム内部では入力文字列がトークンに置き換えられ、例えば11+4は11, +, 4などと分割されます。
そして、先頭からトークンを読み込んでいき、括弧や演算子はスタックに、数字はキューにたまっていき、ある一定の条件でスタックの演算子らが取り出されキューに追加されていきます。
2*(3+4)-1を例に流れを見ていってみます。
| 順番 | スタック | 出力キュー | 式 | 説明 |
|---|---|---|---|---|
| 1 | 2 | *(3+4)-1 | 先頭から探索が始まる。2のためキューに入れる |
|
| 2 | * | 2 | (3+4)-1 |
*のため、スタックに入れる |
| 3 | *( | 2 | 3+4)-1 |
(のため、スタックに入れる |
| 4 | *( | 2 3 | +4)-1 |
3のためキューに入れる |
| 5 | *(+ | 2 3 | 4)-1 |
+のためスタックに入れる |
| 6 | *(+ | 2 3 4 | )-1 |
4のためキューに入れる |
| 7 | *(+ | 2 3 4 + | -1 |
)のため(が来るまでスタックからpopする。まず+をキューに入れる |
| 8 | * | 2 3 4 + | -1 |
(は削除 |
| 9 | 2 3 4 + * | -1 | トークンの次の演算子は-だが*のほうが優先度が高いため*をキューに入れる |
|
| 10 | - | 2 3 4 + * | 1 |
-をスタックに入れる |
| 11 | - | 2 3 4 + * 1 |
1をキューに入れる |
|
| 12 | 2 3 4 + * 1 - |
-をポップしキューに入れる |
置き換えと同時に計算する
操車場アルゴリズムによって2*(3+4)-1という式が2 3 4 + * 1 -という風に置き換わりましたが、置換の段階で計算が行われる事も多いみたいです。
上記の流れの中で実際に計算してみます。
| 順番 | スタック | 出力キュー | 式 | 説明 |
|---|---|---|---|---|
| 1 | 2 | *(3+4)-1 | 先頭から探索が始まる。2のためキューに入れる |
|
| 2 | * | 2 | (3+4)-1 |
*のため、スタックに入れる |
| 3 | *( | 2 | 3+4)-1 |
(のため、スタックに入れる |
| 4 | *( | 2 3 | +4)-1 |
3のためキューに入れる |
| 5 | *(+ | 2 3 | 4)-1 |
+のためスタックに入れる |
| 6 | *(+ | 2 3 4 | )-1 |
4のためキューに入れる |
| 7 | *( | 2 7 | -1 |
)のため(が来るまでスタックからpopする。スタックからは+が取得出来たため、出力キューから値を2つ(3,4)取り出し、それらを足し合わせた結果が出力キューに入れられる。7
|
| 8 | * | 2 7 | -1 |
(は削除 |
| 9 | 14 | -1 | トークンの次の演算子は-だが*のほうが優先度が高いため、出力キューの中のものを掛け合わせたものが出力キューに入る。14
|
|
| 10 | - | 14 | 1 |
-をスタックに入れる |
| 11 | - | 14 1 |
1をキューに入れる |
|
| 12 | 13 |
-をポップし、出力キューのものを2つ取得し、引き合わせたものが出力キューに入る。 |
逆ポーランド記法の応用方法
上記の例では、2*(3+4)-1といった、一度に2つまでの項を計算する前提でしたが、
このアルゴリズムの応用として、2*(3+4+5)など3つ以上の項の計算を行いたい時は、+の演算子を__3つ足し合わせる意味を持つ変数名__などで置き換えるなどの方法でどんな計算にも応用出来ます。
例として、2*(3+4+5)-1という式があったら、
2 3 4 5 add3 * 1 -といった風に+を何個足し合わせるという意味を持たせればこのような式も計算が可能になります。
こんな感じで、検索アルゴリズムや文字列の四則演算などにも応用し使用出来そうです。
実際に実装してみた
今回は入門という事で、簡単な12+3*4+9*(1+2)という式を例として実装しました。
Wikiにもある通り、置き換える時点で計算していってもいいみたいですが、今回は理解するために操車場アルゴリズムによって逆ポーランド記法に置き換えてから、計算するようにしています。
※また、今回は単純な計算にするために__括弧の中の項は2つまで、小数点は無し、文字は無し、二乗などは無し__を前提としてます。
import re
stack = []
outputStack = []
SPLITTER = re.compile(r'[\s]*(\d+|.)')
PARENTHESES = ['(', ')']
line = '12+3*4+9*(1+2)'
SYMBOLS = {
"*": {
"priority": 2,
"func": lambda x,y:x*y,
},
"/": {
"priority": 2,
"func": lambda x,y:x/y,
},
"+": {
"priority": 1,
"func": lambda x,y:x+y,
},
"-": {
"priority": 1,
"func": lambda x,y:x-y,
}
}
# 括弧判定
def isParentheses(s, **kwargs):
if 'index' in kwargs:
return s is PARENTHESES[kwargs['index']]
return s in PARENTHESES
# 記号判定
def isSymbol(s):
return s in SYMBOLS
# 数字判定
def isNum(s):
return s.isdigit()
# Symbolの優先度取得
def getPriority(s):
return SYMBOLS[s]['priority']
# Symbolの関数取得
def getFunc(s):
return SYMBOLS[s]['func']
# トークンに分ける
def tokenize(line):
return SPLITTER.findall(line)
def parse(tokenList):
"""
tokenListを逆ポーランド記法に変換する。
"""
for i in range(len(tokenList)):
token = tokenList.pop(0)
# 数字だったら出力スタックへpush
if isNum(token):
outputStack.append(token)
# 括弧始まりだったらスタックへpush
elif isParentheses(token, index=0):
stack.append(token)
# 括弧終わりだったら括弧始まりが来るまでpopして出力スタックへ追加
elif isParentheses(token, index=1):
for i in range(len(stack)):
symbol = stack.pop()
if isParentheses(symbol, index=0):
break
outputStack.append(symbol)
# 読み込んだトークンの優先度がスタックの末尾の優先度以下だったら
# スタックからポップして、出力スタックに追加してから、スタックにトークンを追加する。
elif stack and isSymbol(stack[-1]) and getPriority(token) <= getPriority(stack[-1]):
symbol = stack.pop()
outputStack.append(symbol)
stack.append(token)
# それ以外は普通にスタックにpush
else:
stack.append(token)
# 最後にスタックのものを全て出力スタックへ追加する。
while stack:
outputStack.append(stack.pop(-1))
return outputStack
def evaluate(parsedData):
"""
先頭から見ていって、記号だったらスタックから2つ取り出してそれらを計算した後出力スタックへ。
"""
cnt = 0
while len(parsedData) != 1:
if isSymbol(parsedData[cnt]):
targetIndex = cnt-2
symbol = parsedData.pop(cnt)
num1 = parsedData.pop(targetIndex)
num2 = parsedData.pop(targetIndex)
res = getFunc(symbol)(int(num1), int(num2))
parsedData.insert(targetIndex, res)
cnt = targetIndex+1
else:
cnt += 1
return parsedData[0]
def main():
print('式：', line)
tokenList = tokenize(line)
parsedData = parse(tokenList)
print('parsedData：', parsedData)
result = evaluate(parsedData)
print('result：', result)
if __name__ == '__main__':
main()
出力は以下のような感じです。
式： 12+3*4+9*(1+2)
parsedData： ['12', '3', '4', '*', '9', '1', '2', '+', '*', '+', '+']
result： 51
まとめ
操車場アルゴリズムによって、中置記法のものを後置記法に置き換える事で処理がしやすくなる事が分かった。
これを使って、xなどが入っている四則演算や括弧内に3つ以上の項がある四則演算、字句解析などに応用出来そう。