使用堆栈在 C 程序中评估前缀表达式时内存转储

Question

在double evaluatePrefix(char preFix[])函数中进入switch(preFix[i])的情况下分段错误到来。如何克服？

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

#define MAX 100

void infixToPrefix(char infix[], char prefix[]);
int precedence(char symbol);
int power(int a, int b);
void reverseStr(char str[]);
double evaluatePrefix(char preFix[]);

long int stack[MAX];
int top = -1;
void push(long int symbol);
long int pop();
int isEmpty();
int isFull();

int main()
{
   char infix[MAX], prefix[MAX];

   printf("Enter infix expression: ");
   gets(infix);

   reverseStr(infix);
   infixToPrefix(infix,prefix);
   reverseStr(prefix);

   printf("Prefix expression is: %s\n",prefix);
   printf("Value of expression: %.2lf\n",evaluatePrefix(prefix));

   return 0;
}

int isEmpty()
{
   return (top == -1) ? 1 : 0;
}

int isFull()
{
   return (top == MAX-1) ? 1 : 0;
}

void push(long int x)
{
  if(isFull())
   {
      printf("Stack Overflow\n");
      return;
   }
   top++;
   stack[top] = x;
}

long int pop()
{
   long int x;
   if(isEmpty())
   {
      printf("Stack Underflow\n");
      exit(1);
   }
   x = stack[top];
   top--;

   return x;
}

int power(int base, int exponent)
{
   int i, x = 1;
   for(i = exponent; i > 0; i--)
   {
       x *= base;
   }
   return x;
}

void reverseStr(char str[])
{
  char reverse[strlen(str)+1];
  for(int i = strlen(str)-1, j = 0; i >= 0; i--, j++)
      reverse[j] = str[i];
  reverse[strlen(str)] = '[=10=]';

  for(int i = 0; i < strlen(reverse); i++)
      str[i] = reverse[i];
}

int precedence(char symbol)
{
  switch(symbol)
  {
   case ')':
        return 0;
   case '+':
   case '-':
        return 1;
   case '*':
   case '/':
   case '%':
        return 2;
   case '^':
        return 3;
   default:
        return 0;
   }
}

void infixToPrefix(char infix[], char prefix[])
{
unsigned int i, p;
char next, symbol;

p = 0;
for(i = 0; i < strlen(infix); i++)
{
    symbol = infix[i];

    if(symbol == ' ' || symbol == '\t') // ignore blanks and tabs
        continue;

    switch(symbol)
    {
    case ')':
        push(symbol);
        break;
    case '(':
        while((next = pop()) != ')')
                prefix[p++] = next;
        break;
    case '+':
    case '-':
    case '*':
    case '/':
    case '%':
    case '^':
        while(!isEmpty() && precedence(stack[top]) >= precedence(symbol))
            prefix[p++] = pop();
        push(symbol);
        break;
    default:   // Operand
        prefix[p++] = symbol;
    }
}

while(!isEmpty())
    prefix[p++] = pop();

prefix[p] = '[=10=]';  // Add '[=10=]' to make postfix a string
}


double evaluatePrefix(char preFix[])
 {
 long int x, y;
 double result;
 unsigned int i;

for(i = strlen(preFix)-1 ; i >= 0; i--)
{
    if(preFix[i] <= '9' && preFix[i] >= '0')
        push(preFix[i]-'0');
    else
    {
        y = pop();  // 1st operand
        //printf("1st %.ld\n",y);
        x = pop();  // 2nd operand
        //printf("2nd %.ld\n",x);
        switch(preFix[i])   // I think Segmentation fault happened here
        {
        case '+':
            push(y+x);
            break;
        case '-':
            push(y-x);
            break;
        case '*':
            push(y*x);
            break;
        case '/':
            push(y/x);
            break;
        case '%':
            push(y%x);
            break;
        case '^':
            push(power(y,x));
        }
    }
}

result = pop();
return result;
}

Answer 1

在此循环中：

double evaluatePrefix(char preFix[])
{
    ...
    unsigned int i;

    for (i = strlen(preFix)-1; i >= 0; i--)

条件为i >= 0，但i声明为unsigned int：i将总是大于或等于 0 并且循环将“never”停止。一旦 i 等于 0，下一次迭代从中减去 1 (i--)，但新值不能是 -1（因为 i 是 unsigned)，它将是一个非常大的数字（2^32 - 1 假设 int 是 4 个字节），该值将“从 0 环绕”。然后循环继续，第一次 i 用于索引 preFix 它将导致段错误。

见What's the best way to do a reverse 'for' loop with an unsigned index?

也请不要使用 gets()，使用更安全的替代方法 fgets()。参见 man gets。

最后，现代编译器会警告你这一切，看看当我在 gcc 10.2 上用 -Wall -Wextra 编译你的代码时会发生什么：

$ gcc -Wextra -Wall stack.c
stack.c: In function ‘main’:
stack.c:25:4: warning: implicit declaration of function ‘gets’; did you mean ‘fgets’? [-Wimplicit-function-declaration]
   25 |    gets(infix);
      |    ^~~~
      |    fgets
stack.c: In function ‘reverseStr’:
stack.c:89:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
   89 |   for(int i = 0; i < strlen(reverse); i++)
      |                    ^
stack.c: In function ‘evaluatePrefix’:
stack.c:163:30: warning: comparison of unsigned expression in ‘>= 0’ is always true [-Wtype-limits]
  163 | for(i = strlen(preFix)-1 ; i >= 0; i--)
      |                              ^~
/usr/bin/ld: /tmp/cc9ys6Yb.o: in function `main':
stack.c:(.text+0x29): warning: the `gets' function is dangerous and should not be used.
$

使用堆栈在 C 程序中评估前缀表达式时内存转储

Memory dumped while Evaluateing Prefix Expression in C program using stack

c

stack

prefix