電脳ミツバチのコンピュータ広報室

銀座の屋上菜園を耕しています。コンピュータ畑も耕します。

①-2スタック

スポンサーリンク

メモリの項で散々スタックの説明をしたがリストを使ったスタックの実装について説明する。
データ構造として最も重要なスタックだが、基本的な操作は2つだけで、プッシュとポップと言う概念からなる。プッシュはリストで言えば項目の挿入であり、ポップは項目の取出しである。
スタックを使った算術式を述べると
仮に
5*(((9+8)*(4*6)+7)と言う式
9+8をやってから4*6をやり続いて掛け算をしてから7を加え、最後に5を掛ける。
この手順をオペラントも含めて並べてみると

  1. 5を入れる。
  2. 9を入れる
  3. 8を入れる
  4. 9+8の答えを入れる
  5. 4を入れる
  6. 6を入れる
  7. 4*6の答えを入れる
  8. 9+8の答えと4*6の答えを掛けたものを入れる
  9. 7を入れる
  10. 9+8の答えと4*6の答えを掛けた答えに七を加える
  11. 5を掛ける

この手順をpushとpopで表すと

  1. push(5);
  2. push(9);
  3. push(8);
  4. push(pop()+pop());
  5. push(4);
  6. push(6);
  7. push(pop()*pop());
  8. push(pop()*pop());
  9. push(7);
  10. push(pop()+pop());
  11. push(pop()*pop());

こうなる。
pushとpopを除いて算術式で書くと

598+46**7+*

こうなることが分かる。
これをreverse Polish notation(逆ポーランド記法)もしくは後置記法と呼ぶ。
(これに対し通常の書き方をinfix(中置記法)という。)
逆ポーランドの利点は括弧が必要ではないことに尽きる。
これによりプッシュ、ポップの2つだけで簡単に算術式が書ける。
この一連の操作をリストを用いて実現する。