掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.27034

線形リスト
投稿者---hon(2006/05/31 04:37:49)


逆ポーランド。。。+だけの中途ですが、なにがわるいのかがわかりません。
どこがいけないんでしょう。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>

typedef struct _cell{
  double data;
  struct _cell *next;
}cell;

void insert_cell(cell **pointer, double new_value)
{
  cell *new_cell;
  new_cell = (cell *)malloc(sizeof(cell));
  new_cell->data = new_value;
  new_cell->next = *pointer;
  *pointer = new_cell;
}

void delete_cell(cell **pointer)
{
  cell *target;
  target = *pointer;
  *pointer = target->next;
  free((void *)target);
}

int main()
{
  char str[256];
  char token[10];
  int i = 0, j = 0;
  double data1, data2;
  cell *head = NULL, **p;
  p = &head;
  fgets(str, 256, stdin);
  while(i < strlen(str)){
    j = 0;
    while(isspace(str[i])) /* move to the not space  */
      i++;
    while(!isspace(str[i]) && i < strlen(str)){
      token[j] = str[i];
      j++;
      i++;
    }
    token[j] = '\0';
    if(strcmp(token,"+") == 0){
      data1  = (*p)->data;
      *p = (*p)->next;
      data2 = (*p)->data;
      *p = (*p)->next;
      delete_cell(p);
      delete_cell(p);
      insert_cell(p, (data1 + data2));
    }
    else if(strcmp(token,"-") == 0){

    }
    else if(strcmp(token,"*") == 0){

    }
    else if(strcmp(token,"/") == 0){

    }
    else{
      insert_cell(p, atof(token));
      p = &(*p)->next;
    }
  }
  return 0;
}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:線形リスト 27035 ぽへぇ 2006/05/31 06:37:02
<子記事> Re:線形リスト 27036 あしっど 2006/05/31 09:41:17
<子記事> Re:線形リスト 27037 かずま 2006/05/31 10:27:31


No.27035

Re:線形リスト
投稿者---ぽへぇ(2006/05/31 06:37:02)


>逆ポーランド。。。+だけの中途ですが、なにがわるいのかがわかりません。
>どこがいけないんでしょう。

問題が起こるテスト・ケースと、その結果が書いていないところ。

>症状は具体的に詳しく書きます。




この投稿にコメントする

削除パスワード

No.27036

Re:線形リスト
投稿者---あしっど(2006/05/31 09:41:17)


見難いソースだなあ。
エラー処理も全くないし。
解読するのが困難なので、仕様かコメントぐらい書きましょう。

それと、線形リストを使うなら、インサートデリートじゃなくて、
スタックのプッシュとポップを操作するように変えた方がいいと思いますよ。
スタックって線形リストのことだから。

あと下の線形リストでも思ったんだけど、この構造体のnextはnextじゃなくてpreviewのような気がするんだが…
pって、スタックの先頭を常に指してるポインタだと思うけど、
本当ならp->nextにnew_cellのアドレスを入れるべきじゃない?


この投稿にコメントする

削除パスワード

No.27043

Re:線形リスト
投稿者---へろり(2006/05/31 14:00:18)



>それと、線形リストを使うなら、インサートデリートじゃなくて、
>スタックのプッシュとポップを操作するように変えた方がいいと思いますよ。
>スタックって線形リストのことだから。
>

スタックと線形リストはまったくの別物です。
リストの”途中”にノードを追加したり削除したりするからこそリスト構造では?




この投稿にコメントする

削除パスワード

No.27054

Re:線形リスト
投稿者---επιστημη(2006/06/01 22:11:04)


>あと下の線形リストでも思ったんだけど、この構造体のnextはnextじゃなくてpreviewのような気がするんだが…

previewじゃなくてpreviousまたはpredecessor.



この投稿にコメントする

削除パスワード

No.27037

Re:線形リスト
投稿者---かずま(2006/05/31 10:27:31)


次のプログラムとどこが違うのか説明してください。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct _cell {
    double data;
    struct _cell *next;
} cell;

void insert_cell(cell **pointer, double new_value)
{
    cell *new_cell = malloc(sizeof(cell));
    new_cell->data = new_value;
    new_cell->next = *pointer;
    *pointer = new_cell;
}

void delete_cell(cell **pointer)
{
    cell *target = *pointer;
    *pointer = target->next;
    free(target);
}

