逆ポーランド記法への変換２


　カッコのある式の変換は、カッコの中にある式がそれだけで完結するように変換しなければなりません。
　ですのでまず左カッコ'('が来たら脇に並べます。そしてそのカッコに対応する右カッコ')'が来たら、式が終了したときのように脇に積んである演算子を左カッコが来るまで一つずつ手元に並べます。
　左カッコが来たら、それは右カッコとペアにして捨ててしまいます。 
　手元               (1 + 4) * (3 + 7) / 5
　脇　                                      ;スタート
　
　手元               1 + 4) * (3 + 7) / 5
　脇　(                                     ;左カッコ
　
　手元 1 4           ) * (3 + 7) / 5
　脇　( +                                   ;普通に進める
　
　手元 1 4           * (3 + 7) / 5
　脇　( + )                                 ;右カッコがきた
　
　手元 1 4 +         * (3 + 7) / 5
　脇　( )                                   ;左カッコまで演算子一つずつ手元へ移す
　
　手元 1 4 +         * (3 + 7) / 5
　脇　                                      ;カッコ対消滅
　
　手元 1 4 +         3 + 7) / 5
　脇　 * (                                  ;通常の演算子と左カッコ
　
　手元 1 4 + 3 7     / 5
　脇　 * ( + )                              ;右カッコが来るまで普通どおり。
　
　手元 1 4 + 3 7 +   / 5
　脇　 * ( )                                ;また左カッコまで演算子一つずつ手元へ移す
　
　手元 1 4 + 3 7 +   / 5
　脇　 *                                    ;またカッコ対消滅
　
　手元 1 4 + 3 7 +   5    
　脇　 * /                                  ;通常処理
　
　手元 1 4 + 3 7 + * 5  
　脇　 /                                    ;通常処理
　
　手元 1 4 + 3 7 + * 5 /
　脇　                                      ;残った演算子をつけて終了

　まとめるとアルゴリズムはこのようになります。
　
　準備として、変換する式と結果収容用バッファと、ワーク用のスタックを準備します。
　ここでのトークンとは、数式の解析においての最小単位をさします。具体的には数字や演算子のことです。
　

矢印前ページ トップ
 		次ページ矢印