操車場アルゴリズム
読み込むべきトークンがある間、以下を繰り返す(ここで示すアルゴリズムには、中置記法の演算子の他、atan2(1, 2) といったような(すなわち、前置で括弧と引数セパレータによる引数リストが引き続いている)「関数」の扱いも含まれている)。 トークンを1つ読み込む。 トークンが数値の場合、それを出力キューに追加する。 トークンが関数の場合、それをスタックにプッシュする。 トークンが関数の引数セパレータ(カンマなど)の場合 スタックのトップにあるトークンが左括弧となるまで、スタックから演算子をポップして出力キューに追加する動作を繰り返す。左括弧が出てこない場合、引数セパレータの位置がおかしいか、左右の括弧が不一致となっている(エラー)。 トークンが演算子 o1 の場合 スタックのトップに演算子トークン o2 があり、o1 が左結合性(英語版)で、かつ優先順位が o2 と等しいか低い場合、あるいは、o1 の優先順位が o2 より低い場合、以下を繰り返す。 o2 をスタックからポップし、出力キューに追加する。 o1 をスタックにプッシュする。 トークンが左括弧の場合、スタックにプッシュする。 トークンが右括弧の場合 スタックのトップにあるトークンが左括弧になるまで、スタックからポップした演算子を出力キューに追加する動作を繰り返す。