#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <string>
#include <iostream>
#include <sstream>
#include "ExprComputer.h"

using namespace std;

int main(int argc, char * argv[])
{
    CExprComputer loExprComputer;
    // all these below can work right,comment is same as the content 'couted'.
    stringstream lss;
    lss << "1 + 2 * 3 =";

    cout <<"test trans stringstream in and cout." <<endl;
    loExprComputer.TransInfix2Postfix(lss, cout);

    cout <<"test trans cin and cout." <<endl;
    loExprComputer.TransInfix2Postfix(cin, cout);

    stringstream lss2;
    cout <<"test trans cin and stringstream out." <<endl;
    loExprComputer.TransInfix2Postfix(cin, lss2);
    cout << lss2.str() <<endl;

    lss.seekg(0);
    cout <<"test stringstream in computeInfix." <<endl;
    cout << lss.str();
    cout << loExprComputer.ComputeInfix(lss) <<endl;

    cout <<"test cin in computeInfix." <<endl;
    cout << loExprComputer.ComputeInfix(cin) <<endl;

    stringstream lssPostfix;
    lssPostfix << "1 2 3 * + =";
    cout <<"test stringstream in ComputePostfix." <<endl;
    cout << lssPostfix.str();
    cout << loExprComputer.ComputePostfix(lssPostfix) <<endl;

    cout <<"test cin in ComputePostfix." <<endl;
    cout << loExprComputer.ComputePostfix(cin) <<endl;

    cout <<"Test completed." <<endl;
    exit(0);
}

#ifndef __EXPR_COMPUTE_H__
#define __EXPR_COMPUTE_H__

#include <iostream>
#include <sstream>
#include <stack>
using namespace std;

// argument to input
#define _IN_ 

// argument to output
#define _OUT_ 

class CExprComputer
{
public :
    int ComputeInfix(_IN_ istream& aisExpr);
    int ComputePostfix(_IN_ istream& aisExpr);

    // Transform a infix expression to Postfix expression
    int TransInfix2Postfix(_IN_ istream& aisInfix,
            _OUT_ ostream& aosPostfix);

private :
    // Stack should be empty,Dump the information still in Stack and exit
    void DumpStack();

    // Output all information still in Stack
    void OutputStack();

    // Make sure Stack is not empty when it should not.
    void CheckStack();

    // I don't know why Stack operator is so few.And why I need to
    // clear the Stack in this example? GOD knows.
    void ClearStack();

    // Read a int or a operator from a stream
    bool ReadStream(_IN_ istream& aisExpr, _OUT_ int & aiReaded,  _OUT_ bool & abIsChar);

    // Process a Operator
    void ProcessOperator(char ac, _OUT_ ostream& aosPostfix);

    void ComputeOperator(char ac);

    stack<int> miSta;
};

#endif

#include "ExprComputer.h"

void CExprComputer::DumpStack()
{
    if(!miSta.empty())
    {
        cout <<"stack: ";
        OutputStack();
        cout <<endl;
        exit(1);
    }

}

void CExprComputer::OutputStack()
{
    while(!miSta.empty())
    {
        cout <<miSta.top() <<" ";
        miSta.pop();
    }
}

void CExprComputer::ClearStack()
{
    while(!miSta.empty())
    {
        miSta.pop();
    }
}

void CExprComputer::CheckStack()
{
    if(    miSta.empty() )
    {
        cout <<"Invalid expression input." <<endl;
        exit(1);
    }
}

bool CExprComputer::ReadStream(_IN_ istream& aisExpr, _OUT_ int & aiReaded,  _OUT_ bool & abIsChar)
{
    if(aisExpr.eof())
    {
        return false;
    }

    // try to read stream as a int
    abIsChar = false;
    int li;
    aisExpr >> li;

    // if next thing in stream is not a int, back a char and read it
    if(aisExpr.fail())
    {
        aisExpr.clear();
        aisExpr.unget();
        char c;
        aisExpr >> c;
        if(c != '=')
        {
            aiReaded = c;
            abIsChar = true;
            return true;
        }
        else
        {
            return false;
        }
    }

    aiReaded = li;
    return true;
}

void CExprComputer::ProcessOperator(char ac, _OUT_ ostream& aosPostfix)
{
    switch(ac)
    {
        case '(':
        {
            // save the '('
            miSta.push(ac);
            break ;
        }
        case ')':
        {
            char lc;
            CheckStack();

            // output all operator until find a '('
            while( (lc = miSta.top()) != '(' )
            {
                aosPostfix << lc <<" ";
                miSta.pop();
                CheckStack();
            }

            // the first '(' in stack,We just need pop it
            miSta.pop();
            break ;
        }
        case '*':
        {
            char lc;

            // output all operator until find a lower level operator
            while( !miSta.empty() &&
                    ((lc = miSta.top()) != '(') &&
                    ( lc != '+') )
            {
                aosPostfix <<lc <<" ";
                miSta.pop();
            }

            miSta.push(ac);
            break ;
        }
        case '+':
        {

            char lc;

            // output all operator until find a lower level operator
            while( !miSta.empty() &&
                    ((lc = miSta.top()) != '(') )
            {
                aosPostfix <<lc <<" ";
                miSta.pop();
            }

            miSta.push(ac);
            break ;
        }
        default :
        {
            cout <<"Don't support this operator." <<endl;
            exit(1);
        }
    }

}

int CExprComputer::TransInfix2Postfix(_IN_ istream& aisInfix,
        _OUT_ ostream& aosPostfix)
{
    int li = 0;
    bool lbIsChar = false;
    while( ReadStream(aisInfix, li, lbIsChar) )
    {
        // number need immediately output
        if(!lbIsChar)
        {
            aosPostfix <<li <<" ";
        }
        else
        {
            char lc = static_cast<char>(li);
            ProcessOperator(lc, aosPostfix);
        }
    }

    while(!miSta.empty())
    {
        aosPostfix <<(char)miSta.top() <<" ";
        miSta.pop();
    }
    aosPostfix <<'=' <<endl;

    return 1;
}

int CExprComputer::ComputePostfix(_IN_ istream& aisExpr)
{
    ClearStack();

    int li = 0;
    bool lbIsChar = false;
    while( ReadStream(aisExpr, li, lbIsChar) )
    {
        // number need immediately output
        if(!lbIsChar)
        {
            miSta.push(li);
        }
        else
        {
            char lc = static_cast<char>(li);
            ComputeOperator(lc);
        }
    }

    CheckStack();
    int liResult = miSta.top();
    miSta.pop();

    DumpStack();

    return liResult;
}

void CExprComputer::ComputeOperator(char ac)
{
    // get lhs and rhs
    CheckStack();
    int lilhs = miSta.top();
    miSta.pop();
    CheckStack();
    int lirhs = miSta.top();
    miSta.pop();

    switch(ac)
    {
        case '*':
        {
            int liResult = lilhs * lirhs;
            miSta.push(liResult);
            break ;
        }
        case '+':
        {
            int liResult = lilhs + lirhs;
            miSta.push(liResult);
            break ;
        }
        default :
        {
            cout <<"Don't support this operator." <<endl;
            exit(1);
        }
    }
}

int CExprComputer::ComputeInfix(_IN_ istream& aisExpr)
{
    stringstream lss;
    TransInfix2Postfix(aisExpr, lss);
    return ComputePostfix(lss);
}