プログラミング演習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が結果となる
例２

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は休講
です（木村が出張のため）

Download Report