// http://zh.wikipedia.org/zh-tw/调度场算法

#include <cstdlib>
#include <iostream>
#include <string>
#include <sstream>
#include <cctype>           // used for function 'isdigit' 
#include <stack>
#include <queue>

using namespace std;

// list of constants specifying specific error messages  
const int OperatorExpected = 0,
          OperandExpected = 1,
          MissingLeftParenthesis = 2,
          MissingRightParenthesis = 3,
          InvalidInput = 4;

// labels designating the parentheses characters 
const char leftparenthesis  = '(',
           rightparenthesis = ')';
       
// checks if character is an operator or parentheses   
int isoperator(char ch)   
{   
    if (ch == '+' || ch == '-' || ch == '*' ||   
        ch == '/' || ch == '(' )   
        return 1;   
    else   
        return 0;   
}   
       
// checks if character is a whitespace character   
int iswhitespace(char ch)   
{   
    if (ch == ' ' || ch == '\t' || ch == '\n')   
       return 1;   
    else   
       return 0;   
}   
       
// error handling function   
void error(int n)   
{   
    // table gives the different error messages   
    string errormsgs[] = {   
           "Operator expected",   
           "Operand expected",   
           "Missing left parenthesis",   
           "Missing right parenthesis",   
           "Invalid input"   
           };   
                               
    // the parameter n is an error message index   
    // print the message and terminate the program     
    cerr << errormsgs[n] << endl;
    
    //system("PAUSE");   
    exit(1);   
}

// convert double to string
string float2string(float value) {
    stringstream sstr;
    sstr << value;
    return sstr.str();
}

// convert char to string
string char2string(char value) {
    stringstream sstr;
    sstr << value;
    return sstr.str();
}
       
int main()   
{
    // infix  : 5 + ((1 + 2) * 4) - 3
    // postfix: 5 1 2 + 4 * + 3 -
     
    // stack: OprStack
    stack<char> OprStack;

	// queue: postfix
	queue<string> postfix;
	
    float number;   
    char ch;   

    // init stack and push 'End' mark
    OprStack.push('!');
      
    // process the expression until '=' is read   
    while (cin.get(ch) &&  ch != '=')   
    {   
        //  ********  process a floating point operand  ********   
        if (isdigit(ch) || ch == '.')   
        {   
            // put back digit or '.' and read number   
            cin.putback(ch);   
            cin >> number;
            // push number
            postfix.push( float2string(number));

        }   
        //  *********  process an operator  **********   
        else if (isoperator(ch))   
        {   
            if ( OprStack.top()=='*' || OprStack.top()=='/' )
            {
                // push operator
                postfix.push( char2string(OprStack.top()));
                OprStack.pop();
            }
            OprStack.push(ch);
            
        }   
        //  *********  process a right parenthesis  **********   
        else if (ch == rightparenthesis)   
        {
             int loop = 1;

             while (loop==1)
             {
                // push operator
                postfix.push( char2string(OprStack.top()));
                OprStack.pop();
                if ( OprStack.top()=='(' )
                {
                   loop=0;
                   OprStack.pop();
                }
             }
		}      
        //  *********  have some invalid input  **********   
        else if (!iswhitespace(ch))   
             error(InvalidInput);   
    }   

    // push all operator
    while (!OprStack.empty())
    {
        postfix.push( char2string(OprStack.top()));
        OprStack.pop();
    }
           
    // display queue
	cout << "Postfix:" ;
    while (!postfix.empty())
    {
        cout << " " << postfix.front();       
        postfix.pop();    	
    }
    cout << endl;
    
    //system("PAUSE");
    return 0;
}