Memory dumped while Evaluateing Prefix Expression in C program using stack

Question

In double evaluatePrefix(char preFix[]) function during entering switch(preFix[i]) case segmentation fault arrives. How to overcome it?

#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)] = '\0';

  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] = '\0';  // Add '\0' 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;
}

can you give some more information, e.g. your input? – Marcell Juhász Oct 10 '21 at 18:13 — Marcell Juhász, Oct 10 '21 at 18:13

MarcoLucidi · Accepted Answer · 2021-10-10T19:13:53.020

in this loop:

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

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

the condition is i >= 0, but i is declared as unsigned int: i will always be greater than or equal to 0 and the loop will "never" stop. once i is equal to 0, the next iteration subtracts 1 from it (i--), but the new value can't be -1 (because i is unsigned), it will be a very big number (2^32 - 1 assuming int is 4 bytes), the value will "wrap around from 0". the loop then goes on and the first time i is used to index preFix it will cause a segfault.

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

also please don't use gets(), use the more safe alternative fgets(). see man gets.

in the end, modern compilers will warn you about all this, look what happens when I compile your code with -Wall -Wextra on gcc 10.2:

$ 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.
$

thanks for the valuable explanation . – DevManush Oct 10 '21 at 19:16 — DevManush, Oct 10 '21 at 19:16

Memory dumped while Evaluateing Prefix Expression in C program using stack

1 Answers1