逆ポーランド記法の負の数への対応の仕方

回答率: 85.48%

質問するログイン新規登録

質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう！

新規登録して質問してみよう

ただいま回答率: 85.48%

トップ Cに関する質問

Q&A

解決済

2回答

2559閲覧

逆ポーランド記法の負の数への対応の仕方

総合スコア7

0グッド

0クリップ

投稿2020/06/08 17:41

編集2020/06/10 05:06

0

0

前提・実現したいこと

逆ポーランド記法で負の数にも対応するプログラムを完成させたいです。

発生している問題・エラーメッセージ

うまく計算できません。stack overflowが表示されます。

該当のソースコード

C
1#include <stdio.h>
2#include <stdlib.h>
3#include <ctype.h>
4#include <string.h>
5
6typedef long ELEMENT;
7
8#define STACK_SIZE 100
9
10ELEMENT stack[STACK_SIZE];
11int n;
12
13/*push関数**/
14void push(ELEMENT x)
15{
16    if (n>=STACK_SIZE){
17        printf("stack overflow");
18        exit(1);
19    }
20    stack[n++]=x;
21}
22
23/*pop関数*/
24ELEMENT pop()
25{
26    if (n<=0){
27        printf("stack underflow");
28        exit(1);
29    }
30    return stack[--n];
31}
32
33
34int is_digit(char *formula)
35{
36    if (*formula=='+' || *formula=='-'){
37        formula++;
38        if (*formula>='0' && *formula<='9'){
39            return 1;
40        }
41        return 0;
42    }
43    if (*formula>='0' && *formula<='9'){
44        return 1;
45    }
46    return 0;
47}
48
49int getnumber(char *formula)
50{
51    int sign=0;
52    if (*formula=='+'){
53        formula++;
54    }else if (*formula=='-'){
55        sign=1;
56        formula++;
57    }
58    while (*formula>='0' && *formula<='9'){
59        n=n*10+(*formula-'0');
60        formula++;
61    }
62    if (sign) return -n;
63    return n;
64}
65
66void calcuration(char *formula,FILE *fp)
67{
68    long a,b,x;
69    while(*formula){
70        if (is_digit(formula)){
71            
72            x=getnumber(formula);
73            
74            push(x);
75
76                    
77                
78        }else{
79            switch (*formula){
80                case '.':
81                    pop();
82                    break;
83                case '+':
84                    b=pop();a=pop();
85                    push(a+b);
86                    break;
87                case '-':
88                    b=pop();a=pop();
89                    push(a-b);
90                    break;
91                case '*':
92                    b=pop();a=pop();
93                    push(a*b);
94                    break;
95                case '/':
96                    b=pop();a=pop();
97                    push(a/b);
98                    break;
99                case ' ':
100                    break;
101                case '\n':
102                    printf("Answer:%ld",pop());
103                
104                default:
105                    printf("不正な入力です。\n");
106                    while (*formula){
107                            ;
108                    break;
109                    }
110                }
111            formula++;
112            }
113        
114        
115    }
116    fclose(fp);
117}
118
119
120int main(void)
121{
122    n=0;            /*スタックの初期化*/
123    
124    int s;
125    char formula[32]={0};
126    printf("数字データの時はスタックに積み、ピリオドの時はスタックから降ろします。(EOFで終了)\n");
127    printf("データ入力の方法を選んでください。\n0..キーボード/1..ファイル：");
128    scanf("%d",&s);
129    FILE *fp=stdin;
130    
131    if (s==1){
132        fp=fopen("data.txt","r");
133        if (fp==NULL){
134            printf("ファイルオープン失敗\n");
135            return 1;
136        }
137        fgets(formula,32,fp);
138        calcuration(formula,fp);
139    }else if (s==0){
140        printf("Input:");
141        scanf("%s",formula);
142        calcuration(formula,fp);
143    }
144    
145    
146    return 0;
147}
148
149
150
151#include <stdio.h>
152#include <stdlib.h>
153#include <ctype.h>
154
155typedef long ELEMENT;
156
157#define STACK_SIZE 100
158
159ELEMENT stack[STACK_SIZE];
160int n;
161
162/*push関数**/
163void push(ELEMENT x)
164{
165    if (n>=STACK_SIZE){
166        printf("stack overflow");
167        exit(1);
168    }
169    stack[n++]=x;
170}
171
172/*pop関数*/
173ELEMENT pop()
174{
175    if (n<=0){
176        printf("stack underflow");
177        exit(1);
178    }
179    return stack[--n];
180}
181
182int is_digit(char *formula)
183{
184    if (*formula=='+' || *formula=='-'){
185        formula++;
186        if (*formula>='0' && *formula<='9'){
187            return 1;
188        }
189        return 0;
190    }
191    if (*formula>='0' && *formula<='9'){
192        return 1;
193    }
194    return 0;
195}
196
197
198解決ver↓
199
200int main(void)
201{
202    n=0;            /*スタックの初期化*/
203    
204    int s;
205    printf("数字データの時はスタックに積み、ピリオドの時はスタックから降ろします。(EOFで終了)\n");
206    printf("データ入力の方法を選んでください。\n0..キーボード/1..ファイル：");
207    scanf("%d",&s);putchar('\n');
208    long x,a,b;
209    FILE *fp=stdin;
210    
211    if (s==1){
212        fp=fopen("data.txt","r");
213        if (fp==NULL){
214            printf("ファイルオープン失敗\n");
215            return 1;
216        }
217    }
218
219    char str[32]={0};
220    
221    
222    if (s==0)
223        printf("input:");
224        
225        while((fscanf(fp,"%s",str)!=EOF)){
226
227            if (is_digit(str)){
228                x=atoi(str);
229                push(x);
230
231            }else{
232                
233                switch (str[0]){
234                    case '.':
235                        pop();
236                        break;
237                    case '+':
238                        b=pop();a=pop();
239                        push(a+b);
240                        break;
241                    case '-':
242                        b=pop();a=pop();
243                        push(a-b);
244                        break;
245                    case '*':
246                        b=pop();a=pop();
247                        push(a*b);
248                        break;
249                    case '/':
250                         b=pop();a=pop();
251                         push(a/b);
252                         break;
253                    case ' ':
254                         break;
255                    case 'A':           /*Aで答えを表示*/
256                         if(n!=0)
257                         printf("答えは%ldです。",pop());
258                         n=0;
259                         break;
260                            
261                    default:
262                         printf("不正な入力です。\n");
263                        while ((fscanf(fp,"%s",str)!=EOF))
264                                ;
265                         break;
266                    }
267                }
268         }
269    fclose(fp);
270    return 0;
271}
272
273
274

