Practice (C++)


// ======================================================================
//
// 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;
}