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