c - 是否应该使用 Malloc 为该函数分配内存？这会导致段错误吗？

Question

我编写这个伪代码是因为我想尝试构建一个在更大的程序中使用的基本计算器。如下:

<小时/>

对于每个 token t:

如果t是运算符或左括号，则将其压入操作数堆栈。

Else if t 是右括号:重复弹出操作数堆栈，直到遇到左括号。对于找到的每个运算符:

• 弹出值堆栈两次以获取操作数。
• 对这些操作数执行运算。
• 将运算结果压入值栈。

Else t 表示数字。

将t转换为整数，并将其压入值堆栈。当 token 用完时，重复弹出操作数堆栈直至其为空，并像以前一样执行每个操作。此时值栈上应该有一个数字，这就是答案。

<小时/>

但是，当我编写代码时，它给了我一个段错误。我知道这与内存有关，但我不确定如何修复它，或者是否需要为此函数分配内存。

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

不确定这样写是否正确或者是否会抛出错误？

int operandApplication(int a, int b, char op){
  if (op == '+'){
    return a + b;
    }
    else {
      return a * b;
      }
} 


int popValStack(int valstack[], int *top){
  int valdata = valstack[*top]; 
  *top = *top - 1;  
 return valdata;
}

void pushValStack(int valstack[], int *top, int value){
  *top = *top + 1;
  valstack[*top] = value;
  }

char *popOpStack (char *charstack[], int *top){
  char *chardata = charstack[*top];
  *top = *top -1; 
  return chardata;
}

void pushOpStack (char *charstack[], int *top, char *value){
  *top = *top + 1;
  charstack[*top] = value;
  }

我需要在下面的主函数中使用malloc分配内存吗？

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

int i;
int valueStack[50];
int valcounter = 0;
int opcounter = 0; 
int l; 
int m;
char *opStack[50]; 
char *op;

for(i = 1; i < argc; i++){ 

我在这里使用了字符串比较，因为它看起来更容易，但不确定它是否有帮助。

  char *t = argv[i];
  int s1 = strcmp(t, "[");
  int s2 = strcmp(t, "+");
  int s3 = strcmp(t, "x");
  int s4 = strcmp(t, "]");

  if(s1 == 0 | s2 ==0 | s3 == 0){
    pushOpStack(opStack, &opcounter, argv[i]); 
  } 

  else if(s4 == 0){ 

    char *S = popOpStack(opStack, &opcounter); 

    while (*S!= '[') { 
      int a = popValStack(valueStack,  &valcounter);
      int b = popValStack(valueStack, &valcounter);
      pushValStack (valueStack, &valcounter, operandApplication(a, b, *S));
    }
  }
  else {
    int x = atoi(t);
    pushValStack(valueStack, &valcounter, x);
  }
}

while (opcounter > 0){

  op = popOpStack(opStack, &opcounter);
  l = popValStack(valueStack, &valcounter);
  m = popValStack(valueStack, &valcounter);
  pushValStack (valueStack, &valcounter, 
  operandApplication(l, m, *op));
}

printf ("%d\n", valueStack[valcounter]);

}

Answer 1

按照编写的程序，不需要 malloc。堆栈内存，普通变量声明，如 int i 或 int valueStack[50] ，一直存在到其声明的函数退出为止。因此，您在 main 中声明的所有变量都将一直存在，直到程序完成。

另一方面，如果您尝试像这样返回堆栈内存:

int *newStack() {
    int stack[50];
    return stack;
}


int *valueStack = newStack();

这将是一个问题，一旦newStack返回，stack指向的内存就会被释放。 vauleStack 将指向已释放的内存，该内存可能会被覆盖。

经验法则是，如果您返回一个指针，则必须对其进行 malloc 处理。

<小时/>

我无法重现您的问题，但我可以看出哪里可能出了问题。有几个地方你可能会放弃你的堆栈。

因为 valueStack 和 opStack 的大小是固定的，所以 pushValStack 和 popOpStack 都会离开​​栈的末尾。当 top 达到 49 时，堆栈会导致(等待)堆栈溢出。

