プログラミング演習I

プログラミング演習II
2004年11月 30日(第6回)
理学部数学科・木村巌
前回までの復習


文字列とポインタ
文字列の操作

動的なメモリの確保
今日学ぶこと





関数ポインタ
教科書10.5から(p. 337~)
スタックというデータ構造と、配列を使ったス
タックの実現
逆ポーランド記法
逆ポーランド記法計算機の実装例(+, -のみ)
関数ポインタ





ポインタ変数とは、さまざまなオブジェクト(int,
char, double型の値や、それらの配列など)の
アドレスを格納する変数だった
アドレスとは、メモリ上の場所(通し番号)だっ
た
関数も、メモリ上に一定の場所を占める
関数のアドレスもある
関数ポインタ
関数ポインタの宣言

関数ポインタの宣言


(*関数ポインタ) (引数リスト);
たとえば


戻り値の型
int (*pM) (int x, int y);
pMは、int型を二つ取り、int型を返す関数へ
のポインタ
関数ポインタにアドレスを代入

関数ポインタに、関数のアドレスを代入する



たとえば



関数ポインタ = 関数名;
&はいらない(関数名は関数のアドレスそのもの)
pM = max;
pMは関数max()を指す
関数ポインタに代入された関数の呼び出し

(*pM)(5, 10) /* max(5, 10)と同じ */
関数ポインタの利用と応用


Sample16.cを入力して、コンパイル・実行して
みよう
関数ポインタの応用


たとえば、関数ポインタを配列に格納し、必要に
応じて異なる関数を呼び出すことができる
Sample17.cを入力して、コンパイル・実行して
みよう
ポインタと配列の応用:スタック




これまで学んだ、ポインタと配列との関係の
応用として、スタック(stack)というデータ構造
を実装してみよう
スタックとは、ある型のデータをpush, popでき
るデータ構造
aをpush, bをpushすると、最初のpopでbが、次
のpopでaが得られる(First In, Last Out)
お皿やお盆を積み重ねたようなもの
スタックの概略図
aをpush
空
a
bを
push
cをpush
b
c
b
a
b
a
a
空のス
タック
popするとcが飛び
出し、残りが一つ筒
繰り上がる
スタックを配列により実現






例えば、文字列をpush, popできるスタックを
作るには?
char *の配列stack(長さdを持つ)を用意
int型の変数stackptr (スタックポインタ)を用意
最初はstackptr = 0と初期化
文字列sをpush: stackptr++; stack[stackptr] =
s;
stackをpopする:return stack[--stack];
スタックと配列
0
aをpush
a
bを
push
a
cをpush
cをpop. 2番目
の要素を返し
て、スタックポ
インタを減らす
1
2
3
4
スタッ
クポイ
ンタ =
0
b
a
b
c
a
b
c
次のpushの際に、2番目の要素cが上書
きされる
スタッ
クポイ
ンタ =
1
スタッ
クポイ
ンタ =
2
配列を使ったスタックの実装例

stack.c, stack.h, stack-example.cを参照
逆ポーランド記法(RPN)







逆ポーランド記法:Reverse Polish Notation
1 + 2 を、1 2 +のように記述する
1 + 2 – 3 なら 1 2 + 3 1 + 2 * 3なら 1 2 3 * +
(1 + 2) * 3なら 1 2 + 3 *
演算子の優先順位が決まっていれば、曖昧
さはない
通常の記述を、中間記法(infix notation)とい
う
逆ポーランド記法とスタックを用いた
計算

逆ポーランド記法で記述された式が与えられ
たら、先頭から読み出して




読み出した文字が数字ならスタックにpush
読み出した文字が演算子なら、その演算子の引
数の数だけスタックからpopし、演算結果をpush
読み出す文字が無くなったときに、スタックに1つ
だけ数字が残っていれば、それが結果
読み出す文字が無くなったときに、上の状態でな
ければ、式が間違っていたということ
例

1 2 + が与えられた式の場合




1をpush
2をpush
+なので、popした結果の2と、もう一度popした結
果1とを足した値3をpush
3が結果となる
例2

1 2 - 3 + が与えられた式の場合






1をpush
2をpush
- なので、1 - 2 = -1をpush.
式から 3をpush
+ なので、-1 + 3 = 2をpush
2が結果
stack.cを使って、逆ポーランド記法計
算機を実装
rpncalc-ez.cを参照
char *program[] = {“1”, “2”, “sub”, “3”, “add”};
は、1 2 – 3 + で、例2と同じもの

今日学んだこと





関数ポインタ
教科書10.5から(p. 337~348)
スタックというデータ構造と、配列を使ったス
タックの実現
逆ポーランド記法
逆ポーランド記法計算機の実装例(+, -のみ)
レポート課題
(1)1 + 3 – 5 を逆ポーランド記法で書け
(2) (1 + 3) * (2 + 4) を逆ポーランド記法で書け
(3・やや難) rpncalc-ez.cを改良して、掛け算も
可能なようにせよ.(2)の答えを、そのプログ
ラムで実際に計算せよ
(発展問題) 中間記法で書かれた式を、逆ポー
ランド記法に変換する手続きについて考え
てみよ.また、文献を調査し、結果をまとめ
よ.
レポート課題(続)



締め切り:2004年12月13日一杯(日本時間
で)
提出:メールで木村([email protected])まで.
感想などあると木村が喜びます
休講通知

12月7日(火)のプログラミング演習IIは休講
です(木村が出張のため)