Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の3_A問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#3「基本データ構造」では、スタック、キュー、リストを学びます。
問題（3_A: Stack）
問題はリンク先をご覧ください。
スタックについて学びます。
スタックについて
後入れ先出し（LIFO: Last-In First-Out）ができるデータ構造です。値を格納する push と値を取り出す pop の典型的な実装は以下となります。
#define N 200
int st[N];
int sp = 0;
void push(int n)
{
st[sp] = n;
++sp;
}
int pop(void)
{
--sp;
return st[sp];
}配列 st と次に値を格納する場所を sp（Stack Pointer）で管理します。sp が指す場所は、「最後に値を入れた場所」と「次に値が入る場所」の2通りの実装があります。上記の例は、sp は「次に値が入る場所」を指しています。このため以下となっています。
- push : 値を格納してから sp をインクリメント
- pop : 値を取り出す前に sp をデクリメント
上記の実装では、スタックが空のときに pop したり、すでにスタックを使いきっている場合に push した場合に、配列として確保している範囲外にアクセスします。これは好ましくありません。多くの実装では、isEmpty や isFull のような関数を実装して、以下のように配列外参照を避けます。この実装例では、文字列を出力しています。実際には、例外を発生させたり、エラー値を返すなどします。
#define N 200
int st[N];
int sp = 0;
bool isFull()
{
return sp == N;
}
bool isEmpty()
{
return sp == 0;
}
void push(int n)
{
if (isFull()) {
cout << "Stack is full." << endl;
return;
}
st[sp] = n;
++sp;
}
int pop(void)
{
if (isEmpty()) {
cout << "Stack is empty." << endl;;
return -1;
}
--sp;
return st[sp];
}C++ プログラム例（ALDS1 3_A）
スタックを使って逆ポーランド記法の簡単な計算機を作ります。逆ポーランド記法の場合、数字だけをスタックに格納することによって実現できます。
具体的な演算処理は以下となります。
- 演算子 + : pop して値 n2 と値 n1 を取得します。n1 + n2 を push します（26ー29行目）。
- 演算子 – : pop して値 n2 と値 n1 を取得します。n1 – n2 を push します（30ー33行目）。
- 演算子 * : pop して値 n2 と値 n1 を取得します。n1 * n2 を push します（34ー37行目）。
- 数字 : 上記の演算子でない場合は数字であるため、atoi で変換した値を push します（39行目）。
問題としては正しい式が入力として与えられるため、スタックのエラー処理を省略しました。以下が、最終的なC++プログラムとなります。
#include <iostream>
#include <string>
using namespace std;
#define N 200
int st[N];
int sp = 0;
void push(int n)
{
st[sp] = n;
++sp;
}
int pop(void)
{
--sp;
return st[sp];
}
int main()
{
string s;
while (cin >> s) {
int n1, n2;
if (s == "+") {
n2 = pop();
n1 = pop();
push(n1 + n2);
} else if (s == "-") {
n2 = pop();
n1 = pop();
push(n1 - n2);
} else if (s == "*") {
n2 = pop();
n1 = pop();
push(n1 * n2);
} else {
push(stoi(s));
}
}
cout << pop() << endl;
return 0;
}標準ライブラリ stack を使う。
「プログラミング応用」（ITP2）の2_A問題で、標準ライブラリとして実装されている stack を紹介しました。
標準ライブラリの実装と異なるのは、pop は値を破棄するだけです。値を取得するためには、top を呼び出します。その後で pop を呼び出しています。より詳しい解説は参照先の記事を読んでください。
標準ライブラリ stack を使ったプログラムは以下となります。
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
stack<int> st;
string s;
while (cin >> s) {
int n1, n2;
if (s == "+") {
n2 = st.top();
st.pop();
n1 = st.top();
st.pop();
st.push(n1 + n2);
} else if (s == "-") {
n2 = st.top();
st.pop();
n1 = st.top();
st.pop();
st.push(n1 - n2);
} else if (s == "*") {
n2 = st.top();
st.pop();
n1 = st.top();
st.pop();
st.push(n1 * n2);
} else {
st.push(stoi(s));
}
}
cout << st.top() << endl;;
return 0;
}上記プログラムはどちらも、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
トピック#3では、スタック、キュー、リストを学びます。多くの場合、これらの機能は標準ライブラリを通して使うため具体的な実装は知らなくても気にならないかもしれません。ただし、それぞれのデータ構造を自分で実装することによって、データ構造の理解が深まると考えています。
引き続き、ALDS1 の問題を紹介していきます。
