プログラミング演習II レポート課題1 1 スタックを利用した逆ポーランド式の

プログラミング演習 II レポート課題 1
佐々木稔, 野口宏
平成 27 年 11 月 11 日
1
スタックを利用した逆ポーランド式の計算プログラムの
作成
本課題では，一次元配列や関数の使い方を中心に， C のプログラミングに対する理解
を確認するため，スタックを利用した逆ポーランド式の計算プログラムを作成する．
1.1
スタックとは
スタック (stack) とは，要素へのアクセス方法に制約のある抽象的なデータ型のひとつ
で，最後に入力したデータが先に出力される特徴を持つデータ構造である (図 1 参照)．例
えば，本を机の上に積み上げたり，取り出したりするような操作と同じように，データ
を入力する場合は、push 関数を呼び出すことで新しいデータが一番上に追加され，デー
タを取り出す場合は、pop 関数を呼び出すことで一番上にあるデータを優先的に取り出
す．このような入出力の方式は “Last In, First Out (LIFO)” または，“First In, Last Out
(FILO)” と呼ばれている．
push pop
sp
:
0
図 1: スタックの構造
1.2
逆ポーランド記法とは
逆ポーランド記法は，計算機で数式を処理する際に利用される記述方法のひとつであ
る．逆ポーランド記法は演算子を被演算子の後ろに配置する表現で，
「3 + 5」は「3 5 +」
1
に，
「(3 + 4) * 5」は「3 4 + 5 *」と表される．数学において利用される中置記法は，計
算順序を括弧を使って指定するのに対して，逆ポーランド記法は二項演算子だけで式が
構成されている場合，括弧を使うことなく演算を記述することができる．そのため，記
述された順序で処理を行うことができるため，プログラム上での計算処理において扱い
やすい性質を持つ．
レポート課題
2
2.1
[基本課題 1] スタックの作成
ここでは，スタックのデータ構造とそれを操作する関数の作成を行う．
スタックを実現するためには，以下に示す 2 つの変数をすべての関数において操作で
きるように “外部変数” として用意すればよい．
• 数値を格納する配列 stack
• スタックポインタ sp
スタックポインタは，スタックに現在入っている要素の中で一番上のものの位置 (配列の
要素番号) を指すものとする．
スタックに対する基本操作としては，以下の 4 つの関数を考える．
• スタックポインタを初期化する関数 init stack
• スタックにデータをひとつ入れる関数 push
• スタックからデータをひとつ取り出す関数 pop
• スタックに格納された値をすべて表示する関数 show stack
これらの操作による動作例を図 2 に示す．スタックポインタの初期化を行う関数 init stack
では，スタックに何も入っていないことを表すため sp を -1 に設定する．関数 push には
引数としてスタックに入れるべき数値を与えて呼び出す．関数 push の内部では，スタッ
クポインタ sp に 1 を加え，渡された数値がスタックに格納される．関数 pop は，スタッ
クポインタが現在指しているスタックの位置から数値を取り出し，スタックポインタ sp
から 1 を引いて，取り出した数値を関数の返り値として返す．
このプログラムが正しく動作することを確認するために，main 関数において，以下の
スタック操作を行い，スタックに格納されたデータの全体的な内容や pop 関数により取
り出される値を出力するテストプログラムを作成する．
{ push(9), pop(), push(8), push(7), pop(), push(6), pop(), push(5),
push(4), pop(), pop(), push(3), push(2), push(1), pop(), pop() }
また，上の操作以外で，各自で自由にスタック操作を考えて実行した結果も示す．
2
操作
push(1)
push(2)
pop()
push(3)
push(4)
pop()
スタックの中身
[1]
[1 2]
[1]
[1 3]
[1 3 4]
[1 3]
sp pop で取り出される値
0
1
0
2
1
2
1
4
図 2: push 関数、pop 関数によるスタックの値、sp の変化と戻り値
2.2
[基本課題 2] 標準入力からのスタック操作
基本課題 1 では，main 関数内でスタック操作の内容を記述していたため，操作を行う
際にはプログラムを書き換える必要があった．基本課題 2 は，その問題を解決するため
に標準入力からスタック操作命令を受け付けられるように改良を行う．
具体的な入力方法として，スタックにデータを入力する場合は ‘i’ を入力し，その後で
入力する数値を入力する．また，スタックからデータをひとつ取り出す場合は ‘o’ を入力
する，スタック操作がすべて終われば，入力の終了を表す ‘e’ を入力することでプログラ
ムが終了する．さらに，スタックに格納された全体的な内容を表示する場合は ‘s’ を入力
することで，入力時点でのスタックの内容が標準出力に表示される．
例えば，基本課題 1 においてテストプログラムでのスタック操作を上記の表現方法で
表すと，以下のデータ列として表現される．
i 9 o i 8 i 7 o i 6 o i 5 i 4 o o i 3 i 2 i 1 o o e
このデータ列を標準入力から受け取り，適切にスタック処理を行うプログラムを作成
する．このとき，スタックには数値のみしか格納できない制約やスタック処理における制
約など，多数の例外処理を行う必要がある．考えられるすべての例外に対してメッセー
ジを適切に出力し，異常終了処理で終わることができるように例外対策を行い，他の入
力を受け付けないような改良を同時に行う．このようなプログラムを作成し，それが正
しく動作することを確認する．
2.3
[標準課題 1] 逆ポーランド式の計算
ここでは，1 桁の自然数に限定した逆ポーランド式の計算プログラムを作成する．逆
ポーランド式で表現された数式を標準入力から受け取り，文字型配列 expr に格納する．
例えば，標準入力に以下の数式を入力する．
98+76*5/このとき，文字型配列 expr には以下のようにデータが格納されている．このとき，式の
終わりには ’\n’ が終了記号として含まれている．
3
図 3: スタックによる逆ポーランド式の計算処理例 (箱がスタック)
expr[] = {’9’, ’8’, ’+’, ’7’, ’6’, ’*’, ’5’, ’/’, ’-’, ’\n’};
この配列 expr を最初から順番にたどって計算を行い，配列の要素に ’\n’ が出現すれ
ば処理を終了し，計算結果を表示する．計算過程での処理は以下のようになる．
• 配列 expr の要素となる文字が ‘0’ ∼ ‘9’ であれば，数値に変換してスタックに積む．
• 要素が演算子 (‘+’, ‘-’, ‘*’, ‘/’) であれば，2 つの数値を取り出して演算を行い，そ
の結果を再びスタックに積む．
例として、逆ポーランド式を表す配列 {’9’, ’8’, ’+’} に対する計算処理を表現したものを
図 3 に示す。このとき，演算子 ‘-’ と ‘/’ については，最初に取り出した数値は引く数，
もしくは，割る数で，2 番目に取り出した数値が引かれる数，もしくは割られる数となる．
また，この課題では整数値のみを扱うので割り算 ‘/’ の結果は小数点以下を切り捨てた商
の数値を演算結果とする．
このプログラムが正しく動作していることを確認するため，上の逆ポーランド式を入
力したときにおける計算結果と，この式以外に各自で逆ポーランド記法を用いた式を文
字列として与えた結果についても実行し，処理結果が正しい計算結果となっていること
を確認する．なお，処理結果については，途中の計算状況やスタックの内容なども確認
できるように工夫する．
2.4
[標準課題 2] 2 桁以上の数を含む式の計算
標準課題 1 では，1 桁の自然数に限定したが，ここでは 2 桁以上の数値を扱えるよう
にプログラムを変更する．このとき，2 つの数値の間を区別できるように，標準入力とし
て与えた逆ポーランド式に数値間のみの区切り文字として ‘\’ を挿入し，区切り文字まで
はひとつの数値として扱うこととする．
このプログラムが正しく動作することを確認するために，以下の逆ポーランド式に対
して正しい計算結果が出力されることを示す．
11\12\13\14\15\16\17\18\19\20+-+-+-+-+4\28\16-2/*6/4
2.5
[発展課題 1] 他のスタック操作関数の作成
基本課題 1 において作成したスタックへの操作関数は push と pop の 2 種類で，これ
らの操作が一般的によく知られている．しかし，その他にもスタックに対する操作など
を行う関数が存在する．発展課題 1 では，スタックの操作をより幅広く行うための関数
を作成し，それらの関数を実際に利用する簡単な処理プログラムの作成も行う．作成す
る 4 つの関数を以下に示す．
1. スタックに格納された値の数を返す関数 stack size を作成する．
2. スタックのトップの値を関数値として返すが，その値はスタックから取り除かない
関数 peek を作成する．
3. スタックの上から n 個の値を回転するように入れ替える関数 rotate を作成する．
例えば，n = 3 としてスタックに 1，2，3 が順に格納されているとき，この順番を
2，3，1 と変化させる操作が行われる．
4. スタックの上から 1 番目と 2 番目にある 2 つの値を入れ替える関数 swap を作成
する．
2.6
[発展課題 2] 小数を含む式の計算
標準課題 2 では，複数桁の自然数に拡張したが，ここではさらに小数点以下の正の実
数値を扱えるようにプログラムを変更する．このとき，計算結果の表示は小数点以下第
5 位までとする．
このプログラムが正しく動作することを確認するために，以下の逆ポーランド式に対
して正しい計算結果が出力されることを示す．
1.3\3\5/+0.5-
5

Download Report