Shunting Yard Algorithmについて
Shunting Yard Algorithmは、オランダの計算機科学者のダイクストラ(Edsger W. Dijkstra)が考案したアルゴリズムです。
60才くらいのアルゴリズムです。
これは、mathematical expressionの変換に関するものです。
mathematical expressionの表現方法としては、以下があります。
-
- 1 2: prefix notation
- 1 + 2: infix notation
- 1 2 +: postfix notation
postfix notationは特に、Reverse Polish Notationと呼ばれることもあります。
Shunting Yard Algorithmは、Infix Notationでの表現をReverse Polish Notationでの表現に変換するものです。
wikiのページは以下です。
Compilerは、プログラム中のalgerbraic expressionsを評価するときにReverse Polish Notationを使用することが知られています。このためこのような変換アルゴリズムが必要とされます。
Reverse Polish Notationの特徴ですがthe operators follow their operandsです。
これは3 4 + 5 * + instead of (3 + 4) * 5のようなことです。
加えて、Reverse Polish Notationではparenthesesが存在しません。
infix -> RPN
アルゴリズムの全容を示します。
inputはthe expression is given as a sequence of tokensを想定します。constants (つまりnumbers), variable(x, y, z, etc.), +, -, ÷, x, ^、そしてleft bracket ( , right bracket ) です。
outputは、a sequence of tokensです。
constants, variable(x, y, z, etc.), +, -, ÷, x, ^であって、no bracketsです。
The order of constants and variables don't change in this algorithm.
We change only the order of operators and we remove all brackets.
このAlgorithmについては、stackを利用します。This stack holds operators not yet added to the output.
The algorithm reads each token from left to right そして何かします。
- If the token is an operand (constant or variable), it is copied directly to the output.
- It the token is an operator, it is pushed onto the stack. However it is based on the precedences of the operands on the top of the stack.
ここで、operandsの優先順位のruleを示します。
| operator | precedence | associativity |
|---|---|---|
| ^ | 3 | Right |
| * | 2 | Left |
| ÷ | 2 | Left |
| + | 1 | Left |
| - | 1 | Left |
Associativityは このへんにかいています。これは要するにどちらから計算するか、というものです。
乗法の場合は、右から計算します。これは4^3^2を計算する場合、右から4^3^2 => 4^9のようにしていくことです。
アルゴリズム
Example
3 + 4 * 2 ÷ (1-5)^2^3
という式をRPNに変換してみます。
左から読んでいきます。
| Token | 作業 | output | stack | メモ |
|---|---|---|---|---|
| 3 | outputに追加 | 3 | からっぽ | |
| + | stackに追加 | 3 | + | |
| 4 | ouputに追加 | 3 4 | + | |
| * | stackに追加 | 3 4 | +,* | *は+よりprecedenceが高い |
| 2 | outputに追加 | 3 4 2 | +,* | |
| ÷ | stackからoutputに取り出す | 3 4 2 * | + | ÷ と+は同じprecedence |
| stackに追加 | 3 4 2 * | +,÷ | ÷は+よりprecedenceが高い | |
| ( | stackに追加 | 3 4 2 * | +,÷,( | |
| 1 | ouputに追加 | 3 4 2 * 1 | +,÷,( | |
| - | stackに追加 | 3 4 2 * 1 | +,÷,(, - | |
| 5 | outputに追加 | 3 4 2 * 1 5 | +,÷,(, - | |
| ) | stackからoutputに取り出す | 3 4 2 * 1 5 - | +,÷,( | until ( found |
| stackから取り出す | 3 4 2 * 1 5 - | +,÷ |
(をdiscard |
|
| ^ | stackに追加 | 3 4 2 * 1 5 - | +,÷, ^ |
^は÷よりもprecedenceが高い |
| 2 | outputに追加 | 3 4 2 * 1 5 - 2 | +,÷, ^ | |
| ^ | stackに追加 | 3 4 2 * 1 5 - 2 | +,÷,^,^ |
^ is right associativity |
| 3 | stackに追加 | 3 4 2 * 1 5 - 2 3 |
tokenが終わったので、次にstackにあるものをoutputに追加していきます。
3 4 2 * 1 5 - 2 3 ^ ^ ÷ +
これで終わります。
評価
これの評価の仕方ですが、we use a stack again but we store operands instead of operators.
The expression is processed from left to right.
For each token in the RPN expression do. if the token is an operand, then we push it onto the stack else it is operators, then
operand2 := pop from the stack
operand1 := pop from the stack
result := operand1 operator operand2
we push result onto the stack. Finally, we get result when we pop the stack.
これを評価してみましょう。左から右に読んでいきます。
3 4 2 * 1 5 - 2 3 ^ ^ ÷ +
*までstackに詰めます。
Stack: 3,4,2
*まできたら、2と4を取り出しoperandとし、*をoperatorとして計算したものを、stackにいれます。
Stack: 3,4*2
1,5をStackに詰めます。
Stack: 3,8,1,5
-まできたら、1と5を取り出しoperandとし、-をoperatorとして計算したものを、stackにいれます。
Stack: 3,8,1-5
2,3をStackに詰めます。
Stack: 3,8,-4,2,3
^まできたら、2と3を取り出しoperandとし、^をoperatorとして計算したものを、stackにいれます。
Stack: 3,8,-4,2^3
さらに^があるので、2^3と-4を取り出しoperandとし、^をoperatorとして計算したものを、stackにいれます。
Stack: 3,8,-4^8
÷があるので、-4^8と8を取り出しoperandとし、÷`をoperatorとして計算したものを、stackにいれます。
Stack: 3,8/ (2^16)
+があるので、8/ (2^16)と3を取り出しoperandとし、+`をoperatorとして計算したものを、stackにいれます。
Stack: 3 + 2^(-13)
これが計算結果です。
Discussion