int valueStack[50];
int valcounter = 0;
for( int i = 0; i < 50; i++ ) {
    pushValStack(valueStack, &valcounter, i);
}

(它是 49 而不是 50，因为 top 在将值放入堆栈之前会递增。这会导致一个离一错误，如果要在位置 0 存储任何内容top 必须从 -1 开始。)

类似地，popValStack 和 popOpStack 可能会离开数组的后面，导致堆栈下溢。负索引在 C 中起作用；他们在指针之前读取内存，这是不好的。有趣的是，这并没有给我带来错误。 YMMV。

发现此类错误的一种方法是添加一些 assert 来检查您是否超出了范围。断言是您假设为真的表达式。如果不是，程序将停止。

#include <stdio.h>
#include <assert.h>

// Here I put the stack size into a constant so it can be referenced by the asserts.
#define STACK_SIZE 50

int popValStack(int valstack[], int *top){
    assert( *top >= 0 );
    int valdata = valstack[*top]; 
    *top = *top - 1;  
    return valdata;
}

void pushValStack(int valstack[], int *top, int value){
    *top = *top + 1;
    assert( *top < STACK_SIZE );
    valstack[*top] = value;
}

int main(int argc, char *argv[]){ 
    int valueStack[STACK_SIZE];
    int valcounter = 0;
    for( int i = 0; i < STACK_SIZE; i++ ) {
        pushValStack(valueStack, &valcounter, 1);
    }
}

然后，您将得到一个明显的错误，而不是神秘的段错误。

Assertion failed: (*top < STACK_SIZE), function pushValStack, file test.c, line 26.

断言可以方便地验证代码中的任何假设和边界。

<小时/>

更进一步，我们可以通过使用结构将与堆栈相关的所有变量收集到一个地方来改进堆栈的代码和完整性。

typedef struct {
    int *stack;
    size_t size;
    size_t top;
} IntStack;

(我在这里使用了 size_t 而不是 int 因为它保证足够大以容纳最大可能对象的大小，所以它是适用于数组索引。)

然后 IntStack 可以作为单个单元传递。它知道它的大小和顶部在哪里。

void IntStackPush( IntStack *stack, int value ) {
    assert( stack->top < stack->size );
    stack->stack[stack->top] = value;
    stack->top += 1;
}

int IntStackPop( IntStack *stack ) {
    assert( stack->top > 0 );
    stack->top -= 1;
    return stack->stack[stack->top];
}

#define STACK_SIZE 50
int main(){ 
    int values[STACK_SIZE];
    IntStack valueStack = { .stack = values, .size = STACK_SIZE, .top = 0 };

    for( int i = 0; i < STACK_SIZE; i++ ) {
        IntStackPush(&valueStack, i);
    }

    for( int i = 0; i < STACK_SIZE; i++ ) {
        printf("%d\n", IntStackPop(&valueStack));
    }
}

请注意，我们必须手动初始化该结构，这可能容易出错。相反，我们可以编写一个函数来为我们做到这一点。由于我们现在要从函数返回指针，因此我们需要 malloc。

IntStack *IntStackNew( size_t size ) {
    // Allocate space for the struct.
    IntStack *stack = malloc(sizeof(IntStack));

    stack->top = 0;
    stack->size = size;
    // And allocate space for the stack.
    stack->stack = malloc( size * sizeof(int) );

    return stack;
}

由于我们在堆上分配内存，因此需要释放它。

void IntStackFree( IntStack *stack ) {
    free(stack->stack);
    free(stack);
}

现在可以在不了解其内部情况的情况下使用堆栈。

#define STACK_SIZE 50
int main(){ 
    IntStack *valueStack = IntStackNew(STACK_SIZE);

    for( int i = 0; i < STACK_SIZE; i++ ) {
        IntStackPush(valueStack, i);
    }

    for( int i = 0; i < STACK_SIZE; i++ ) {
        printf("%d\n", IntStackPop(valueStack));
    }

    IntStackFree(valueStack);
}