// Phil Ottewell's STL Course - http://www.pottsoft.com/home/stl/stl.htmlx
//
// Example 5.2                  © Phil Ottewell 1997 <philXZY@pottsoftXZY_REMOVEXYZ.com>
//
// Purpose:
//          Transform an arthmetic expression into reverse polish
//          notation, substitute symbols and evaluate.

// ANSI C Headers
#include <ctype.h>
#include <float.h>
#include <math.h>
#include <stdlib.h>

// C++ and STL Headers
#include <iostream>
#include <map>
#include <string>
#include <stack>

// Function prototypes
double perform_operation( char oper, double operand1, double operand2 );
int precedence( char oper );

#ifdef _WIN32
using namespace std;
#endif

#ifdef _WIN32
# pragma warning(disable:4786) // We know basic_string generates long names :-)
#endif

int main( int argc, char *argv[] )
{
    size_t ip;
    double value, operand[2];
    char nxc, cstring[64];
    string expression, item;
    stack< string > x, y;
    map< string, double > symbol_values;
//  End of declarations ...

//  Set a couple of built-in symbols
    symbol_values["pi"] = 3.1415926535898; 
    symbol_values["c"] = 299792459.0;   // Speed of light, m/s
    symbol_values["e"] = 1.602e-19;     // Electron charge, Coulombs
    symbol_values["me"] = 9.10956e-31;  // Electron rest mass, kg
    symbol_values["mp"] = 1.672614e-27; // Proton rest mass, kg
    symbol_values["mn"] = 1.674920e-27; // Neutron rest mass, kg

    if ( argc < 2) {
      cout << "Enter expression: ";
      getline( cin, expression );
    } else {
      expression = *argv[1]; // Use expression from command line if given
    }

//  Junk everything except alphanumerics, brackets and operators
    ip = 0;
    while ( ip < expression.length() ) {
      nxc = expression.at(ip);
      if ( isspace(nxc) ||
           (!isalnum(nxc) && !precedence(nxc) && nxc != '(' && nxc != ')') ) {
        expression.erase(ip,1);
      } else {
        ++ip;
      }
    }
    if ( !expression.length() ) {
      cout << "Bye" << endl;
      return( EXIT_SUCCESS );
    }

//  Add space as an end of expression marker and to allow final pass thru loop
    expression = expression + " ";

//  Process the expression

    while ( expression.length() ) {
      nxc = expression.at(0);
      if ( nxc == '(' ) {
        y.push( expression.substr(0,1) ); // Push '(' onto Operator stack
        expression.erase(0,1);

      } else if ( nxc == ')' ) {
        while ( !y.empty() ) { // If right brack loop until left bracket reached
          item = y.top(); y.pop();
          if ( item.at(0) == '(' ) {
            break;
          } else {
            x.push( item );
          }
        }
        expression.erase(0,1);

      } else if ( !precedence( nxc ) ) {
//      If not brackets or operator stick value or variable on stack
        ip = expression.find_first_of("^*/+-() ");
        if ( ip == expression.npos ) ip = expression.length();
        item = expression.substr(0,ip);
        x.push( item ); // Push value string onto stack
        expression.erase(0,ip);

      } else {
//      nxc is operator or space
        while ( 1 ) {
          if ( y.empty() ) {
            y.push( expression.substr(0,1) );
            break;
          }

          item = y.top(); y.pop();
          if ( item.at(0) == '(' || precedence(nxc) > precedence(item.at(0)) ) {
            y.push( item );
            y.push( expression.substr(0,1) );
            break;
          } else {
            x.push( item );
          }
        }
        expression.erase(0,1);
      }
    }

//  Put stack into correct order and substitute symbols if any
    while ( !x.empty() ) {
      item =  x.top(); x.pop();
      nxc = item.at(0);
      if ( !precedence(nxc) && !isdigit(nxc) ) {
        value = symbol_values[item]; // Not oper or number, must be a symbol
        sprintf( cstring, "%.*g", DBL_DIG, value );
        item = string(cstring);
      }
      cout << item  << endl;
      y.push( item );
    }
    cout << endl;

//  Now evaluate, using X stack to hold operands until we meet an operator
    while ( !y.empty() ) {
      item =  y.top(); y.pop();
      nxc = item.at(0);
      if ( nxc == ' ') break; // End marker
      if ( !precedence(nxc) ) {
        x.push( item ); // Must be number - throw it on X stack till we need it
      } else {
        operand[0] = operand[1] = 0.0;
        operand[1] = atof( x.top().c_str() ); x.pop(); // Get values and do op
        if ( !x.empty() ) {
          operand[0] = atof( x.top().c_str() ); x.pop();
        }
        value = perform_operation( nxc, operand[0], operand[1] );
        sprintf( cstring, "%.*g", DBL_DIG, value );
        item = string( cstring );
        x.push( item ); // Put result on X stack
      }
    }
    cout << x.top() << endl;

    return( EXIT_SUCCESS );
}

int precedence( char oper )
{
//  Returns an precedence of operator, or 0 if it isn't a known operator
//  Known Operators: " ","+","-","*","/","^"
//                    |                   | 
//                  Do nothing           Raise to power

    if ( oper == '^') return( 4 );
    if ( oper == '*'  ||  oper == '/') return( 3 );
    if ( oper == '+'  ||  oper == '-') return( 2 );
    if ( oper == ' ') return( 1 );
    return( 0 ); //    Not operator
}

double perform_operation( char oper, double operand1, double operand2 )
{
//  Return the result of performing the required operation on the operands.

    if ( oper == '^') return( pow( operand1, operand2 ) );
    if ( oper == '*') return( operand1*operand2 );
    if ( oper == '/') return( operand1/operand2 );
    if ( oper == '+') return( operand1+operand2 );
    if ( oper == '-') return( operand1-operand2 );
    return( 0.0 ); // Invalid operator
}