// ======================================================================
//
// by David O'Neil, 1/2/00
// If you make any changes or improvements, let me know.
//
// david@randommonkeyworks.com
//
// Thanks, and enjoy!
// ======================================================================
//eliminate these #include and using statements if breaking this file apart
#include <vector>
#include <iostream>
using std::vector;
using std::cin;
using std::cout;
// ======================================================================
// The original Stack.h file follows
// ======================================================================
#ifndef Stack_h
#define Stack_h
#include <vector>
using std::vector; */
// Class to manipulate a float vector
class Stack {
private:
vector<float> stack;
public:
void addToStack(float);
void add();
void subtract();
void multiply();
void divide();
void power();
float getAnswer();
};
//#endif //Stack.h - uncomment if separating
// ======================================================================
// The original Objects.h file follows
// ======================================================================
#ifndef Objects_h
#define Objects_h
#include "Stack.h" */
//the order of this enumeration is critical for correct operation
enum precedence_ {PrecGet, PrecEnd, PrecParen, PrecAddSub, PrecMulDiv, PrecPow,
PrecVal, NoPrec };
// ======================================================================
// Base class for various objects (ie - Numbers, Delimiters ('+', '-', '*'...))
// ======================================================================
class Object {
private:
Stack *numStack;
protected:
Object(precedence_);
public:
//will make precedence private in future, but for simple test leave public
precedence_ precedence;
virtual void execute();
Object();
};
// ======================================================================
// Classes derived from the base Object class
// ======================================================================
// Get class derived from base class. This object is placed on the bottom
// of the stack so that the precedence checking algorithm will fetch the next
// object for the stack when the stack is reduced to only having this on it.
class Get: public Object {
public:
Get();
};
// Number class derived from Base class
class Number : public Object {
private:
void execute();
float number;
Stack *numStack;
public:
Number(float, Stack*);
float getNumber();
};
// Plus derived from Base (handles the '+' sign)
class Plus : public Object {
private:
void execute();
Stack *numStack;
public:
Plus(Stack* stack);
};
// Minus derived from Base (handles the '-' sign)
class Minus : public Object {
private:
void execute();
Stack *numStack;
public:
Minus(Stack* stack);
};
// Minus derived from Base (handles the '*' sign)
class Multiply : public Object {
private:
void execute();
Stack *numStack;
public:
Multiply(Stack* stack);
};
// Divide derived from Base (handles the '/' sign)
class Divide : public Object {
private:
void execute();
Stack *numStack;
public:
Divide(Stack* stack);
};
// Power derived from Base (handles the '^' sign)
class Power : public Object {
private:
void execute();
Stack *numStack;
public:
Power(Stack* stack);
};
// LParen derived from Base (handles '(' )
class LParen : public Object {
private:
void execute();
public:
LParen();
bool isRightParen;
};
// RParen derived from Base (handles ')' )
class RParen : public Object {
private:
void execute();
public:
RParen();
bool isRightParen;
};
// End derived from Base (handles the string EOL '\0')
class End : public Object {
public:
End();
};
//#endif //Objects_h - uncomment if breaking this file up
// ======================================================================
// The original Parser.h file follows
// ======================================================================
#ifndef Parser_h
#define Parser_h
#include "Objects.h"
#include <vector>
using std::vector; */
const int MaxStr = 80;
// Class to implement the parsing of the expression
class Parser {
private:
Stack floatStack;
char *str;
bool getObject();
vector<Object *> obStack;
void showCommands();
void run();
bool isObject(char *);
Object *tempOb;
public:
bool parse(char *str_);
double answer;
};
//#endif //Parser_h - reinclude if breaking file up
// ======================================================================
// The original Parser.cpp file follows
// ======================================================================
#pragma hdrstop
#include <condefs.h>
#include "parser.h"
#include <iostream>
using std::cout;
using std::cin;
// ======================================================================
USEUNIT("parser.cpp"); //these three lines will need to be recreated
USEUNIT("Stack.cpp"); //by adding these units to your project
USEUNIT("Objects.cpp"); //if you break this file apart
// ======================================================================
#pragma argsused */
int main() {
char expstr[MaxStr+1];
for (;;) {
Parser parse; //scope it so ctor and dtor's get called each time
cout << "Enter expression\n('Enter' to quit, ? for help): ";
cin.getline(expstr, MaxStr);
if (*expstr == NULL) break;
if (parse.parse(expstr))
cout << "Answer is: " << parse.answer << "\n\n";
else cout << "\n\n";
}
return 0;
}
// ======================================================================
// The original Parser.cpp file follows
#include "Parser.h"
#include <iostream>
using std::cout;
using std::cin; */
// parse() - main entry point into parser class. Returns true if it parsed correctly.
bool Parser::parse(char *str_) {
Get junk;
tempOb = &junk;
str = str_;
if (*str == '?') {
showCommands();
return false;
}
//first, place a Get object on the stack...
Get *get = new Get;
obStack.push_back(get);
while (tempOb->precedence != PrecEnd) {
if (!getObject()) {
return false;
}
}
//now, place an End object onto the list
End *end = new End;
obStack.push_back(end);
//now, run the list of objects:
run();
//now, get the last value on the stack:
answer = floatStack.getAnswer();
//now, free the space back up
while (!obStack.empty()) {
delete obStack.back();
obStack.pop_back();
}
return true;
}
// getObject() - Gets the current object being pointed to by str.
bool Parser::getObject() {
//skip over whitespace
while (isspace(*str)) ++str;
//determine if at the end of the string
if (!*str) {
End *end = new End;
tempOb = end;
//if (tempOb->precedence != PrecEnd) { cout << "Oh no\n"; }
obStack.push_back(end);
return true;
}
switch (*str) {
case '+': {
Plus *plus = new Plus(&floatStack);
tempOb = plus;
obStack.push_back(plus);
*str++;
break; }
case '-': {
Minus *minus = new Minus(&floatStack);
tempOb = minus;
obStack.push_back(minus);
*str++;
break; }
case '*': {
Multiply *mul = new Multiply(&floatStack);
tempOb = mul;
obStack.push_back(mul);
*str++;
break; }
case '/': {
Divide *div = new Divide(&floatStack);
tempOb = div;
obStack.push_back(div);
*str++;
break; }
case '^': {
Power *pow = new Power(&floatStack);
tempOb = pow;
obStack.push_back(pow);
*str++;
break; }
case '(': {
LParen *lparen = new LParen();
tempOb = lparen;
obStack.push_back(lparen);
*str++;
break; }
case ')': {
RParen *rparen = new RParen();
tempOb = rparen;
obStack.push_back(rparen);
*str++;
break; }
default:
//convert the following characters into a floating point number
// floats can have 7 digits of precision, but we will allow the
// user to input as much as they want.
//First, check to make sure that it is indeed a number
if (!isdigit(*str)) {
cout << "\nunknown command\n";
return false;
}
char tempval[MaxStr];
int i = 0;
do {
tempval[i++] = *str++;
}
while (isdigit(*str) || *str == '.');
tempval[i] = '\0';
Number *num = new Number(atof(tempval), &floatStack);
tempOb = num;
//now, add the object ptr to the list:
obStack.push_back(num);
}
return true;
}
// isObject() - tells if the character at str is an object
bool Parser::isObject(char *tstr) {
switch (*tstr) {
case '+':
case '-':
case '*':
case '/':
case '^':
case '(':
case ')':
return true;
default:
return false;
}
}
// showCommands() - shows the commands available in the parser.
void Parser::showCommands() {
cout << "\n";
cout << "Available Commands:\n";
cout << " + - plus\n";
cout << " - - minus\n";
cout << " * - multiply\n";
cout << " / - divide\n";
cout << " ^ - power\n";
cout << "\nsimply enter expression like: 5*(4^5+2)\n";
}
// run() - finally executes the list of objects
void Parser::run() {
int i = -1, tStackSize = 0;
vector<Object*> tStack;
precedence_ precLast, precPrior;
//first, place the first 'Get' onto the stack
tStack.push_back(obStack[++i]);
//now, start running the stack
do {
//push another object onto the stack
tStack.push_back(obStack[++i]);
++tStackSize;
//simply in for debugger inspecting
//to help prog'r understand workings
precPrior = tStack[tStackSize-1]->precedence;
precLast = tStack[tStackSize]->precedence;
while (precPrior >= precLast) {
//check for stack reduction ( '(' and ')' objects)
if (precLast == PrecParen) {
if (RParen *rpar = dynamic_cast<RParen*>(tStack[tStackSize])) {
// the last obj is a right parenthisis
// if the previous obj is not parenthesis
// it needs to be processed
if (tStack[tStackSize-1]->precedence > PrecParen) goto breakout;
//that leaves the previous obj as being a parenthesis
if (LParen *lpar = dynamic_cast<LParen*>(tStack[tStackSize-1])) {
//need to pop both parenthesis off the stack
tStack.pop_back();
tStack.pop_back();
tStackSize -= 2;
if (tStackSize < 1) break;
// these two lines can
// be elim when precLast
// &precPrior eliminated
precPrior = tStack[tStackSize-1]->precedence;
precLast = tStack[tStackSize]->precedence;
continue;
}
//the previous object was a right parenthesis - error
cout << "\n'(' not reduced - meaningless answer\n\n";
return;
}
//the last object must be a left parenthesis. see if prior is parenthesis
if (tStack[tStackSize-1]->precedence > PrecParen) break;
//now, need to check for prior object being left parenthesis
if (LParen *lpar = dynamic_cast<LParen*>(tStack[tStackSize-1])) { //get the next
tStack.push_back(obStack[++i]); //stack item
++tStackSize;
precPrior = tStack[tStackSize-1]->precedence;
precLast = tStack[tStackSize]->precedence;
continue;
}
//big problem if it reaches here. Last item = '(' and prior = ')'
cout << "\nbad reduction. reduced to ')('\n\n";
return;
}
breakout:
tStack[tStackSize-1]->execute();
tStack[tStackSize-1] = tStack[tStackSize];
tStack.pop_back();
tStackSize--;
precPrior = tStack[tStackSize-1]->precedence;
precLast = tStack[tStackSize]->precedence;
}
}
while (tStack[tStackSize]->precedence != PrecEnd);
}
// ======================================================================
// The original Objects.cpp file follows
// ======================================================================
#include "Objects.h"
#include <iostream>
using std::cout; */
// ======================================================================
// Class implementations of Base objects (Numbers, Add, Subtract, Multiply, Divide)
// ======================================================================
// Object::(functions) ***********************************
Object::Object() : precedence(NoPrec), numStack(NULL) { }
Object::Object(precedence_ prec) : precedence(prec) { }
//virtual function - give programmer clue...
void Object::execute() { cout << "\nUndefined Operator\nMeaningless answer\n\n"; }
// ======================================================================
// End of virtual base class definition, now on to the derived objects...
// ======================================================================
// Number::(functions) ***********************************
Number::Number(float num, Stack *stackToUse)
: number(num), numStack(stackToUse), Object(PrecVal) { }
//virtual override
void Number::execute() { numStack->addToStack(number); }
//public access...
float Number::getNumber() { return number; }
// Get::() ***********************************
Get::Get() : Object(PrecGet) { }
// Plus::() ***********************************
Plus::Plus(Stack* stack) : numStack(stack), Object(PrecAddSub) { }
void Plus::execute() { numStack->add(); }
// Minus::() ***********************************
Minus::Minus(Stack* stack) : numStack(stack), Object(PrecAddSub) { }
void Minus::execute() { numStack->subtract(); }
// Multiply::() ***********************************
Multiply::Multiply(Stack* stack) : numStack(stack), Object(PrecMulDiv) { }
void Multiply::execute() { numStack->multiply(); }
// Divide::() ***********************************
Divide::Divide(Stack* stack) : numStack(stack), Object(PrecMulDiv) { }
void Divide::execute() { numStack->divide(); }
// Power::() ***********************************
Power::Power(Stack* stack) : numStack(stack), Object(PrecPow) { }
void Power::execute() { numStack->power(); }
// LParen::() ***********************************
LParen::LParen() : isRightParen(false), Object(PrecParen) { }
void LParen::execute() { cout << "\nshift reduction incorrect\nmeaningless answer\n\n"; }
// RParen::() ***********************************
RParen::RParen() : isRightParen(true), Object(PrecParen) { }
void RParen::execute() { cout << "\nshift reduction incorrect\nmeaningless answer\n\n"; }
// End::() ***********************************
End::End() : Object(PrecEnd) { }
// The original Stack.cpp file follows
#include "Stack.h"
#include <iostream>
using std::cout; */
// add() - commands the stack to add the top two numbers
void Stack::add() {
int i = stack.size()-1;
if (i < 1) {
cout << "\nnot enough variables to add\nmeaningless answer\n\n";
return;
}
stack[i-1] += stack[i];
stack.pop_back();
}
// subtract() - commands the stack to subtract the top two numbers
void Stack::subtract() {
int i = stack.size()-1;
if (i < 1) {
cout << "\nnot enough variables to subtract\nmeaningless answer\n\n";
return;
}
stack[i-1] -= stack[i];
stack.pop_back();
}
// multiply() - commands the stack to multiply the top two numbers
void Stack::multiply() {
int i = stack.size()-1;
if (i < 1) {
cout << "\nnot enough variables to multiply\nmeaningless answer\n\n";
return;
}
stack[i-1] *= stack[i];
stack.pop_back();
}
// multiply() - commands the stack to multiply the top two numbers
void Stack::divide() {
int i = stack.size()-1;
if (i < 1) {
cout << "\nnot enough variables to divide\nmeaningless answer\n\n";
return;
}
stack[i-1] /= stack[i];
stack.pop_back();
}
// power() - commands the stack to multiply the top two numbers
void Stack::power() {
int i = stack.size()-1;
if (i < 1) {
cout << "\nnot enough variables to divide\nmeaningless answer\n\n";
return;
}
stack[i-1] = pow(stack[i-1], stack[i]);
stack.pop_back();
}
// addToStack() - public function to add a number to the stack
void Stack::addToStack(float num) {
stack.push_back(num);
}
// getAnswer() - public function to return the answer on the stack, and pop the stack down
float Stack::getAnswer() {
int i = stack.size();
if (i != 1) {
cout << "\nstack contains too many values\n\n";
return 0.0;
}
float ans = stack[0];
stack.pop_back();
return ans;
}
