STACKS - the ignored datastructure

stacks have been largely ignored,because the are normally easy.
stacks are a basic requirement,lets see how many are able to write interesting stack codes.

so any post in this topic should have new problem and its solution,in itself.
if u want to post a question,please do it in a separate topic.any question here will be deleted.
(of course one can point out mistakes,but the post will be deleted after correction is made)

please try and use C++ STL.(that is one of the main reasons for starting this topic)

Some basics for c++ STL

Code:


// stack::push/pop
#include <iostream>
#include <stack>
using namespace std;

int main ()
{
  stack<int> mystack;

  for (int i=0; i<5; ++i)
          mystack.push(i);

  cout << "Popping out elements...";
  while (!mystack.empty())
  {
    cout << " " << mystack.top();
    mystack.pop();
  }
  cout << endl;

  return 0;
}


for more details:http://www.cplusplus.com/reference/stl/stack/

http://www.codechef.com/problems/ONP/
infix to postfix.

http://www.cs.laurentian.ca/dgoforth/cosc2006/asst5/algorithm_to_convert_infix.html

Code:


/*
 * File:  TransformtheExpression.cpp
 * Author: RamprasadG
 *
 * Created on March 7, 2009, 8:18 PM
 */

#include <stdlib.h>
#include <iostream>
#include <stack>

using namespace std;
/*
 *
 */

stack<char> pstack;
bool precedence_rule(char t)
{
    int tval,topval;
    switch(t)
    {
        case '+':
        case '-':tval=0;break;
        case '/':
        case '*':tval=1;break;
        case '^':tval=2;break;
    }
        switch(pstack.top())
    {
        case '+':
        case '-':topval=0;break;
        case '/':
        case '*':topval=1;break;
        case '^':topval=2;break;
    }
        if(topval>tval)
            return true;
        else
            return false;
}
string convert(string infix)
{
    string postfix;
    char t,tt;
    for(int i=0;i<infix.size();i++)
    {
        t=infix[i];
        //cout<<"\nhandling "<<t;
        if(t=='(')
        {
                // cout<<"if1 ";
                  pstack.push(t);
        }
        else if(t=='+' || t=='*' || t=='/' || t=='^' || t=='-' )
        {
          // cout<<" elseif2";
            while(!pstack.empty() && precedence_rule(t) && pstack.top()!='(' )
            {
                //cout<<" while1 ";
                tt=pstack.top();pstack.pop();
                postfix.push_back(tt);
            }
            pstack.push(t);
        }
        else if(t==')')
        {
          // cout<<" elseif3 ";
            while(!pstack.empty() && pstack.top()!='(')
            {
              // cout<<" while2";
                tt=pstack.top();pstack.pop();
                postfix.push_back(tt);
            }
            pstack.pop();
        }
        else
        {
          // cout<<" else4";
            postfix.push_back(t);
        }
        // cout<<"\ncurrent "<<postfix;
      // if(!pstack.empty())cout<<" top="<<pstack.top();
    }
    //cout<<"\nb4 while current "<<postfix;
      // if(!pstack.empty())cout<<" top="<<pstack.top();
    while(!pstack.empty())
    {
        //cout<<"\nwhile3";
        tt = pstack.top();pstack.pop();
        postfix.push_back(tt);
        //cout<<"\ncurrent "<<postfix;
        //if(!pstack.empty())cout<<" top="<<pstack.top();
    }
    //cout<<endl;
   
    return postfix;
}
int main(int argc, char** argv) {
   
    string infix;
    int n;
    cin>>n;
    while(n--)
    {
    cin>>infix;
    cout<<convert(infix)<<endl;
    }
    return (EXIT_SUCCESS);
}


good method to convert prefix directly to postfix

Code:


/*
http://fahadshaon.wordpress.com/2008/01/18/prefix-to-postfix-stack-emplementation/
*************************************

*Postfix to prefix conversion        *

*    (a+b)*c infix                  *

*    ab+c*  postfix                *

*    *+abc  prefix                  *

**************************************/





#include <iostream>

#include <stack>

using namespace std;



#define MAX 100

#define LEFT_DONE '#'



bool isOperator(char ch){

    return ch=='+' || ch=='-' || ch == '*' ||

        ch == '/' || ch == '$' || ch == '%';

}



int main(){



   //e input expression and p output expression

   char e[MAX],p[MAX];

   stack<char> stk;



   cout << "Enter a prefix : ";

   cin >> e;



   int j=0;

   //until the end of expression riches

   for (int i=0;e[i];i++){



      if(isOperator(e[i])){

         stk.push(e[i]);

      }

      else {

         p[j++]=e[i];



         while(!stk.empty() && stk.top()==LEFT_DONE){

            stk.pop();

            p[j++]=stk.top();

            stk.pop();

         }

         stk.push(LEFT_DONE);

      }

   }

   p[j]=0;

   cout << "Postfix expression is :" << p << endl;



   return 0;

}





reverse with and without an auxiliary stack

Code:


#include<iostream>
#include<stack>

using namespace std;

stack<int> s,aux;
void reverseWithAux(int size);
void reverseWithOutAux();
void print(stack<int> s);

int main(){
s.push(1);
s.push(2);
s.push(3);
s.push(4);

print(s);
reverseWithAux(s.size());
print(s);
reverseWithOutAux();
print(s);

}

void print(stack<int> s){
  while(! s.empty()){
      std::cout<<s.top();
      s.pop();
  }
  cout<<endl;
}

void reverseWithAux(int size){
  if(size <= 1)
      return;
 
  int top = s.top();
  s.pop();
   
  while(--size){
      aux.push(s.top());
      s.pop();
  }
 
  s.push(top);
 
  while(! aux.empty()){
      s.push(aux.top());
      aux.pop();
      size++;
  }
 
  reverseWithAux(size); 
}

void percolateUp()
{
        int a,b;
        if(s.empty())
                return;

        a = s.top();
        s.pop();
       
        if(s.empty())
        {
                s.push(a);
                return;
        }

        percolateUp();
        b = s.top();
        s.pop();
       
        s.push(a);
        s.push(b);
}

void reverseWithOutAux(){
        int a;
        if(s.empty())
                return;
        percolateUp();
        a = s.top();
        s.pop();
        reverseWithOutAux();
        s.push(a);
}

how will u sort a stack without an auxiliary stack ?
HINTS:
recursion is allowed
very similar to the code for reversing the stack

Code:


#include<iostream>
#include<stack>

using namespace std;

stack<int> s,aux;
void sort();
void percolateBiggestUp();
void print(stack<int> s);

int main(){
s.push(4);
s.push(2);
s.push(3);
s.push(1);

print(s);
sort();
print(s);

}

void print(stack<int> s){
  while(! s.empty()){
      std::cout<<s.top()<<endl;
      s.pop();
  }
  cout<<endl;
}

void sort(){
  if(s.size() <=0 )
      return;
     
  percolateBiggestUp();
 
  int biggest = s.top();
  s.pop();
 
  sort();
 
  s.push(biggest); 
}

void percolateBiggestUp(){
  int top = s.top();
  s.pop();
  if(s.size() == 0){
      s.push(top);
  }
  else{
      percolateBiggestUp();
      int secondTop = s.top();
      s.pop();
     
      //keep the bigger one on top!!   
      if(secondTop > top){
        s.push(top);
        s.push(secondTop);
      }
      else{
              s.push(secondTop);
              s.push(top);
      }     
  }   
}