ALDS1_3_A スタックをC++で解いてみた[AIZU ONLINE JUDGE]

AIZU ONLINE JUDGE

こんにちは! mnbd(@mnbbbbbd)です。

AIZU ONLINE JUDGEの「ALDS1_3_A スタック」を解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文

逆ポーランド記法は、演算子をオペランドの後に記述する数式やプログラムを記述する記法です。例えば、一般的な中間記法で記述された数式 (1+2)*(5+4) は、逆ポーランド記法では 1 2 + 5 4 + * と記述されます。逆ポーランド記法では、中間記法で必要とした括弧が不要である、というメリットがあります。

逆ポーランド記法で与えられた数式の計算結果を出力してください。

入力
1つの数式が1行に与えられます。連続するシンボル(オペランドあるいは演算子)は1つの空白で区切られて与えられます。

出力
計算結果を1行に出力してください。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_A

解答

#include <bits/stdc++.h>
using namespace std;

#define MAX 100000

class Stack {
  private:
    int values[MAX];
    int top;

  public:
    Stack();
    void push(int x);
    int pop();
    bool is_full();
    bool is_empty();
};

Stack::Stack() { top = 0; }

void Stack::push(int x) {
    top++;
    values[top] = x;
}

int Stack::pop() {
    top--;
    return values[top + 1];
}

bool Stack::is_full() { return top >= MAX - 1; }

bool Stack::is_empty() { return top == 0; }

int main() {
    string str;
	Stack s;
	while (cin >> str) {
        int a, b;
        if (str.at(0) == '+') {
            a = s.pop();
            b = s.pop();
            s.push(b + a);
        }
        else if (str.at(0) == '-') {
            a = s.pop();
            b = s.pop();
            s.push(b - a);
        }
        else if (str.at(0) == '*') {
			a = s.pop();
			b = s.pop();
			s.push(b * a);
        }
        else {
            s.push(atoi(str.c_str()));
        }
    }

    cout << s.pop() << endl;
    return 0;
}

ハマったポイント

配列の確保数

Stackクラスのvalues配列の確保数で、数値を大きくしすぎてしまうと何も出力されないエラーに悩まされました。

char型の入力とswitch文

入力の受け取りをchar型変数にしてしまい、二桁以上の数字を計算できないという点でもミスがりました。

当初はchar型変数でswitch文を使い、演算子と数値を分岐していたのですが、char型をstring型に変えたことでそのまま単純にswitch文が使えず、if文に修正しました。

string型の文字列に対して単純にswitch文を使って文字を分岐できないことを知りました。

感想

データ構造のスタックの問題でしたが、それ以外の文法でつまずいてしまったという感じでした。

まとめ

AIZU ONLINE JUDGEの「ALDS1_3_A スタック」を解いてみましたので、その回答と解説をご紹介いたしました。

少しずつですが、プログラミングの勉強をしています。
まだ初心者ですが、よかったらつながっていただけると嬉しいです。
Twitterアカウント(@mnbbbbbd

以上です。
読んでいただきありがとうございました!