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