// Piotr Majcher

#include <iostream>
#include <stack>
#include <queue>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{   
    /* Pokazanie idei stosu.
       Tworzymy napis, który wpisujemy znak po znaku na stos.
       Napis jest palindromem, więc jeśli będziemy odczytywać go od końca 
       to powinien powstać ten sam napis.
       Wykorzystanie konstruktora - stack<value_type val>;
                     metod        - void push(value_type val);
                                  - void pop();
                                  - reference top();
                                  - size_type size();
                                  */ 
    string palindrom("zaradnydyndaraz");      
    cout<<"Napis wpisany znak po znaku na stos:                 \""<<palindrom<<"\" "<<endl;
    stack<char> stos;                                           /* konstruktor tworzy stos znaków   */
    for( unsigned int i = 0; i < palindrom.size(); ++i)
    {
             stos.push(palindrom[i]);                           /* odkładamy na stos kolejne litery napisu */
    }
    cout<<"Napis powstaly ze znaków zdejmowanych ze stosu :     \"";
    for( unsigned int i = stos.size(); i > 0; --i)                       /* w każdym obiegu pętli odczytujemu znak zapisany na gorze*/
    {
             cout<<stos.top();                                  /* funkcja zwraca znak umieszczony na wierzchołku stosu*/
             stos.pop();                                        /* funkcja zdejmuje znak z wierzchołka stosu  */
    }
    cout<<"\" "<<endl;

    cout << endl ; 
    /* Na konsoli widzimym, ze obydwa napisy sa takie same.*/
    

    /* Testowanie operatorów  -       operator!= (stack);
                              -       operator< (stack);
                              -       operator<= (stack);
                              -       operator> (stack);
                              -       operator>= (stack);
                              -       operator== (stack)*/
    stack<int> stosA;
    stosA.push(1);
    stosA.push(2);
    stosA.push(3);
    cout<<"stosA - 1 2 3"<<endl;
    stack<int> stosB;
    stosB.push(1);
    stosB.push(2);
    stosB.push(3);
    cout<<"stosB - 1 2 3"<<endl;
    
    if( stosA > stosB)
        cout<<"stosA > stosB " << endl;
    if( stosA < stosB)
        cout<<"stosA < stosB " << endl;
    if( stosA == stosB)
        cout<<"stosA = stosB " << endl;
    if( stosA >= stosB)
        cout<<"stosA >= stosB " << endl;
    if( stosA <= stosB)
        cout<<"stosA <= stosB " << endl;
    if( stosA != stosB)
        cout<<"stosA != stosB " << endl;
    cout << endl ; 
    stosB.pop();
    stosB.push(4);
    cout<<"stosA - 1 2 3"<<endl;
    cout<<"stosA - 1 2 4"<<endl;
    if( stosA > stosB)
        cout<<"stosA > stosB " << endl;
    if( stosA < stosB)
        cout<<"stosA < stosB " << endl;
    if( stosA == stosB)
        cout<<"stosA = stosB " << endl;
    if( stosA >= stosB)
        cout<<"stosA >= stosB " << endl;
    if( stosA <= stosB)
        cout<<"stosA <= stosB " << endl;
    if( stosA != stosB)
        cout<<"stosA != stosB " << endl;
        
    cout<<endl;
    stack<int> stosC = stosA;
    cout<<"stosC - ";
    /* wykorzystanie metody  - empty()*/
    while( !stosC.empty())
    {      cout<<stosC.top()<<" ";
           stosC.pop();
    } 
    cout<<endl;
    cout<<"stosA - ";
    while( !stosA.empty())
    {      cout<<stosA.top()<<" ";
           stosA.pop();
    } 
    cout<<endl;
    /* Przykładowe wykorzystanie stosu
       ODWROTNA NOTANCJA POLSKA 
       Przedstawiony jest uproszczony algorytm
       konwersji z notacji infiksowej na odwrotną notację polską.
       Uproszczenie polega na ograniczeniu operatorów
       wykorzystywanych w wyrażeniach tylko do "+" i "*".
       Można korzystać równierz z nawiasów.*/
       
    stack<char> RPNStack;       /* stos wykorzystywany w algorytmie  */ 
    
    queue<char> RPNQueue;       /* kolejka służąca do zapisywania wyniku
                                   wyjściowego     */
    string wyrazenie("1+(2*3)*2 +(2+1)*4");   /* wyrażenie w notacji infiksowej    */
    cout<<"wyrazenie przed konwersja:  "<<wyrazenie<<endl;

    unsigned int i = 0;
    while( i < wyrazenie.size())
    {
           if( wyrazenie[i] >= 48 && wyrazenie[i] <= 57 )   /* trafiliśny na cyfrę  */
           {
                   RPNQueue.push(wyrazenie[i]);
           }

           else if(wyrazenie[i] == '(' )
           {
                    RPNStack.push(wyrazenie[i]);
           }
           else if(wyrazenie[i] == ')' )
           {
                while( RPNStack.top() != '(' )
                {  
                          RPNQueue.push( RPNStack.top() );
                          RPNStack.pop();
                }
                if(  RPNStack.top() ==  '(')
                      RPNStack.pop();
           }
           else if(  wyrazenie[i] == '+')
           {
                     while( !RPNStack.empty() && RPNStack.top() ==  '*')
                     {       
                          RPNQueue.push( RPNStack.top() );
                          RPNStack.pop();
                     }
                     RPNStack.push(wyrazenie[i]);
           }
           else if(  wyrazenie[i] ==  '*')
                     RPNStack.push(wyrazenie[i]);
                
           ++i;
    }     
    while( !RPNStack.empty())
    {
          RPNQueue.push( RPNStack.top() );
          RPNStack.pop();  
    }
    i = 0;
    cout<<"wyrazenie po konwersji:     ";
    while( !RPNQueue.empty())
    {
                  cout<<RPNQueue.front();
                  RPNQueue.pop();
    }
    cout<<endl;
    system("PAUSE");
    return 0;
}