ページ 11

配列のスタック

Posted: 2014年1月23日(木) 01:39
by Nect
お久しぶりです。

 現在、”アルゴリズムとデータ構造”の勉強をしています。使用している書籍は『定本Cプログラマのためのアルゴリズムとデータ構造』です。その書籍のP41に載っているList4.1のプログラムを実行したところ、「stack underflow」と表示されてしまい、何度実行してもその結果は変わりませんでした。P41に「逆ポーランド記法の数式を入力してリターンキーを押すと答えを表示します」と記述してあったのでEnterキーを押してみたものの、答えが表示されませんでした。
 「配列で実現するスタック」を理解したいのでご協力お願いします。

【実行環境】
windows8

コード:

 
/* Page 43 */

/* List 4.1  配列で実現したスタック(逆ポーランド電卓) */

/*
 * stack.c  配列でスタックを実現する
 */

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

typedef	   long	   ELEM;	   /* スタックの要素の型 */

#define	   STACK_SIZE  100	   /* スタックの大きさ */

ELEM   stack[STACK_SIZE];	   /* スタックの定義 */
int    n;			   /* スタックポインタ */


/* エラーメッセージをプリントしてexitする */
void   error(char *s)
{
    fprintf(stderr, s);
    exit(1);
}

/* スタックを初期化する */
void   init()
{
    n = 0;
}

/* スタックにデータを積む */
void   push(ELEM x)
{
    if (n >= STACK_SIZE)
	error("stack overflow\n");
    stack[n++] = x;
}

/* スタックからデータを降ろす */
ELEM   pop()
{
    if (n <= 0)
	error("stack underflow\n");
    return  stack[--n];
}

/* スタックが空かどうかを調べる */
/* 空なら1、空でなければ0を返す */
int    empty()
{
    return  n == 0;
}

/**********************************************************/

/* 逆ポーランド算卓プログラム */

main()
{
    int c;
    long    x, a, b;

    init();
    while ((c = getchar()) != EOF) {
	if (isdigit(c)) {
	    ungetc(c, stdin);
	    scanf("%ld", &x);
	    push(x);
	} else {
	    switch (c) {
	    case '+':
		b = pop(); a = pop();
		push(a + b);
		break;
	    case '-':
		b = pop(); a = pop();
		push(a - b);
		break;
	    case '*':
		b = pop(); a = pop();
		push(a * b);
		break;
	    case '/':
		b = pop(); a = pop();
		push(a / b);
		break;
	    case '\n':
		if (! empty())
		    printf("答えは%ldです\n", pop());
		init();
		break;
	    case ' ':
	    case '\t':
		/* 何もしないで読みとばす */
		break;
	    default:
		printf("不正な文字がありました。\n");
		printf("入力しなおして下さい。\n");
		while ((c = getchar()) != EOF && c != '\n')
		    ;
		break;
	    }
	}
    }
}


Re: 配列のスタック

Posted: 2014年1月23日(木) 03:21
by Nect
すみません。書き忘れていました。

追記.

どのようにすれば、「stack underflow」と表示せずに計算結果を表示することができますか?

Re: 配列のスタック

Posted: 2014年1月23日(木) 06:44
by box
逆ポーランド記法の数式の例を示してください。

こちらの環境(Windows XP、netbeans7.1.2)では、
例えば
2 3 +
と入力すると、想定どおり
答えは5です
と返ってきました。

Re: 配列のスタック

Posted: 2014年1月23日(木) 12:03
by Nect
box さんが書きました:逆ポーランド記法の数式の例を示してください。

こちらの環境(Windows XP、netbeans7.1.2)では、
例えば
2 3 +
と入力すると、想定どおり
答えは5です
と返ってきました。
5 3 +

4 5 *

7 2 -
と入力しました

Re: 配列のスタック

Posted: 2014年1月23日(木) 12:14
by Nect
実行結果を添付します。よろしくお願いします。

http://kie.nu/1CS8

Re: 配列のスタック

Posted: 2014年1月23日(木) 12:34
by 初級者
その入力のしかたでは、+などの演算子を
入力したときに演算対象の数値が
スタックに存在していない状態です。
stack underflow
が起きるのは当然です。

5 2 + <enter>
と入力してみてはどうでしょうか。

Re: 配列のスタック

Posted: 2014年1月23日(木) 12:48
by Nect
初級者 さんが書きました:その入力のしかたでは、+などの演算子を
入力したときに演算対象の数値が
スタックに存在していない状態です。
stack underflow
が起きるのは当然です。

5 2 + <enter>
と入力してみてはどうでしょうか。
実行できました。ありがとうございました。

Re: 配列のスタック

Posted: 2014年1月24日(金) 00:52
by かずま
Nect さんが書きました:実行できました。ありがとうございました。
3 1 4 2 + <Enter> と入力してみてください。満足できますか?