Why does this conversion of infix to postfix notation using stack as an ADT crash?
#include<iostream>
#include<cstring>
using namespace std;
#define MAX 5
struct node
{
char data;
struct node *next;
};
class stack
{
public:
node *top;
stack() //constructor
{
top=NULL;
}
char Top() //return top element without popping
{
return(top->data);
}
int empty() //check empty
{
if(top==NULL)
return(1);
return(0);
}
void push(char x) //push function
{
node *p;
p=new node;
p->data=x;
p->next=top;
top=p;
}
char pop() //pop function
{
node *p;
char x;
p=top;
top=top->next;
x=p->data;
delete(p);
return(x);
}
int precedence(char x) //check precedence of operators
{
if(x=='(')
return 0;
else if(x=='+'||x=='-')
return 1;
else if(x=='*'||x=='/'||x=='%')
return 2;
return 3;
}
void infix_to_postfix(char infix[],char postfix[]);
};
void infix_to_postfix(char infix[],char postfix[])
{
stack s;
char x,token;
int i,j=0;
for(i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token))
postfix[j++]=token;
else
if(token=='(')
s.push(token);
else
if(token==')')
{
while((x=s.pop())!='(')
postfix[j++]=x;
}
else
{
while(s.precedence(token)<=s.precedence(s.Top())&& !s.empty())
postfix[j++]=s.pop();
s.push(token);
}
}
while(!s.empty())
{
x=s.pop();
postfix[j++]=x;
}
postfix[j++]='\0';
}
int main()
{
char infix[30],postfix[30];
cout<<"\nEnter the infix expression::\n";
cin>>infix;
infix_to_postfix(infix,postfix);
cout<<"/nThe equivalent postfix expression is::"<<postfix;
return 0;
}
The above code is giving segmentation fault with gedit in Ubuntu...whereas when the same code when run with turbo C in Windows with the required changes as follows...runs correctly...
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define MAX 5
struct node
{
char data;
struct node *next;
};
class stack
{
public:
node *top;
stack() //constructor
{
top=NULL;
}
char Top() //return top element without popping
{
return(top->data);
}
int empty() //check empty
{
if(top==NULL)
return(1);
return(0);
}
void push(char x) //push function
{
node *p;
p=new node;
p->data=x;
p->next=top;
top=p;
}
char pop() //pop function
{
node *p;
char x;
p=top;
top=top->next;
x=p->data;
delete(p);
return(x);
}
int precedence(char x) //check precedence of operators
{
if(x=='(')
return 0;
else if(x=='+'||x=='-')
return 1;
else if(x=='*'||x=='/'||x=='%')
return 2;
return 3;
}
void infix_to_postfix(char infix[],char postfix[]);
};
void infix_to_postfix(char infix[],char postfix[])
{
stack s;
char x,token;
int i,j=0;
for(i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token))
postfix[j++]=token;
else
if(token=='(')
s.push(token);
else
if(token==')')
{
while((x=s.pop())!='(')
postfix[j++]=x;
}
else
{
while(s.precedence(token)<=s.precedence(s.Top())&& !s.empty())
postfix[j++]=s.pop();
s.push(token);
}
}
while(!s.empty())
{
x=s.pop();
postfix[j++]=x;
}
postfix[j++]='\0';
}
int main()
{
char infix[30],postfix[30];
cout<<"\nEnter the infix expression::\n";
cin>>infix;
infix_to_postfix(infix,postfix);
cout<<"\nEquivalent postfix expression is::"<<postfix;
getch();
return 0;
}
Why is the problem arising in Ubuntu???
Answer
You never check whether your input stack is empty before directly dereferencing top->data. Specifically, this loop:
while(s.precedence(token)<=s.precedence(s.Top())&& !s.empty())
postfix[j++]=s.pop();
s.push(token);
can, and in your case will, dereference an empty stack because you check the empty state after you've already dereferenced the top pointer via s.Top(). You can avoid the inappropriate dereference by using boolean short-circuiting and the proper evaluation order:
while(!s.empty() && s.precedence(token)<=s.precedence(s.Top()))
postfix[j++]=s.pop();
s.push(token);
Input
A*(B+C/(D-A))
Output
The equivalent postfix expression is::
ABCDA-/+*
That said, this is extremely brittle. Unless specifically instructed to do so there is no reason you shouldn't be using a custom stack in the first place, as the standard adapter std::stack<> will remove about 90% of this code, and I strongly suggest taking advantage of that.
Finally, this is flat-out bug. Windows or Ubuntu makes no difference. It invokes undefined behavior. That it didn't crash on Windows means you were lucky (or not, since you assumed it was ok because it didn't crash); not right. And in case you're wondering how I noticed this, I saw it in the code, but confirmed it with Valgrind, which confirmed my suspicion immediately.
Using Standard Library for the Heavy Lifting
This gets considerably simpler when you use classes from the standard library for most of the operations, as you can hopefully see below. I kept your algorithm intact, but just used the std::stack adapter and std::string classes for the guts:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
static int precedence(char x) //check precedence of operators
{
if(x=='(')
return 0;
else if(x=='+'||x=='-')
return 1;
else if(x=='*'||x=='/'||x=='%')
return 2;
return 3;
}
std::string infix_to_postfix(const std::string& infix)
{
std::stack<char> s;
std::string postfix;
for (auto ch : infix)
{
if (isalnum(ch))
postfix.push_back(ch);
else if (ch == '(')
s.push(ch);
else if(ch == ')')
{
while (!s.empty())
{
ch = s.top();
s.pop();
if (ch == '(')
break;
postfix.push_back(ch);
}
}
else
{
while(!s.empty() && precedence(ch)<=precedence(s.top()))
{
postfix.push_back(s.top());
s.pop();
}
s.push(ch);
}
}
while(!s.empty())
{
postfix.push_back(s.top());
s.pop();
}
return postfix;
}
int main()
{
const char infix[] = "A*(B+C/(D-A)+2*(E-F))";
cout << "\nThe equivalent postfix expression is: " << infix_to_postfix(infix);
return 0;
}
Input
A*(B+C/(D-A)+2*(E-F))
Output
The equivalent postfix expression is:
ABCDA-/+2EF-*+*