試したこと

ネットにあるものも参考にさせてもらいました。formulaのインクリメントをいじってみたりしましたが効果出ず。。

補足情報（FW/ツールのバージョンなど）

Xcode Version 11.2 (11B52)

行動規範の内容に同意します

回答2件

0

解決済みになっているのでもう見てくれないかもしれませんが、
strtol を使うと簡単になるコードの例です。

C
1void calcuration(char *formula)
2{
3	n = 0;
4    while (*formula) {
5		char *p;
6		long x = strtol(formula, &p, 10);
7        if (p != formula) { push(x); formula = p; }
8        else {
9            switch (*formula++) {
10			case '.': pop(); break;
11			case '+': x = pop(); push(pop() + x); break;
12			case '-': x = pop(); push(pop() - x); break;
13			case '*': x = pop(); push(pop() * x); break;
14			case '/': x = pop(); push(pop() / x); break;
15			case ' ': break;
16			case '\n': printf("Answer:%ld\n", pop()); break;
17            default: printf("不正な入力です。\n");
18            }
19    	}
20	}
21}

追記
main も付けます。

C
1int main(void)
2{
3    printf("数字データの時はスタックに積み、"
4		"ピリオドの時はスタックから降ろします。(EOFで終了)\n"
5    	"データ入力の方法を選んでください。\n"
6		"0..キーボード/1..ファイル：");
7    char formula[256];
8    FILE *fp = stdin;
9    int s;
10    scanf("%d", &s);
11    if (s == 1) {
12        fp = fopen("data.txt", "r");
13        if (fp == NULL) { printf("ファイルオープン失敗\n"); return 1; }
14    }
15	else if (s == 0) {
16		fgets(formula, sizeof formula, fp); // 0 1 の後の改行の読み飛ばし
17		printf("Input:");
18	}
19	else return 1;
20
21	while (fgets(formula, sizeof formula, fp)) calcuration(formula);
22	if (s == 1) fclose(fp);
23}

