この演習では、 スタック（アルゴリズムＣ 第１巻 p.29） の操作方法について学び、そのプログラムを作成します。 キュー（アルゴリズムＣ 第１巻 p.34） については触れませんが、スタックを作ることができれば、 キューを作るのもそれほど難しいことではありません。
(1) 以下の式を逆ポーランド記法で表しなさい。
1 + 2 * 3 ( 1 + 2 ) * 3 ( 1 + 2 ) * ( 3 + 4 ) 1 + ( 2 + 3 ) * 4 + 5 (2) (1) の 4 で逆ポーランド記法で表したものを、 スタックを使って計算しなさい。 ただし、計算過程でのスタックの状態も書くこと。
(1) は
逆ポーランド記法（アルゴリズムＣ 第１巻 p.31）
に変換する問題です。
逆ポーランド記法は他にも
「後置記法」
「RPN (Reverse Polish Notation)」
「IPN (Inverse Polish Notation)」
などと呼ばれます。逆ポーランド記法は日本語表記と似ています。
例えば、1 + 2 を逆ポーランド記法で表すと
1 2 + になります。これは日本語で
「1 と 2 を足す(+)」 と書いたときの語順と同じです。
逆ポーランド記法にすると括弧が不要になります。
人間様には読みにくいかもしれませんが、
コンピュータが処理をする場合にはとても都合が良い表記方法です。
(2) では、以下の図を参考にして書いてみてください。
逆ポーランド記法で表された式を、 スタックを使って計算するプログラムを作成しなさい。 また、以下の条件を満たすこと。
実行例： % ./a.out Input data by Reverse Polish Notation: 12+34+* 1 1 2 3 3 3 3 3 4 3 7 21 Answer: 21
余裕のある人は、もう少しスタックっぽく表示 できるよう工夫しなさい。
スタックを配列で表現する場合、次の図のようになります。
処理の流れとしては、まず getchar() などの入力関数を使って
入力データを 1 文字読み込みます。そのデータが数字であれば、
整数型に変換してスタックにプッシュし、+-*/ などの
記号であれば、スタックから 2 回ポップして計算して、計算結果を
またプッシュします。
スタックを作るには、以下のような関数が必要になります。
void push(int x); スタックにデータ x をプッシュ（一番上に置く）する関数
int pop(); スタックからデータをポップ（一番上を取る）して、それを返す関数
int isempty(); スタックが空かどうかをチェックする関数。空なら 1、そうでないなら 0 を返す。
isempty() 関数は pop() 関数の中で使います。 ポップする前にスタックにデータが入っているかを調べる必要があるからです （空ならポップできない）。
まずはスタック操作のための関数を作成し、簡単なテストをしてみると良いでしょう。
int main(){
push(1);
push(2);
printf("poped value is %d.\n", pop());
printf("poped value is %d.\n", pop());
}
実行すると、このようになるのが正解です。
% ./a.out poped value is 2. poped value is 1.
また、次のような関数を作成すれば、プログラミングしやすくなるでしょう。
int dtoi(char c); 文字型としての数字を整数型に変換する関数
（例： '5' → 5）
void print_stack(); スタックの中身を表示する関数
逆ポーランド記法で表された式をスタックを使って計算するプログラム を作成しなさい。ただし、スタックを作るのにはリストを用いること。 他の条件については、問題２と同じで良い。 また、必要であれば 演習第 2 回 で使用した関数を用いなさい。
実行例： % ./a.out Input data by Reverse Polish Notation: 12+34+* 1 2 1 3 3 3 4 3 3 7 3 21 Answer: 21
問題２とは違い、リストを使ってスタックを表現します。
リストでのプッシュは、head の次にノードを挿入します。
リストでのポップは、head の次のノードを削除します。
また、リストを使うことによって、キューも同様に作ることができます。