逆ポーランド電卓

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
turasan
記事: 21
登録日時: 6年前

逆ポーランド電卓

#1

投稿記事 by turasan » 6年前

現在、『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;
	    }
	}
    }
}

理解できないでいる箇所は、

コード:

 while ((c = getchar()) != EOF) {
	if (isdigit(c)) {
	    ungetc(c, stdin);
	    scanf("%ld", &x);
	    push(x);
	} 
の部分です。
自分の読み方としては、getchar()で一度入力させて、その入力が0~1の場合、ungetcでその数値をとりあえずストリームに戻しておいて、そのあとscanfで入力させる...
と読んだのですが、これだと最初のgetcharで入力した数値はスタックに積まれてないことになりませんか、、。
どのように解釈したらよいでしょうか。。

box
記事: 1747
登録日時: 9年前

Re: 逆ポーランド電卓

#2

投稿記事 by box » 6年前

turasan さんが書きました: その入力が0~1の場合
どこに、そのように書いてあるでしょうか。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

turasan
記事: 21
登録日時: 6年前

Re: 逆ポーランド電卓

#3

投稿記事 by turasan » 6年前

isdigit(c)はcが数字(0~9)なら真(0以外の数)を返し、 c が数字以外なら偽(0)を返す標準ライブラリ関数ではないでしょうか、、。

box
記事: 1747
登録日時: 9年前

Re: 逆ポーランド電卓

#4

投稿記事 by box » 6年前

turasan さんが書きました:isdigit(c)はcが数字(0~9)なら真(0以外の数)を返し、 c が数字以外なら偽(0)を返す標準ライブラリ関数ではないでしょうか、、。
確かにそうではあるのですが、先に書かれていた
turasan さんが書きました: 自分の読み方としては、getchar()で一度入力させて、その入力が0~1の場合
これをこのまま素直に読むと、getchar()による入力内容が0~1の場合、と解釈できてしまうのです。
getchar()の入力結果(つまり変数c)の内容を「isdigit()で数字かどうか判断して」
という一文があると誤解や勘違いを招かずにすむと思います。

さて、
当該のソースで行なっていることは、
getchar()で読み取った1文字が'0'~'9'の数字であるならば、
いったん入力ストリームに戻して、あらためてscanf()で数値として読み取り、
その数値をスタックに格納する、ということだと思います。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

turasan
記事: 21
登録日時: 6年前

Re: 逆ポーランド電卓

#5

投稿記事 by turasan » 6年前

ありがとうございます。
返信おそくなって申し訳ありません。

いったん読み取ったその1文字を、一度入力ストリームに戻してから、再びscanfで読み取ることに
どのようなメリットがあるんでしょうか、、。
入力ストリームに流さずに、そのまま直接、x = c;と書いて変数xに直接cを代入すればよいのではないか思ったのですが。

box
記事: 1747
登録日時: 9年前

Re: 逆ポーランド電卓

#6

投稿記事 by box » 6年前

turasan さんが書きました: いったん読み取ったその1文字を、一度入力ストリームに戻してから、再びscanfで読み取ることに
どのようなメリットがあるんでしょうか、、。
入力ストリームに流さずに、そのまま直接、x = c;と書いて変数xに直接cを代入すればよいのではないか思ったのですが。
どういうメリットがあるのかよくわからない or メリットなどない
と思われたのであれば、その、「直接 x = c; と書いてみる」方法で
どういう動きをするか、チェックしてみてはどうでしょうか。
本に書いてあるコードが、当該の問題を解くための唯一無二のコード『ではない』
わけで、「お~、本に書いてあるのより自分のコードの方がいい!」ということが
もしわかるのであれば、それはすばらしい体験となるでしょう。

ちなみに、スタックというのはデータ構造の一つです。
アルゴリズムではありません。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

turasan
記事: 21
登録日時: 6年前

Re: 逆ポーランド電卓

#7

投稿記事 by turasan » 6年前

すみません、自分で動かすのを怠っていました。
x = c;
と書き換えてコンパイルしてみたのですが。
これだと、getchar()でキーボードから数字を読み込んだとしても、「整数」としては認識されてないようです、、。
ただの「文字」ですよね、。
そこで、一度ストリームに戻してから、再びscanfで「整数」として読み込むということですね。。

box
記事: 1747
登録日時: 9年前

Re: 逆ポーランド電卓

#8

投稿記事 by box » 6年前

turasan さんが書きました: これだと、getchar()でキーボードから数字を読み込んだとしても、「整数」としては認識されてないようです、、。
ただの「文字」ですよね、。
混乱させてしまうとしたら申し訳ないのですが、「文字or文字コード」というのは、
要するに「小さい値の整数」のことです。
くだんの「直接 x = c; と書く」方法の直後で
xをprintfか何かで出力してみるとわかると思いますが、
おそらく、
'0' という数字を入れるとx = 48(16進で0x30)
'1' という数字を入れるとx = 49(16進で0x31)
'2' という数字を入れるとx = 50(16進で0x32)
(中略)
'9' という数字を入れるとx = 57(16進で0x39)
'+'という文字を入れるとx = 43(16進で0x2b)
'-'という文字を入れるとx = 45(16進で0x2d)
'*'という文字を入れるとx = 42(16進で0x2a)
'/'という文字を入れるとx = 47(16進で0x2f)
という結果を得るのではないでしょうか。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

box
記事: 1747
登録日時: 9年前

Re: 逆ポーランド電卓

#9

投稿記事 by box » 6年前

今回のプログラムでは、
'0'~'9', '+', '-', '*', '/'
を有効な入力として規定しています。
四則演算子の場合はそのまま素通りさせて、
スタックから2個の数値を取り出して所定の演算を行なうのに対し、
数字の場合は後で数値として扱いたいので、
'0'~'9'のいずれかの数字の入力をisdigit()で検知したら、
数値に変換するための準備としていったん入力ストリームに戻して
(つまり何も読まなかったことにして)から、あらためてscanf()で
数値として読み取る、という工程を踏んでいます。

上記の文章で、「数字」と「数値」を明確に区別している点に留意してください。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

turasan
記事: 21
登録日時: 6年前

Re: 逆ポーランド電卓

#10

投稿記事 by turasan » 6年前

ありがとうございました、
たしかに先ほどprintfでも試しに出力させていたのですが、
そのような数値が出てきました。

もともとの質問も解決できました。

(次からは自分で動かしてから、トピック立たてるようにします、、。)

turasan
記事: 21
登録日時: 6年前

Re: 逆ポーランド電卓

#11

投稿記事 by turasan » 6年前

ありがとうございました

ISLe
記事: 2648
登録日時: 9年前
連絡を取る:

Re: 逆ポーランド電卓

#12

投稿記事 by ISLe » 6年前

例えば123という文字列が入力されたとき、'1'を読み出して数字と判定、戻したあと123という文字列をscanfで一気に数値として取り込みます。
二桁以上の数をバラバラに処理しなくて良いところがメリットだと思います。

turasan
記事: 21
登録日時: 6年前

Re: 逆ポーランド電卓

#13

投稿記事 by turasan » 6年前

なるほど、
ありがとうございます

閉鎖

“C言語何でも質問掲示板” へ戻る