スタックの操作(電卓への応用が可能)
スタックはプログラミングでは非常に重要なデータ構造である。大学の情報学科では必ず教える内容です。プログラムの解析などで使い、数式の計算に使うと非常に便利です。ここでは数式の計算例を示すことにより、スタックの扱い方を説明いたします。
スタックは先入れ後出し法をとるデータ構造です。例えばレストランでキレイに洗った皿を一つひとつ積み上げて行って、必要になったら上から一枚一枚とっていくような皿の積み上げ管理をする道具といえばよろしいでしょうか。コンピュータのメモリでいえば配列のような形をしていて、始めは空で、データは上に入れ、上からとるようなデータの出し入れをする配列(リスト)であると言える。ただし、スクラッチではこの配列をリストで実現する。リストはデータを入れていくと下向きに成長する。例えばスタックに3を入れて(PUSHして)5を入れる(PUSHする)と図stack0-1のようになる。このスタックの名前はstackである。
スタックを使用して数式を計算する場合、数式を左から順番に見ていて、直ちに計算できる数値があれば、それをスタックにPUSHします。多くの場合二つの数値をPUSHします。
そのあと、その2数の間の計算を行い、スタックのTOPにあった二つの数値をPOP(スタックがら取り除く)して、さらに計算結果をPUSHします。これを繰り返して、最後の計算を行うと結果がスタックのTOPに残ります。
例1 2+3は以下のように行われる。
操作とプログラムの処理
図 stack1は始めスタックが空であることを示す。
- 2をクリック---2が変数rに入る
- P(PUSH)をクリック---変数rの内容がスタックのトップに入る(図stack2)
- 3をクリック---3が変数rに入る
- P(PUSH)をクリック---変数rの内容がスタックのトップに入る(図stack3)
- +をクリック---プログラムが以下のように働いて結果がスタックのトップに残る
・スタックのトップをポップして、変数Bに入れる。
・スタックのトップをポップした、変数Aに入れる。
・C=A-Bを計算(=5)
・Cをスタックにプッシュ(図stack4)
|
例2 (7+3)/(5-2)は以下のように行われる。
操作とプログラムの処理
図 stack5は始めスタックが空であることを示す。
1)7をクリック---7が変数rに入る
2)P(PUSH)をクリック---変数rの内容がスタックのトップに入る(図stack6)
3)3をクリック---3が変数rに入る
4)P(PUSH)をクリック---変数rの内容がスタックのトップに入る(図stack7)
5)+をクリック---プログラムが以下のように働いて結果がスタックのトップに残る
・スタックのトップをポップして、変数Bに入れる。
・スタックのトップをポップした、変数Aに入れる。
・C=A-Bを計算(=10)
・Cをスタックにプッシュ(図stack8)
6)5をクリック---5が変数rに入る
7)P(PUSH)をクリック---変数rの内容がスタックのトップに入る(図stack9)
8)2をクリック---2が変数rに入る
9)P(PUSH)をクリック---変数rの内容がスタックのトップに入る(図stack10)
10)ーをクリック---プログラムが以下のように働いて結果がスタックのトップに残る
・スタックのトップをポップして、変数Bに入れる。
・スタックのトップをポップした、変数Aに入れる。
・C=A-Bを計算(=3)
・Cをスタックにプッシュ(図stack11)
11)/をクリック---プログラムが以下のように働いて結果がスタックのトップに残る
・スタックのトップをポップして、変数Bに入れる。
・スタックのトップをポップした、変数Aに入れる。
・C=A*Bを計算(=3.333333)
・Cをスタックにプッシュ(図stack12)