投稿2020/06/10 04:52

編集2020/06/10 06:23

総合スコア8224

2020/06/10 05:03

ご親切にありがとうございます。

行動規範の内容に同意します

0

ベストアンサー

ELEMENT stack[STACK_SIZE];
int n;

この n はスタックの先頭位置ですよね?

C
1int getnumber(char *formula)
2{
3    int sign=0;
4    if (*formula=='+'){
5        formula++;
6    }else if (*formula=='-'){
7        sign=1;
8        formula++;
9    }
10    while (*formula>='0' && *formula<='9'){
11        n=n*10+(*formula-'0'); // ************ ここで壊してますよ *************
12        formula++;
13    }
14    if (sign) return -n;
15    return n;
16}

あと(こっちの方が重要なんだが)getnumber()から戻ってきたときに formula が
更新されないために、最初に現れた数値を延々とpush()し続けてスタック溢れを起こしてます。

あ...main() で scanf("%s", formula); やってるのもトラブルの原因。
これだと空白が読みこまれず、"12 34 +" の入力に対し formulaは"12"となります。

[追記]

C
1#define _CRT_SECURE_NO_WARNINGS
2#include <stdio.h>
3#include <stdlib.h>
4#include <ctype.h>
5#include <string.h>
6#include <stdbool.h>
7#include <assert.h>
8
9typedef long ELEMENT;
10const char* ELEMENT_FORMAT = "%ld";
11
12#define STACK_SIZE 100
13
14typedef struct {
15    ELEMENT body[STACK_SIZE];
16    int size;
17} Stack;
18
19void initialize(Stack* stack) {
20    assert( stack );
21    stack->size = 0;
22}
23
24/*push関数**/
25bool push(Stack* stack, ELEMENT x) {
26    assert( stack );
27    if ( stack->size >= STACK_SIZE) {
28        fputs("stack overflow!", stderr);
29        return false;
30    }
31    stack->body[stack->size++] = x;
32    return true;
33}
34
35/*pop関数*/
36bool pop(Stack* stack, ELEMENT* px) {
37    assert( stack );
38    assert( px );
39    if ( stack->size <= 0) {
40        fputs("stack underflow!", stderr);
41        return false;
42    }
43    *px = stack->body[--stack->size];
44    return true;
45}
46
47
48bool getnumber(const char* formula, ELEMENT* px) {
49    assert( formula );
50    assert( px );
51    return sscanf(formula, ELEMENT_FORMAT, px) == 1;
52}
53
54void calculate(Stack* stack, char* formula) {
55    assert( stack );
56    assert( formula );
57    char* token;
58    for ( token = strtok(formula, " \t\n"); token; token = strtok(NULL, " \t\n") ) {
59        ELEMENT x;
60        ELEMENT a, b;
61        if ( getnumber(token, &x) ) {
62            push(stack, x);
63        } else {
64            if ( false ) ; /* do nothing */
65            else if ( strcmp(token, ".") == 0 ) {
66              pop(stack, &x);
67            }
68            else if ( strcmp(token, "+") == 0 ) {
69              pop(stack, &b);
70              pop(stack, &a);
71              push(stack, a + b);
72            }
73            else if (strcmp(token, "-") == 0) {
74                pop(stack, &b);
75                pop(stack, &a);
76                push(stack, a - b);
77            }
78            else if (strcmp(token, "*") == 0) {
79                pop(stack, &b);
80                pop(stack, &a);
81                push(stack, a * b);
82            }
83            else if (strcmp(token, "/") == 0) {
84                pop(stack, &b);
85                pop(stack, &a);
86                push(stack, a / b);
87            } else {
88                fprintf(stderr, "[%s] unknown\n", token);
89            }
90        }
91    }
92}
93
94int main(void) {
95    Stack stack;
96    initialize(&stack);
97
98    int s;
99    char formula[256] = { 0 };
100    printf("数字データの時はスタックに積み、ピリオドの時はスタックから降ろします。(EOFで終了)\n");
101    printf("データ入力の方法を選んでください。\n0..キーボード/1..ファイル：");
102    scanf("%d", &s);
103    FILE* fp = stdin;
104
105    if (s == 1) {
106        fp = fopen("data.txt", "r");
107        if (fp == NULL) {
108            printf("ファイルオープン失敗\n");
109            return 1;
110        }
111        fgets(formula, sizeof(formula), fp);
112        fclose(fp);
113        calculate(&stack, formula);
114    }
115    else if (s == 0) {
116        printf("Input:");
117        gets_s(formula, 32); // 一度空読み
118        fgets(formula, 32, stdin);
119        calculate(&stack, formula);
120    }
121
122    ELEMENT x;
123    pop(&stack, &x);
124    printf("result = ");
125    printf(ELEMENT_FORMAT, x);
126    puts("");
127
128    return 0;
129}

