ページ 1 ／ 1
逆ポーランド記法(c)
Posted: 2017年4月20日(木) 11:18
by パティロケ
コード:
#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->への代入がうまくいかない点
主にここを直せばコンパイルはできると思うのでよろしくお願いします。
Re: 逆ポーランド記法(c)
Posted: 2017年4月21日(金) 02:01
by みけCAT
パティロケ さんが書きました:まずmain内whileで読み込んだトークンの優先順位を比較する関数read_p（トークンによって返された値で比較しようとしました）
read_p関数内でdata_type型(=char型)の値をstrcmp関数に渡しているのはおかしいでしょう。
「文字列」の比較にはstrcmp関数を用いるのが一般的ですが、「文字」は素直に==演算子などで比較できます。
パティロケ さんが書きました:new_nodeが型の競合というエラーが出てしまう点
関数は、使用する
前に宣言または定義をしなければいけません。
パティロケ さんが書きました:関数strtok使用箇所でread->への代入がうまくいかない点
区切り文字が無いようなので、strtokを使うのをやめて、自分で読み取り位置を管理するといいでしょう。
また、109行目のtと110行目のopの間に改行があるのも、おかしいと思います。
Re: 逆ポーランド記法(c)
Posted: 2017年4月21日(金) 13:17
by かずま
コンパイルできるようにしてみました。
new_node の定義を、それを使う push より前に移しました。
read_p と main も修正しています。
コード:
#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); //削除
}
}
}
でも、結果は思い通りになりません。
参考にならないプログラム
コード:
#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;
}
Re: 逆ポーランド記法(c)
Posted: 2017年4月21日(金) 17:32
by かずま
かずま さんが書きました:でも、結果は思い通りになりません。
スタックが空なのにどんどん pop するのは変ですね。
ループを抜けた後にまだスタックに残っていたら、
それを出力するようにしてみました。
コード:
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;
}
正しいのかどうか、私は検証していません。
質問者の確認をお願いします。