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;
}
CodePudding user response:
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.
$