从中缀创建 rpn 表达式

Question

我尝试将中缀表示法表达式转换为后缀表示法 (RPN)。这是函数:

String createRPN(String infix)
{
     Stack *stack = node_alloc(1); //stack pointer
     stack->next = NULL;
     String ptr; //index
     String RPN = malloc(strlen(infix) + 1);
     String start = RPN;

     for (ptr = infix; *ptr != '\0'; ptr++)
     {
         if (isNum(*ptr) || (*ptr == ' ')) *RPN++ = *ptr;
         else if (*ptr == '(') push(&stack, '(');
         else if (isOper(*ptr))
         {
              while ((stack != NULL) && (stack->value != '('))
              {
                    if (compareOper(stack->value, *ptr)) *RPN++ = pop(&stack);
                    else break;
              }
              push(&stack, *ptr);
         } 
         else if (*ptr == ')')
         {
              while ((stack != NULL) && (stack->value != '(')) *RPN++ = pop(&stack);
              if (stack != NULL) pop(&stack);
         }
         else;
     }
     while (stack != NULL) *RPN++ = pop(&stack);
     *RPN = '\0';

     return start;
}

这是堆栈代码:

typedef struct node
{
   int value;
   struct node *next;   
}Stack;

void push(Stack **node, int value)
{
     Stack *temp = node_alloc(1);
     if (temp == NULL) return;
     temp->value = value;
     temp->next = *node;
     *node = temp;
}

int pop(Stack **node)
{
    if (*node == NULL) return 0;

    int num = (*node)->value;
    Stack *temp = (*node)->next;
    free(*node);
    *node = (temp == NULL) ? NULL : temp;

    return num;
}

但在我输入中缀字符串后，例如:

2 * ((3 + 5) + (6 + 2) * 5)

程序崩溃了，我需要你的帮助来检测我的错误..

Answer 1

这个:

 String RPN = malloc(sizeof(char*) * strlen(infix));

全错了。

当您应该用普通字符思考时，您正在分配 sizeof (char *) (指向字符的指针)单位。另外，您也不允许使用终止字符。

您需要:

String RPN = malloc(strlen(infix) + 1);

(永远)乘以 sizeof (char) 是没有意义的，因为它保证为 1。