JavaScriptを有効にしてください

操車場のアルゴリズム

中置記法から逆ポーランド記法への変換

 ·  ☕ 2 分で読めます
Photo by Pixabay from Pexels

Photo by Pixabay from Pexels

前回、逆ポーランド記法とその計算方法について書いた。

逆ポーランド記法 – ひとりごと2.0

今度は中置記法から逆ポーランド記法への変換の仕方をメモしておく。

中置記法
$ 2 + 3 \times 4 $

逆ポーランド記法
$ 2 3 4 \times + $

操車場のアルゴリズム

調べてみると中置記法から逆ポーランド記法への変換する、操車場のアルゴリズム(Shunting-yard algorithm)という有名なアルゴリズムがある。

操車場アルゴリズム - Wikipedia

ちなみに考案したのはエドガー・ダイクストラという人で、計算機科学の世界では相当有名な学者とのこと。
自分でもダイクストラ法というアルゴリズムの名前くらいは競プロの解説などで聞いたことがある。

手順

$ 2 3 4 \times + $

結果を出力するためのキューと、演算子を保存しておくためのスタックを用意する

左から順に文字を読んでいく

  • 数字ならキューにプッシュする
  • 演算子o1なら
    • スタックのトップに演算子o2が存在し、かつo2の優先順位がo1以上である限り、繰り返しo2をキューにプッシュする
    • スタックに演算子が存在しないか、o2の優先順位がo1より低いならo1をスタックにプッシュする
  • 文字がなくなった場合、スタックから演算子を繰り返し取り出してキューにプッシュする

※上記は数字と演算子のみで構成されるシンプルな場合

// 2 + 3 * 4

Q [2]
S []

Q [2]
S [+]

Q [2 3]
S [+]

Q [2 3]
S [+ *] <-* は + より優先順位が高い

Q [2 3 4]
S [+ *]

Q [2 3 4 *] <-stackからpop
S [+]

Q [2 3 4 * +] <-result
S []

Pythonで実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def expressionToRPN(ex):
    priority = {
        "+": 2,
        "-": 2,
        "*": 3,
        "/": 3
    }
    operatorStack = []
    outputQueue = []
    elements = expressionToList(ex)
    while len(elements) > 0:
        element = elements.pop(0)
        # element is a number
        if type(element) == int:
            outputQueue.append(element)
            continue
        
        # element is an operator
        while len(operatorStack) != 0 and priority[operatorStack[-1]] >= priority[element]:
            outputQueue.append(operatorStack.pop())
        
        operatorStack.append(element)
    
    while len(operatorStack) > 0:
        outputQueue.append(operatorStack.pop())
    
    return outputQueue

if __name__ == '__main__':
	print(expressionToRPN('2+3*4'))
	# Output: [2, 3, 4, '*', '+']
共有

関連記事