合計 昨日 今日

逆ポーランド記法(c)

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Name: パティロケ
[URL]
Date: 2017年4月20日(木) 11:18
No: 1
(OFFLINE)

 逆ポーランド記法(c)

コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define TRUE 1
#define FALSE 0
 
typedef char data_type;
typedef struct node_tag{
  data_type data;
  struct node_tag *next; //次ノードへのポインタ
} node_type; //ノードの型
 
void init(node_type **pp){
  *pp = NULL;
}
//空スタック確認
int is_empty(node_type *p){
  if(p==NULL){
    return TRUE;
  }else{
    return FALSE;
  }
}
//スタック先頭データ取得
data_type top(node_type *p){
  if(p==NULL)
    return '\n';
  else
    return p->data;
}
//スタックpush
int push(node_type **pp, data_type x){
  node_type *temp;
 
  temp = new_node(x, *pp);
  if(temp==NULL)
    return FALSE;
  *pp = temp;
  return TRUE;
}
 
//スタックpop
int pop(node_type **pp){
  node_type *temp;
 
  if(*pp!=NULL){
    temp=(*pp)->next;
    free(*pp);
    *pp=temp;
    return TRUE;
  }
  else return FALSE;
}
//
 
node_type *new_node(data_type x, node_type *p){
  node_type *temp;
  temp = (node_type *)malloc(sizeof(node_type));
 
  if(temp == NULL)
    return NULL; //割り当て失敗
  else{
    temp->data = x;
    temp->next = p; //次へのポインタNULLなど
    return temp;
  }
}
 
 
 
//読み込んだ優先順位
int read_p(data_type a){
  if(!strcmp(a, "=")){
    return 0;
  }else if(!strcmp(a, "+")){
    return 2;
  }else if(!strcmp(a, "-")){
      return 2;
  }else if(!strcmp(a, ")")){
        return 1;
  }else if(!strcmp(a, "*")){
          return 3;
  }else if(!strcmp(a, "/")){
            return 3;
  }else if(!strcmp(a, "(")){
    return 4;
  }else{
    return 5;
  }
}
 
 
 
 
//main関数
int main()
{
  node_type *stack;
  init(&stack); //初期化
 
  node_type *read;
  data_type ch1[] = "A=(B-C)/D+E*F";
  data_type ch2[] = " ";
 
  read->next = strtok(ch1, ch2);
  while((read->next!=NULL)){ //トークン読み込み中
    read->next = strtok(NULL, ch2);
    while((is_empty(stack)==0)&&(top(stack)!='(')&&(read_p(read->data)<=read_p(t
op(stack))))
      {
        printf("%s\n", top(stack));//先頭表示
        pop(&stack);//削除
      }
    if(read->data!=')'){
      push(&read, read->data);
    }else{
      pop(&stack);//つまり"("削除
    }
    while(is_empty(stack)==1){
      printf("%s\n", top(stack));//先頭表示
      pop(&stack);//削除
    }
  }
}


読み込んだ計算式(ex)A=B+Cを逆ポーランド記法に変換するプログラムとしてスタックを用いて実装したいのですが、エラーが直せません。
直したいところは、まずmain内whileで読み込んだトークンの優先順位を比較する関数read_p(トークンによって返された値で比較しようとしました)
new_nodeが型の競合というエラーが出てしまう点
関数strtok使用箇所でread->への代入がうまくいかない点
主にここを直せばコンパイルはできると思うのでよろしくお願いします。

Name: みけCAT
[URL]
伝説なるハッカー(660,241 ポイント)
Date: 2017年4月21日(金) 02:01
No: 2
(OFFLINE)

 Re: 逆ポーランド記法(c)

パティロケ さんが書きました:まずmain内whileで読み込んだトークンの優先順位を比較する関数read_p(トークンによって返された値で比較しようとしました)

read_p関数内でdata_type型(=char型)の値をstrcmp関数に渡しているのはおかしいでしょう。
「文字列」の比較にはstrcmp関数を用いるのが一般的ですが、「文字」は素直に==演算子などで比較できます。

パティロケ さんが書きました:new_nodeが型の競合というエラーが出てしまう点

関数は、使用するに宣言または定義をしなければいけません。

パティロケ さんが書きました:関数strtok使用箇所でread->への代入がうまくいかない点

区切り文字が無いようなので、strtokを使うのをやめて、自分で読み取り位置を管理するといいでしょう。

また、109行目のtと110行目のopの間に改行があるのも、おかしいと思います。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Name: かずま
[URL]
Date: 2017年4月21日(金) 13:17
No: 3
(OFFLINE)

 Re: 逆ポーランド記法(c)

