从中缀创建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。