Infix (With Parenthesis) to Postfix Conversion Using Linked List Stack in Data Structure Using C++

on

Data Structure Using C++

Stack Data Structure

Infix (With Parenthesis) to Postfix Conversion Using Linked List Stack

class stack
{
 private:
  node *head;
 public:
  stack();
  void push(int val);
  int pop ();
  int top();
  int isEmpty ();
};
stack::stack()
{
 head=NULL;
}
void stack::push(int val)
{
 node *ptr= new node (val);
 ptr->setNext(head);
 head=ptr;
}
int stack::pop()
{
 if(isEmpty())
 {
  cout<<"Error: Stack is empty. can't pop element."<<endl;
 }
 else
 {
  int val=head->get();
  head=head->getNext();
  return val;
 }
}
int stack::top()
{
 return head->get();
}
int stack::isEmpty()
{
 return head==NULL;
}

bool precedence(char op1, char op2);
int priority(char x);
class node
{
 private:
  char data;
  node *next;
 public:
  node(char d);
  void set(char d);
  char get ();
  void setNext (node *);
  node* getNext();
  void showData();
};
node::node(char d)
{
 data=d;
 next=NULL;
}
void node::set(char d)
{
 data=d;
}
char node::get()
{
 return data;
}
void node::setNext(node* n)
{
 next=n;
}
node* node::getNext()
{
 return next;
}
void node::showData()
{
 cout<<get()<<"\t";
}
class stack
{
 private:
  node *head;
 public:
  stack();
  void push(char val);
  char pop ();
  char top();
  int isEmpty ();
};
stack::stack()
{
 head=NULL;
}
void stack::push(char val)
{
 node *ptr= new node (val);
 ptr->setNext(head);
 head=ptr;
}
char stack::pop()
{
 if(isEmpty())
 {
  cout<<"Error: Stack is empty. can't pop element."<<endl;
 }
 else
 {
  int val=head->get();
  head=head->getNext();
  return val;
 }
}
char stack::top()
{
 return head->get();
}
int stack::isEmpty()
{
 return head==NULL;
}
int main ()
{
 stack s;    
 char op, ch;
 char str[20]={'(','3','+','(','3','+','6',')',')','*','(','3','+','9',')'
 };
 char res[10];
 int j=-1;
 int i=0;
 while(str[i]!='\0')
 { 
  ch=str[i];
  if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^')
  {
   while(!s.isEmpty()&&precedence(s.top(),ch))
   {
    op=s.pop();
    res[++j]=op;
   }
   s.push(ch);
  }
  else if(ch=='(')
  {
   s.push(ch);
  }
  else if(ch==')')
  {
   while(s.top()!='(')
   {
    op=s.pop();
    res[++j]=op;
   } 
   s.pop();
  }
  else
  {
   res[++j]=ch;
  }
  i++;
 }
 while(!s.isEmpty())
  {
   op=s.pop(); 
   res[++j]=op;
  }
 i=0;
 while(str[i]!='\0')
 {
  cout<<res[i]<<" ";
  i++;
 }
 cout<<endl;
} 
bool precedence(char op1, char op2)
{
 if(priority(op1)>=priority(op2))
 {
  return true;
 }
 else
 {
  return false;
 }
} 
int priority(char x)
{
 if(x=='^'){
  return 4;
 }
 else if(x=='*'||x=='/')
 {
  return 3;
 }
 else if(x=='+'||x=='-')
 {
  return 2;
 }else{
  return 1;
 }
}

Let me know in the comment section if you have any question.

Previous Post:
Infix to Postfix Conversion Using Linked List Stack in C++

Comments

Post a Comment