int main()
{
    char str[256], token[10];
    int i = 0, j;
    double data1, data2;
    cell *head = NULL, **p = &head;

    fgets(str, 256, stdin);
    while (str[i]) {
        j = 0;
        while (isspace(str[i])) i++;
        if (str[i] == '\0') break;
        while (str[i] && !isspace(str[i])) token[j++] = str[i++];
        token[j] = '\0';
        if (strcmp(token, "+") == 0) {
            data1 = (*p)->data;
            delete_cell(p);
            data2 = (*p)->data;
            delete_cell(p);
            insert_cell(p, (data1 + data2));
        } else if (strcmp(token, "-") == 0) {

        } else if (strcmp(token, "*") == 0) {

        } else if (strcmp(token, "/") == 0) {

        } else {
            insert_cell(p, atof(token));
        }
    }
    printf("%.15g\n", (*p)->data);
    return 0;
}



この投稿にコメントする

削除パスワード

No.27050

Re:線形リスト
投稿者---hon(2006/06/01 11:46:15)


逆ポーランドここまでできました。
ただしこれで
(1.0 + 2.0) * (3.0 - 1.0)
をやると
1.0 + 2.0 = (A)
をやったあと
(A) * 3.0
ってなちゃうのはわかったんですがどう訂正すればいいのでしょう...

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

typedef struct _cell{
  double data;
  struct _cell *next;
}cell;

void insert_cell(cell **pointer, double new_value)
{
  cell *new_cell;
  new_cell = (cell *)malloc(sizeof(cell));
  new_cell->data = new_value;
  new_cell->next = *pointer;
  *pointer = new_cell;
}

void delete_cell(cell **pointer)
{
  cell *target;
  target = *pointer;
  *pointer = target->next;
  free((void *)target);
}


int main()
{
  char str[256];
  char token[10];
  int i = 0, j = 0;
  double data;
  cell *head = NULL, **p;
  p = &head;
  fgets(str, 256, stdin);
  while(i < strlen(str)){
    j = 0;
    while(isspace(str[i])) /* move to the not space  */
      i++;
    while(!isspace(str[i]) && i < strlen(str)){
      token[j] = str[i];
      j++;
      i++;
    }
    token[j] = '\0';
    if(strcmp(token,"+") == 0){
      p = &head;
      data  = (*p)->data;
      printf("#: %lf\n", (*p)->data);
      p = &((*p)->next);
      printf("#: %lf\n", (*p)->data);
      insert_cell(p, (data + (*p)->data));
      printf("+: %lf\n", (*p)->data);
      p = &head;
      delete_cell(p);
      p = &((*p)->next);
      delete_cell(p);
    }
    else if(strcmp(token,"-") == 0){
      p = &head;
      data  = (*p)->data;
      printf("#: %lf\n", (*p)->data);
      p = &((*p)->next);
      printf("##: %lf\n", (*p)->data);
      insert_cell(p, (data - (*p)->data));
      printf("-: %lf\n", (*p)->data);
      p = &head;
      delete_cell(p);
      p = &((*p)->next);
      delete_cell(p);
    }
    else if(strcmp(token,"*") == 0){
      p = &head;
      data  = (*p)->data;
      printf("#: %lf\n", (*p)->data);
      p = &((*p)->next);
      printf("##: %lf\n", (*p)->data);
      insert_cell(p, (data * (*p)->data));
      printf("*: %lf\n", (*p)->data);
      p = &head;
      delete_cell(p);
      p = &((*p)->next);
      delete_cell(p);
    }
    else if(strcmp(token,"/") == 0){
      p = &head;
      data  = (*p)->data;
      printf("#: %lf\n", (*p)->data);
      p = &((*p)->next);
      printf("##: %lf\n", (*p)->data);
      insert_cell(p, (data / (*p)->data));
      printf("/: %lf\n", (*p)->data);
      p = &head;
      delete_cell(p);
      p = &((*p)->next);
      delete_cell(p);
    }
    else if(strcmp(token,"^") == 0){
      p = &head;
      data  = (*p)->data;
      p = &((*p)->next);
      insert_cell(p, pow(data, (*p)->data));
      p = &head;
      delete_cell(p);
      p = &((*p)->next);
      delete_cell(p);
    }
    else if(strcmp(token,"%") == 0){
      p = &head;
      data  = (*p)->data;
      p = &((*p)->next);
      insert_cell(p, fmod(data, (*p)->data));
      p = &head;
      delete_cell(p);
      p = &((*p)->next);
      delete_cell(p);
    }
    else{
      insert_cell(p, atof(token));
      p = &(*p)->next;
    }
  }
  p = &head;
  printf("%lf\n", (*p)->data);
  return 0;
}





