/*****************************************************************************
 * File: RPNEvaluate.cpp
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * Implementation of the RPNEvaluate interface to lex and evaluate RPN
 * expressions.
 *
 * RPN evaluation is particularly elegant and simple.  We maintain a stack of
 * integers corresponding to the parsed versions of the numbers we've seen so
 * far.  Upon seeing another token, if the token is an integer, we add it to
 * the stack.  If it is an operator, we pop the top two tokens from the stack,
 * apply the operator to the operands, then replace them atop the stack.  If
 * at the end of this operation we end up with a single value on the stack and
 * at no time in the process tried applying an operator to a singleton stack,
 * then the evaluation succeeds.
 */

#include "RPNEvaluate.hh"
#include "Lexer.hh"       // Generated by strain from Expression.strain
#include <sstream>
#include <stack>
#include <stdexcept>
using namespace std;
using namespace strain;

/* Lexing a string works by taking the string, funneling it through the strain
 * lexer, then funneling it back out to a vector.
 */

vector<string> RPNLex(const string& expr) {
  vector<string> result;

  /* Build up a stringstream holding the string to lex, then wrap it up in a
   * strain lexer.
   */

  istringstream streamWrapper(expr);
  Lexer lexer(streamWrapper);

  /* Continously read a token/lexeme pair from the lexer until we find the
   * end of the stream.  To do this, we use the comma operator to, in the same
   * expression, read the lexeme and then check if it was valid.
   */

  pair<Lexer::LexemeType, Lexeme> lexeme;
  while (lexeme = lexer.next(), lexeme.first != Lexer::None)
    result.push_back(lexeme_cast<const string>(lexeme.second));

  return result;
}

/* A utility function to convert a string representation of an integer to an
 * integer.  It's assumed that the integer is well-formed, which is in general
 * a safe assumption because the lexer guarantees this.
 */

static int StringToInteger(const string& str) {
  /* Funnel the string through a stringstream to do the conversion. */
  istringstream converter(str);

  /* Pull out an integer. */
  int result;
  converter >> result;

  return result;
}

/* Given a string, returns whether that string is an operator. */
static bool IsOperator(const string& token) {
  return token == "+" ||
         token == "-" ||
         token == "*" ||
         token == "/" ||
         token == "%";
}

/* Given a string representing an operator and its operands, applies that
 * operator to the operands.
 */

static int ApplyOperator(const string& op, int lhs, int rhs) {
  /* These next operations are always well-defined. */
  if (op == "+"return lhs + rhs;
  if (op == "-"return lhs - rhs;
  if (op == "*"return lhs * rhs;
  
  /* Division only valid if rhs != 0. */
  if (op == "/") {
    if (rhs == 0throw runtime_error("Attempt to divide by zero.");
    return lhs / rhs;
  }

  /* Modulus only valid if both operands are nonnegative. */
  if (op == "%") {
    if (lhs < 0 || rhs < 0throw runtime_error("Modulus with negative arguments.");
    if (rhs == 0throw runtime_error("Attempt to mod by zero.");
    return lhs % rhs;
  }

  /* Some unknown operator? */
  throw runtime_error("Unknown operator: " + op);
}

/* Evaluating an RPN expression maintains a stack and evaluates by growing and
 * shrinking the stack as operators are applied or new literals found.
 */

int RPNEvaluate(const vector<string>& expr) {
  /* Stack of literals seen so far. */
  stack<int> s;

  /* Continue processing tokens until everything has been evaluated. */
  for (size_t i = 0; i < expr.size(); ++i) {
    /* If the next token is an operator, apply it to the top two arguments on
     * the stack and store the result.
     */

    if (IsOperator(expr[i])) {
      /* Confirm that the operands exist. */
      if (s.size() < 2)
        throw runtime_error("Not enough operands for " + expr[i]);

      /* Extract the operands. */
      int rhs = s.top(); s.pop();
      int lhs = s.top(); s.pop();
      
      /* Apply the operator and store the result. */
      s.push(ApplyOperator(expr[i], lhs, rhs));
    }
    /* Otherwise, the next element must be a value to place atop the stack. */
    else
      s.push(StringToInteger(expr[i]));
  }

  /* Once we've applied all the appropriate operators, we need to check that
   * we ended up with exactly one item on the stack.  If not, then we have
   * either too few arguments or too many operands.
   */

  if (s.size() != 1)
    throw runtime_error("Expression does not evaluate to a single term.");

  return s.top();
}