// rpn.cpp
// Glenn G. Chappell
// 6 Nov 2009
//
// For CS 311 Fall 2009
// Reverse Polish Notation expression evaluation
// Example application of a Stack

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <sstream>
using std::istringstream;
#include <string>
using std::string;
#include <stack>
using std::stack;


// toInt
// Converts a string to an int
// Pre: None.
// Post:
//    Return value is int version of s,
//     as determined by operator>>(istream &, int &).
// No-Throw Guarantee
int toInt(const string & str)
{
    istringstream istr(str);
    int n;
    istr >> n;
    return n;
}


// rpn
// Reverse-Polish Notation computation.
// Given a string and a stack, interpret the string as a command
// and use it to operate on the stack.
// Command type is determined by its first character.
//     0-9: positive int to push on stack.
//      (Negative values cannot be entered.)
//     +, -, *, /: binary operator. ("/" is integer division,
//      with a/0 returning 0 for every integer a.)
//      Operands are taken from top two items on stack.
//      Result is left in top item on stack.
// Pre:
//     None.
// Post:
//     s (Stack) was transformed appropriately, if possible.
//     If s.size() was too small to complete operation,
//      or if token does not have a first character listed above,
//      then s is unchanged.
// May throw std::bad_alloc on out-of-memory.
// Basic Guarantee
void rpn(const std::string & token,
         std::stack<int> & s)
{
    int a, b;           // Temporary vars to hold popped values

    if (token.empty())  // Can't test first char if there isn't one
        return;

    switch (token[0])   // Classify token by first char
    {
    case '0':  // '0' - '9': push number
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
        s.push(toInt(token));
        break;
    case '+':  // '+': add
        if (s.size() < 2) return;
        b = s.top();
        s.pop();
        a = s.top();
        s.pop();
        s.push(a + b);
        break;
    case '-':  // '-': subtract
        if (s.size() < 2) return;
        b = s.top();
        s.pop();
        a = s.top();
        s.pop();
        s.push(a - b);
        break;
    case '*':  // '*': multiply
        if (s.size() < 2) return;
        b = s.top();
        s.pop();
        a = s.top();
        s.pop();
        s.push(a * b);
        break;
    case '/':  // '/': divide (integer)
        if (s.size() < 2) return;
        b = s.top();
        s.pop();
        a = s.top();
        s.pop();
        if (b == 0)
            s.push(0);  // Prevent div-by-zero error by letting a/0 be 0.
        else
            s.push(a / b);
        break;
    default:   // Unknown symbol: do nothing
        break;
    }
}


// rpnLoop
// Repeatedly inputs space-separated token from standard input,
// operates on Stack (RPN operations) and prints top of Stack.
// Pre: None.
// Post:
//     Input prompted for and read, RPN operations performed,
//      and results printed.
// May throw std::bad_alloc on stack overflow/out of memory.
// Strong Guarantee
void rpnLoop()
{
    std::stack<int> s;

    while (true)
    {
        std::string prompt = "Command (q to quit): ";

        // Get line from stdin
        cout << endl;
        cout << prompt;
        std::string line;
        std::getline(cin, line);
        while (!cin)  // Error reading? Clear error & try again
        {
            if (cin.eof())
                return;
            cin.clear();
            cin.ignore();
            cout << prompt;
            std::getline(cin, line);
        }
        cout << endl;

        // Get space-deliminted commands from line
        std::istringstream lineStream(line);
        while (lineStream)
        {
            // Get space-delimited command ("token") from line
            std::string token;
            lineStream >> token;

            // If we could not read, call it end-of-line
            //  and go get another line
            if (!lineStream)
                break;

            // Quit?
            if (!token.empty() && (token[0] == 'q' || token[0] == 'Q'))
                return;

            // Do RPN processing
            rpn(token, s);

            // Print top of stack
            if (s.empty())
                cout << "<Empty stack>" << endl;
            else
                cout << "Top: " << s.top() << endl;
        }
    }
}


int main()
{
    rpnLoop();
    cout << endl;
    return 0;
}