スタックと逆ポーランド記法<ハードウェアとソフトウェア<Web教材<木暮仁

Web教材一覧ハードウェアとソフトウェア

スタックと逆ポーランド記法

キーワード

スタック、キュー、逆ポーランド記法


キューとスタック

       ──┐         push ──┐  ┌─→ pop
         │             │  │
      : │↓   │        │↓  ││
        ├────┤        ├────┤        ┌────┐
      11│データ5│       0│データ5│       0│データ1│
        ├────┤        ├────┤        ├────┤
      12│データ4│       1│データ4│       1│データ2│
        ├────┤        ├────┤        ├────┤
      13│データ3│       2│データ3│       2│データ3│
        ├────┤        ├────┤        ├────┤
      14│データ2│       3│データ2│       3│データ4│
        ├────┤        ├────┤        ├────┤
      15│データ1│       4│データ1│       4│データ5│
        ├────┤        ├────┤        ├────┤
      : │   ││       :│    │       :│↑  ││
            │                        │  │
            └─→                  push ──┘  └─→ pop
         キュー           スタック          スタック
         FIFO          LIFO      (Javascriptでのイメージ)

配列の特殊な構造に、キュースタックがあります。
 キューは、FIFO(First In First Out:先入れ先出し)方式で、待ち行列ともいいます。プリンタへのスプールによる出力処理やデータを入力された順番通りに処理するときなどに用いられます。
 それに対して、スタックは、LIFO(Last In First Out:後入れ先出し)方式です。新しいデータを入れる(Push)と、それまでのデータが下に押し下げられ、取り出すとき(Pop)ときは、1番上のデータが取り出され、2番目以降のデータが上に押し上げられます。

スタックの実験

Javascriptでは、データの入る配列名を「スタック」とすれば、push, popは、
   スタック.push(データ);  スタック.pop();
の形式で記述します。
 しかし、Javascriptでは、配列の末尾にpushし、末尾要素をpopする仕様になっているので、後入れ先出しであることは同じですが、むしろ上右図のようなイメージになります。

適宜、push, popを行ってください(clearはスタックを空にする操作 stack = []; です)。

命令(push | pop | clear) (pushのとき)データ

スタックの利用

コンピュータでは、スタックが広い分野で用いられています。

逆ポーランド記法との関係

逆ポーランド記法
数学の一般的な記法での数式 A+B×C を計算するには、発生順序により「(A+B)×C」とするのは誤りです。日本語では「AにBにCを×したものを+する」ことになりますが、その順に「ABC×+」と記述する記法を逆ポーランド記法といいます。
 もう少し複雑な例にして、数式を逆ポーランド記法にする手順を説明します。
  数式 A+B×(C+D)+E は、演算の優先順位を( )で明示すれば、
   ((A+(B×(C+D)))+E)
になります。
 最も深い( )から、数式を逆ポーランド記法に置き換えていきます。
   ((A+(B×(C+D)))+E)
          └─①─┘
           CD+
       └───②───┘
          BCD+×
    └─────③─────┘
         ABCD+×+
   └─────④─────────┘
         ABCD+×+E+

となり、逆ポーランド記法の
   ABCD+×+E+
になります。
 なお、これを木構造(演算木)を用いて表現することもできます。
練習問題
  問題1: (A+B)×(C-D) → AB+CD-×
  問題2: A/(B-C)+D  → ABC-/D+
スタックによる計算方法
数学での記法を逆ポーランド記法に変換すれば、スタックを利用して簡単に計算することができます。
そのルールは、次の通りです。
   逆ポーランド記法で記述した数式を左から順番に処理する。スタックは空である。
   数値ならば、スタックに Push する
   演算子ならば、
     スタックの1番上の数値を Pop して、その数値をXとする。
     新しくスタックの1番上にきた数値をYとして、YにXを演算する。
     その結果をYに代入する。
   数式がなくなったとき、スタックには唯一の数値が残っており、それが数式の結果である。
 このように、逆ポーランド記法では、+×や( )などの優先順位を考慮する必要がなく、式の解釈が簡単になり、スタック操作だけで行えるので、初期の電卓では逆ポーランド記法の順に入力するものもありました。また、コンパイラで数式を解釈するときにも利用されています。
例題
「ABC/-」を例にして説明します。
  Step1:Aを Push する。
  Step2:Bを Push する。
  Step3:Cを Push する。
  Step4:/になった。Cが Pop され、スタックの最上段がBになる。
    最上段の値を B/C の計算結果に置き換える。
  Step5:-になった。B/C が Pop され、スタックの最上段がAになる。
    最上段の値を A-(B/C) の計算結果に置き換える。
    数式がなくなったので、計算結果は A-(B/C) となる。
スタックの状況は、次のようになります。
    Step1  Step2  Step3  Step4   Step5
     A   B   C   /    -
   ┌───┬───┬───┬───┬──────┐
 0 │ A │ B │ C │B/C│A-(B/C)│
   └───┼───┼───┼───┼───┬──┘
 1     │ A │ B │ A │   └ 計算結果
       └───┼───┼───┘
 2         │ A │
           └───┘
実験

逆ポーランド記法の数式を与えて数学記法に変換します。変数は英字1文字とします。
・数学記法で( )が煩雑についていますが、プログラムを単純にしたからです。
・下記のkと例題の番号が逆になっている理由は、上述「スタックの実験」を参照してください。

逆ポーランド記法 →数学記法