投稿2020/06/08 18:15

編集2020/06/10 05:07

総合スコア16614

2020/06/09 00:01

＞nはスタックの先頭その通りです。ありがとうございます。。 formula++では更新されていないのでしょうか？

2020/06/09 00:03

void inc(int x) { ++x; } に対し、int a = 10; inc(a); しても a = 11 にはならんでしょ？それとおんなじ。

2020/06/09 00:03

空白の処理はどうすればいいのでしょうか。。？ fscanf(stdin, "%s",formula)としてもダメですか？

2020/06/09 00:04

＞void inc(int x)... 確かにそうでした..

2020/06/09 00:10 編集

gets 使えば改行までを読み取れます。 # って、ファイル入力側はちゃんとfgetsしてるやん...

2020/06/09 01:18

そこらへんの理解が曖昧なまま進めてしまいました。。解決できました。ありがとうございます。

2020/06/09 05:13

ちょこちょこっといぢくってそこそこ動くのできたけど、ほしい?

2020/06/09 15:56

解決できたというコードを貼り付けてください。質問を編集して追記してもいいし、新規回答でも構いません。なお、strtol を使うと非常に簡単になりますが、見たいですか？

2020/06/10 05:04

epistemeさん＞ご親切にありがとうございます。よろしければ見せていただきたいです。 kazuma-sさん＞承知しました。

2020/06/10 05:07

追記した。

2020/06/10 05:08

ありがとうございました！

2020/06/10 05:09

引き換えにあなたの解決したコードを見せて。

2020/06/10 05:17

わかりづらいですが、質問を編集して追記しました。お見せするのも恥ずかしいコードですが,,,。煩わしいことしてすみません。

行動規範の内容に同意します

あなたの回答

tips

プレビュー

行動規範の内容に同意します

質問の解決につながる回答をしましょう。サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。また、読む側のことを考えた、分かりやすい文章を心がけましょう。

15分調べてもわからないことは
teratailで質問しよう！

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

関連した質問

トップ Cに関する質問

逆ポーランド記法の負の数への対応の仕方

関連した質問

同じタグがついた質問を見る

運営からのお知らせ

【サポート業務のお知らせ】ゴールデンウィーク休業につき下記の日程で、お問い合わせ等のサポート業務をお休みいたします。 2024/04/27(土)~2024/04/29(月) 2024/05/03(金)〜2024/05/06(月) なお期間中もサポートへのお問い合わせは受け付けております。

【重要なお知らせ】いつもteratailをご利用いただきありがとうございます。現在、認証システムの修正により、一部のユーザーが強制的にログアウトされる可能性がございます。お手数おかけしますが、再度ログインを行なっていただきますよう宜しくお願いいたします。ご不便をおかけし申し訳ございません。

過去のお知らせを見る