c - 将元素插入堆栈时遇到问题

Question

我正在开发一个项目，我必须采用逆波兰表示法获取表达式，将整数和运算符插入堆栈，然后在将它们插入二叉搜索树时将它们从堆栈中弹出。

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

struct snode 
{
  int datum;
  struct snode* bottom;
};

struct tnode
{
  int datum;
  struct tnode* left;
  struct tnode*right;
};

struct snode* 
push(struct snode* stack, int x) {
  struct snode *S = (struct snode*)malloc(sizeof(struct snode));
  S->datum = x;
  S->bottom = stack;
  return S;
}

struct snode* pop(struct snode* stack) {
  struct snode *S;
  if (stack == NULL)
    return NULL;
  S = stack->bottom;
  free(stack);
  return S;
}

int
peek(struct snode* stack){
  return stack->datum;
}


struct tnode*
create_node(int x){
  struct tnode* tmp;
  tmp = (struct tnode*)malloc(sizeof(struct tnode));
  tmp->datum = x;
  tmp->right = NULL;
  tmp->left = NULL;
  return tmp;
}

void
print_table(struct tnode *AST){
  if(AST !=NULL){
    print_table(AST->left);
    printf("%d ", AST->datum);
    print_table(AST->right);
  }
}

struct tnode*
build_tree(struct snode *S)
{
  struct tnode* root;
  if (S==NULL){
    return NULL;
  }else{
    int top = peek(S);
    if (top == 65 || top == 83 || top == 88 || top == 68 || top == 77){
      return create_node(top);
    }else{
      root= create_node(top);
      root->right = build_tree(pop(S));
      root->left = build_tree(pop(S));
      return root;
    }
  }
}

int
main(int argc, const char *argv[])
{

  int i = 1;
  struct tnode *tree = NULL;
  struct snode *stack = NULL;


  while (argv[i]!= NULL){
    stack = push(stack, argv[i][0]);
    i++;
  }

 tree =  build_tree(stack);
 print_table(tree);

 return EXIT_SUCCESS;
}

我觉得这应该可行。一切都编译干净。我这样运行它

./project 5 4 A

结果是

135208 135224 135208 135240 135208 135224 135208 0 135208 135224 135208 52 0 53 0 

什么时候应该

4 65 5

我认为这种情况发生的原因是我将元素插入堆栈的方式。

编辑:

我初始化了 i，使 i = 1。

这就是我得到的结果。

134480 134496 134480 0 5 4 5 

编辑2:

我决定去掉 atol(argv[i]) 并将其更改为 argv[i][0]。 请参阅代码。

现在我的输出只是

65

Answer 1

终于明白是怎么回事了!

以下是新修改的部分，应该可以使您的代码正常工作(请查看 // <== EDIT 注释):

struct tnode*
build_tree(struct snode *S)
{

  struct tnode* root;
  if (S == NULL)
    return NULL;

  int top = peek(S);

  if (top == 65 || top == 83 || top == 88 || top == 68 || top == 77)
  {
     root = create_node(top);
     S = pop(S); // <== EDIT
     root->right = build_tree(S);


     S = pop(S); // <== EDIT
     root->left = build_tree(S);
     return root;
  } 

  root= create_node(top);

  return root;
}

int
main(int argc, const char *argv[])
{

  int i = 1;
  struct tnode *tree = NULL;
  struct snode *stack = NULL;

  int value = 0;
  while (argv[i]!= NULL)
  {
    if ((value = atoi(argv[i])) == 0) // <== EDIT
        value = argv[i][0];
    stack = push(stack, value);
    i++;
  }


 tree =  build_tree(stack);
 print_table(tree);

 return EXIT_SUCCESS;
}

我发现有 3 个问题导致了您的值(value)观。

第一期: 您正在寻找的结果是 4 65 5 ，这意味着如果输入是数字(4、5 等)，则必须使用 atoi() 的结果。如果输入的不是数字，则必须使用 ASCII 值。

为此，我使用了以下几行:

    if ((value = atoi(argv[i])) == 0) // <== EDIT
        value = argv[i][0];
    stack = push(stack, value);

在我的atoi()的实现中，当转换失败时，atoi()返回0 。因此，我检查赋值的值: if atoi()返回0 ，使用 ASCII 值。

第二期: 您遇到的第二个问题是 build_tree()函数似乎有错误的逻辑。由于这是一棵树，我期望字符 A为根，数字 4 和 5 为分支，如下所示:

  A
 / \
4   5

你的逻辑似乎颠倒了情况，你的设置方式，数字成为根值，字母是分支。颠倒你的逻辑可以解决这个问题:

  int top = peek(S);

  if (top == 65 || top == 83 || top == 88 || top == 68 || top == 77)
  {
     root = create_node(top);
     S = pop(S); // <== EDIT
     root->right = build_tree(S);


     S = pop(S); // <== EDIT
     root->left = build_tree(S);
     return root;
  } 

  root= create_node(top);

  return root;

最后一期: 这是最重要的。当您调用build_tree()时，您传递了 pop() 的结果直接地。问题在于，您不会影响 S 的新根值。 。正因为如此:

1. 当您调用build_tree(pop(S))时第一次，您最终释放了S的内存空间。 。

2. 稍后，当您调用build_tree(pop(S))时第二次，您最终调用 pop(S)初始值(早期已释放的值)。

解决方案是重新分配 S当您调用pop()时，并调用 build_tree(S)之后。

     S = pop(S); // <== EDIT
     root->right = build_tree(S);


     S = pop(S); // <== EDIT
     root->left = build_tree(S);

TL；博士: 我对您的代码进行了一些修改，现在问题应该得到解决。复制粘贴，你应该就可以了。