プログラミング演習II 2004年11月 30日（第6回） 理学部数学科・木村巌

前回までの復習 文字列とポインタ 文字列の操作 動的なメモリの確保

今日学ぶこと 関数ポインタ 教科書10.5から（p. 337～） スタックというデータ構造と、配列を使ったスタックの実現 逆ポーランド記法 逆ポーランド記法計算機の実装例（+, -のみ）

関数ポインタ ポインタ変数とは、さまざまなオブジェクト（int, char, double型の値や、それらの配列など）のアドレスを格納する変数だった アドレスとは、メモリ上の場所（通し番号）だった 関数も、メモリ上に一定の場所を占める 関数のアドレスもある 関数ポインタ

関数ポインタの宣言 関数ポインタの宣言 たとえば pMは、int型を二つ取り、int型を返す関数へのポインタ 戻り値の型　　(*関数ポインタ) (引数リスト); たとえば 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） お皿やお盆を積み重ねたようなもの

popするとcが飛び出し、残りが一つ筒繰り上がる スタックの概略図 popするとcが飛び出し、残りが一つ筒繰り上がる aをpush bをpush cをpush 空 a b c 空のスタック

スタックを配列により実現 例えば、文字列をpush, popできるスタックを作るには？ char *の配列stack（長さdを持つ）を用意 int型の変数stackptr （スタックポインタ）を用意 最初はstackptr = 0と初期化 文字列sをpush: stackptr++; stack[stackptr] = s; stackをpopする：return stack[--stack];

cをpop. 2番目の要素を返して、スタックポインタを減らす スタックと配列 1 2 3 4 a b c スタックポインタ = 0 aをpush bをpush スタックポインタ = 1 cをpush スタックポインタ = 2 cをpop. 2番目の要素を返して、スタックポインタを減らす 次のpushの際に、2番目の要素cが上書きされる

配列を使ったスタックの実装例 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. 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日一杯（日本時間で） 提出：メールで木村（iwao@sci.toyama-u.ac.jp）まで． 感想などあると木村が喜びます

休講通知 12月7日（火）のプログラミング演習IIは休講です（木村が出張のため）