この投稿にコメントする

削除パスワード

No.27051

Re:線形リスト
投稿者---あしっど(2006/06/01 12:32:18)


こういう問題は、プログラムがどういうリストを組んでいるのか、
紙に書いてみるとよく分かるでしょう。

このプログラムでは恐らく、数字を左から取り出して計算しています。
例えば[1+2+3*4]=[1234*++]を入力すると、[1*2+3+4]と解釈されてしまいます。
これを数字を右から取り出すようにしましょう。
つまり[4*3+2+1]の順に計算するようにするわけですね。


この投稿にコメントする

削除パスワード

No.27053

Re:線形リスト
投稿者---かずま(2006/06/01 20:59:52)


insert_cell や delete_cell の中でポインタの付け替えをやっているのに
呼び出し側でも *p = (*p)->next; や p = &((*p)->next); などの操作を
行っているからおかしくなるのではありませんか?
そういうことを隠蔽するために関数を使うのではないでしょうか。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct _cell {
    double data;
    struct _cell *next;
} cell;

void insert_cell(cell **pointer, double new_value)
{
    cell *new_cell = malloc(sizeof(cell));
    if (!new_cell) fprintf(stderr, "out of memory\n"), exit(1);
    new_cell->data = new_value;
    new_cell->next = *pointer;
    *pointer = new_cell;
}

double delete_cell(cell **pointer)
{
    double data;
    cell *target = *pointer;
    if (!target) fprintf(stderr, "list empty\n"), exit(1);
    data = target->data;
    *pointer = target->next;
    free((void *) target);
    return data;
}

int main(void)
{
    char str[256], *token, *sep = " \t\r\n";
    double data1, data2;
    cell *head = NULL;

    if (!fgets(str, sizeof str, stdin)) return 1;
    for (token = strtok(str, sep); token; token = strtok(NULL, sep)) {
        if (strcmp(token, "+") == 0) {
            data1 = delete_cell(&head);
            data2 = delete_cell(&head);
            insert_cell(&head, data2 + data1);
        } else if (strcmp(token, "-") == 0) {
            data1 = delete_cell(&head);
            data2 = delete_cell(&head);
            insert_cell(&head, data2 - data1);
        } else if (strcmp(token, "*") == 0) {
            data1 = delete_cell(&head);
            data2 = delete_cell(&head);
            insert_cell(&head, data2 * data1);
        } else if (strcmp(token, "/") == 0) {
            data1 = delete_cell(&head);
            data2 = delete_cell(&head);
            insert_cell(&head, data2 / data1);
        } else if (strcmp(token, "^") == 0) {
            data1 = delete_cell(&head);
            data2 = delete_cell(&head);
            insert_cell(&head, pow(data2, data1));
        } else if (strcmp(token, "%") == 0) {
            data1 = delete_cell(&head);
            data2 = delete_cell(&head);
            insert_cell(&head, fmod(data2, data1));
        } else {
            insert_cell(&head, atof(token));
        }
    }
    data1 = delete_cell(&head);
    if (head)
        fprintf(stderr, "some operators missing\n");
    else
        printf("%.15g\n", data1);
    return 0;
}



この投稿にコメントする

削除パスワード

No.27059

Re:線形リスト
投稿者---ななし(2006/06/02 22:40:17)


私も以前作成したことがあります。
そのときは、紙にいろいろ書きながら作成しました。
ひとつのやり方ですが、式の格納をする構造体を考えました。
struct TREE
{
char Symbol;//1,+,...などを格納します。2桁以上を想定して、数値はnと格納。逆ポーランドでも数値の並び順は不変
int Prioriy;Symbolが数値なのか括弧、演算子なのか
bool Used;このSymbolを二分木のツリーに構築済みなのか
TREE *mTop;//ツリーの親
TREE *mLeft;//ツリーの左
TREE *mRigh;//ツリーの右
TREE *nNext;//式を一文字づつこの構造体に格納し、線形リストのためのポインター、また、構築済みになれば前後のnodeをくっつくけていく。
TREE *nPrev;//同上
TREE *_Next;//上のポインターはNodeの削除に使えないので、削除用の生命線。
TREE *_Prev;//同上
};
と、構造体の情報がいろいろ必要になると思いますので、
考えてください。
以上、通りすがりでした。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