2

我是 C 的新手，正在为 Scheme 做解释器。我正在尝试获得一个合适的 printList 方法来遍历该结构。

该程序接受如下输入：

(a (bc))

并在内部将其表示为：

[""][ ][ ]-->  [""][ ][/]
     |              |              
   ["A"][/][/]     [""][ ][ ]-->  [""][ ][/]     
                        |              |                 
                      ["B"][/][/]    ["C"][/][/]

现在，我只想让程序接受输入，在内部制作适当的单元格结构并打印出单元格结构，从而得到

(a (bc))

在末尾。

这是我的结构：

typedef struct conscell *List;

struct conscell {
char symbol;
struct conscell *first;
struct conscell *rest;

};


void printList(char token[20]){
    List current = S_Expression(token, 0);

     printf("(");

printf("First Value? %c \n", current->first->symbol);
printf("Second value? %c \n", current->rest->first->first->symbol);
printf("Third value? %c \n", current->rest->first->rest->first->symbol);


printf(")");

}

在 main 方法中，我得到第一个令牌并调用：

打印列表（令牌）；

我再次测试了子列表的值，我认为它正在工作。但是，我需要一种方法来遍历整个结构。请再次查看我的 printList 代码。打印调用是我必须输入的，以手动获取 (a (bc)) 列表值。所以我得到这个输出：

第一价值？一种

第一价值？b

第一价值？C

这是我想要的，但我想要一种使用循环的方法，无论结构多么复杂，还要在适当的地方添加括号，所以最后，我应该得到：

(a (bc))

这与输入相同。

谁能帮我解决这个问题？

4

2 回答 2

2

原程序的数据类型有点奇怪；您希望能够描述一组不相交的数据，在这种情况下，联合可能就是您想要的。目前，您只有一个用于 cons 单元格的数据类型，因此很难区分：

(a b c)

和

(a (b c))

您现在使用的技巧是将符号数据视为单元格的左右指针均为 NULL 的数据，但这使得它无法表示：

(())

这正是当您有一个内容均为 NULL 的 cons 单元格时会发生的情况。

表示不相交数据集的一种方法是使用标记的不相交联合，如下所示：

enum SexpType {SYMBOL, CONS, NIL};

struct Sexp {
  enum SexpType type;
  union {
    char symbol;
    struct Cons *cons;
  };
};

struct Cons {
  struct Sexp *first;
  struct Sexp *rest;
};

Sexp 可以是 a SYMBOL、 aCONS或NIL。根据其类型，我们将区别对待结构的联合部分。

我们可能会包含一些帮助程序，以使构建这些结构更容易：

struct Sexp* newCons(struct Sexp* first, struct Sexp* rest) {
  struct Sexp* pair = malloc(sizeof(struct Sexp));
  pair->type = CONS;
  pair->cons = malloc(sizeof(struct Cons));
  pair->cons->first = first;
  pair->cons->rest = rest;
  return pair;
}

struct Sexp* newSymbol(char c) {
  struct Sexp* ch = malloc(sizeof(struct Sexp));
  ch->type = SYMBOL;
  ch->symbol = c;
  return ch;
}

一旦我们有了正确的数据表示，那么printList将是一个基于类型标签调度的递归函数：

void printSexp(struct Sexp* sexp) {
  switch (sexp->type) {
  case SYMBOL: 
    /* FIXME */
    break;
  case CONS:
    /* FIXME */
    break;
  case NIL:
    /* FIXME */
    break;
  }
}

每个案例都相当简单。为了让CONS案例做点什么，我们可能会尝试这样的事情：

printf("(");
printSexp(sexp->cons->first);
printf(" . ");
printSexp(sexp->cons->rest);
printf(")");

我们在该对的组件上递归调用打印机。但是，这可能不是我们想要的，因为它将所有内容都视为不正确的结构，并且您可能希望对常规列表做一些更好的事情。

于 2012-10-22T17:35:17.623 回答
1

List 的类型是 struct conscell 的指针，因此 createList 函数中的 malloc() 应该是 sizeof(struct conscell)：

List node = malloc(sizeof(struct conscell));

指向结构的指针只有 8 字节，而结构本身的大小是 17（默认填充实际上是 24 字节）：

http://en.wikipedia.org/wiki/Data_structure_alignment

于 2012-10-22T02:58:36.480 回答