C言語　ALDS1_3_A　Stack

問題

要点

• 逆ポーランド記法
  • 演算子をオペランドの後に記述する数式やプログラムを記述する記法。
  • (1+2)*(5+4)は 1 2 + 5 4 + *と記述される。

スタックを使って処理する

スタックの基本操作と制約

• push(x)　スタックの頂点に要素Xを追加します。
• pop()　スタックの頂点から要素を取り出す。
• isEmpty()　スタックが空かどうかを調べます。
• isFull()　スタックが満杯かどうかを調べます。

データの中で最後に入ったものが最初に取り出される。pop()によって取り出される要素は、最後にpushされた要素。

スタックの実装
スタックやその他のデータ構造の実装には配列やリストを使ったものなどいくつかの方法がある。今回は整数型のデータが格納されるスタックを配列を用いて実装する。

必要な変数と関数

• データを格納するための整数型1次元配列 :S
• スタックポインタを表す整数型変数 :top
  • topは最後の要素が格納されている場所を指す。
  • またtopの値はスタックの要素数に等しくなる。
• スタックに要素xを追加する関数 push(x)
  • topを１つ増やし、S[top]にxを代入する。
• スタックのトップから要素を取り出す関数 pop()
  • S[top]の値を返し、topを１つ減らす。

コード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top, S[1000];

void push(int x)
{
    top++;
    S[top] = x;
}

int pop(void)
{
    top--;
    return S[top + 1];
}

int main(void)
{
    int a, b;
    top = 0;
    char tmp[10]; //10^6の数が入ればいい

    while ( scanf("%s", tmp) != EOF )
    {
        if (tmp[0] == '+')
        {
            a = pop();
            b = pop();
            push(a + b);
        }
        else if (tmp[0] == '-')
        {
            b = pop();
            a = pop();
            push(a - b);
        }
        else if (tmp[0] == '*')
        {
            a = pop();
            b = pop();
            push(a * b);
        }
        else
        {
            push(atoi(tmp));
        }
    }
    printf("%d\n", pop());
    return 0;
}

ポイント

スペースが入っている文字列の入力は下記でやる。標準入力では、ファイルの終わりというものが存在しないので、ずっと処理待ち状態になる。

Ctrl + Dとかで抜けられる

while ( scanf("%s", tmp) != EOF )

所感

• だらだらやってしまった。
• EOFのところ、詰まってしまったがteratailで調べたら出てきた。
• また一度やり直す。

所要時間 90分

【復習】

• 2020/04/05
  • 記号と数字どちらでも取れるscanf("%s",s)を使う
  • 記号から判断して、数値を処理する
  • pop,pushの中も考える
  • 実装なし