コンパイルできるようにしてみました。
new_node の定義を、それを使う push より前に移しました。
read_p と main も修正しています。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define TRUE 1
#define FALSE 0
 
typedef char data_type;
typedef struct node_tag{
  data_type data;
  struct node_tag *next; //次ノードへのポインタ
} node_type; //ノードの型
 
void init(node_type **pp){
  *pp = NULL;
}
 
node_type *new_node(data_type x, node_type *p){
  node_type *temp;
  temp = (node_type *)malloc(sizeof(node_type));
 
  if(temp == NULL)
    return NULL; //割り当て失敗
  else{
    temp->data = x;
    temp->next = p; //次へのポインタNULLなど
    return temp;
  }
}
 
//空スタック確認
int is_empty(node_type *p){
  if(p==NULL){
    return TRUE;
  }else{
    return FALSE;
  }
}
 
//スタック先頭データ取得
data_type top(node_type *p){
  if(p==NULL)
    return '\n';
  else
    return p->data;
}
 
//スタックpush
int push(node_type **pp, data_type x){
  node_type *temp;
 
  temp = new_node(x, *pp);
  if(temp==NULL)
    return FALSE;
  *pp = temp;
  return TRUE;
}
 
//スタックpop
int pop(node_type **pp){
  node_type *temp;
 
  if(*pp!=NULL){
    temp=(*pp)->next;
    free(*pp);
    *pp=temp;
    return TRUE;
  }
  else return FALSE;
}
 
//読み込んだ優先順位
int read_p(data_type a)
{
    if (a == '=') return 0;
    if (a == '+' || a == '-') return 2;
    if (a == ')') return 1;
    if (a == '*' || a == '/') return 3;
    if (a == '(') return 4;
    return 5;
}
 
//main関数
int main()
{
    node_type *stack;
    init(&stack);  //初期化
 
    data_type ch1[] = "A=(B-C)/D+E*F";
    data_type *read = ch1;
    data_type data;
 
    while ((data = *read++) != '\0') {  //トークン読み込み中
        while ((is_empty(stack) == 0) &&
               (top(stack) != '(') &&
               (read_p(data) <= read_p(top(stack)))) {
            printf("%c\n", top(stack));  //先頭表示
            pop(&stack);  //削除
        }
        if (data != ')') {
            push(&stack, data);
        } else {
            pop(&stack);  //つまり"("削除
        }
        while (is_empty(stack) == 1) {
            printf("%c\n", top(stack));  //先頭表示
            pop(&stack);  //削除
        }
    }
}

でも、結果は思い通りになりません。

参考にならないプログラム
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>  // puts
#include <ctype.h>  // isalpha
 
const char *p, o[] = "==+-*/";
char *q;
unsigned char c;
 
void expr(const char *b)
{
    int d;
    if (*b)
        for (expr(b+2); c == b[0] || c == b[1]; *q++ = d) d = c, expr(b+2);
    else
        isalpha(c = *p++) ? *q++ = c, c = *p++ :
            c == '(' ? expr(o), c = c == ')' ? *p++ : 1 : (c = 1);
}
 
int rpn(const char *s, char *t)
{
    return p = s, q = t, expr(o), *q = 0, c;
}
 
int main(void)
{
    char t[1024];
    puts(rpn("A=(B-C)/D+E*F", t) ? "error" : t);
    return 0;
}

Name: かずま
[URL]
Date: 2017年4月21日(金) 17:32
No: 4
(OFFLINE)

 Re: 逆ポーランド記法(c)

かずま さんが書きました:でも、結果は思い通りになりません。

スタックが空なのにどんどん pop するのは変ですね。
ループを抜けた後にまだスタックに残っていたら、
それを出力するようにしてみました。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main(void)
{
    node_type *stack;
    init(&stack);  //初期化
 
    data_type ch1[] = "A=(B-C)/D+E*F";
    data_type *read = ch1;
    data_type data;
 
    while ((data = *read++) != '\0') {  //トークン読み込み中
        while ((is_empty(stack) == 0) && (top(stack) != '(') &&
               (read_p(data) <= read_p(top(stack)))) {
            putchar(top(stack));  //先頭表示
            pop(&stack);  //削除
        }
        if (data != ')') {
            push(&stack, data);
        } else {
            pop(&stack);  //つまり"("削除
        }
    }
    while (is_empty(stack) == 0) {
        putchar(top(stack));  //先頭表示
        pop(&stack);  //削除
    }
    putchar('\n');
    return 0;
}

正しいのかどうか、私は検証していません。
質問者の確認をお願いします。


Return to C言語何でも質問掲示板

オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[28人]