Infix to Postfix Conversion Using Linked List Stack in C++

on

Data Structure Using C++

Stack Data Structure

Infix 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);

int main ()
{
 stack s;    
 char op;
 char str[10]={'3','+','6','-','9','/','3','^','4'};
 char res[10];
 int j=-1;
 int i=0;
 while(str[i]!='\0')
 { 
  char 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);
   cout<<ch<<endl;
  }
  else
  {
   res[++j]=ch;
  }
  i++;
 }
 while(!s.isEmpty())
  {
   op=s.pop();
   res[++j]=op;
  }
 i=0;
 while(str[i]!='\0')
 {
  cout<<res[i]<<" ";
  i++;
 }
} 
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;
 }
}

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

Previous Post:
Postfix Evaluation Using Linked List Stack In C++

Comments

Post a Comment