Code:
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<fstream>
// #include"Stack.cpp"
using namespace std;
class Underflow { };
class Overflow { };
class OutOfMemory { };
class BadIterator { };
// Stack class -- linked list implementation
// CONSTRUCTION: with no parameters
// ******************PUBLIC OPERATIONS*********************
// void push( x ) --> Insert x
// void pop( ) --> Remove most recently inserted item
// Object top( ) --> Return most recently inserted item
// Object topAndPop( ) --> Return and remove most recently inserted item
// bool isEmpty( ) --> Return true if empty; else false
// bool isFull( ) --> Return true if full; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Overflow and Underflow thrown as needed
template <class Object>
class Stack
{
public:
Stack( );
Stack( const Stack & rhs );
~Stack( );
bool isEmpty( ) const;
bool isFull( ) const;
const Object & top( ) const;
void pop( );
void makeEmpty( );
void push( const Object & x );
Object topAndPop( );
}
const Stack & operator=( const Stack & rhs );
private:
struct ListNode
{
Object element;
ListNode *next;
ListNode( const Object & theElement, ListNode * n = NULL )
: element( theElement ), next( n ) { }
};
ListNode *topOfStack;
};
// /////////////////////////////////////////////////////////////////
template <class Object>
Stack<Object>::Stack( )
{
topOfStack = NULL;
} // Copy constructor.
template <class Object>
Stack<Object>::Stack( const Stack<Object> & rhs )
{
topOfStack = NULL;
*this =rhs;
}
// Destructor
template <class Object>
Stack<Object>::~Stack( )
{
makeEmpty( );
}
/*
Test if the stack is logically full.
Return false always, in this implementation.
*/
template <class Object>
bool Stack<Object>::isFull( ) const
{
return false;
}
// Test if the stack is logically empty.
// Return true if empty, false otherwise.
template <class Object>
bool Stack<Object>::isEmpty( ) const
{
return topOfStack == NULL;
}
// Make the stack logically empty.
template <class Object>
void Stack<Object>::makeEmpty( )
{while( !isEmpty( ) )
pop();
}
/* Get the most recently inserted item in the stack.
Return the most recently inserted item in the stack
or throw an exception if empty.
*/
template <class Object>
const Object & Stack<Object>::top( ) const
{
if( isEmpty( ) )
throw Underflow( );
return topOfStack->element;
}
/* Remove the most recently inserted item from the stack.
Exception Underflow if the stack is empty.
*/
template <class Object>
void Stack<Object>::pop( )
{
ListNode * oldTop;
if( isEmpty( ) ){
oldTop= topOfStack;
}
topOfStack = topOfStack->next; delete oldTop;
}
/* Return and remove the most recently inserted item
from the stack.
*/
template <class Object>
Object Stack<Object>::topAndPop( )
{
Object topItem = top( );
pop( );
return topItem;
}
// Insert x into the stack.
template <class Object>
void Stack<Object>::push( const Object & x )
{
topOfStack = new ListNode( x, topOfStack );
}
// Deep copy.
template <class Object>
const Stack<Object> & Stack<Object>::
operator=( const Stack<Object> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
if( rhs.isEmpty( ) )
return *this;
ListNode *rptr = rhs.topOfStack;
ListNode *ptr = new ListNode( rptr->element );
topOfStack = ptr;
for( rptr = rptr->next; rptr != NULL; rptr = rptr->next )
ptr = ptr->next = new ListNode( rptr->element );
}
return *this;
}
///////////////////////////////////////////////////////////////////////
// operator definition is needed
/ A Pow routine for exponentiation.
template <class NumericType>
NumericType pow( const NumericType & x, const NumericType & n )
{
if( x == 0 )
{
if( n == 0 )
cerr << "0^0 is undefined" << endl;
return 0;
}
if( n < 0 )
{
cerr << "Negative exponent" << endl;
return 0;
}
if( n == 0 )
return 1;
if( n % 2 == 0 )
return pow( x * x, n / 2 );
else
return x * pow( x, n - 1 );
}
///////////////////////////////////////////
enum TokenType { EOL, VALUE, OPAREN, CPAREN, EXP, MULT, DIV, PLUS, MINUS };
template <class NumericType>
class Token
{
public:
Token( TokenType tt = EOL, const NumericType & nt = 0 )
: theType( tt ), theValue( nt ) { }
TokenType getType( ) const
{ return theType; }
const NumericType & getValue( ) const
{ return theValue; }
private:
TokenType theType;
NumericType theValue;
};
/////////////////////////////////////////////////////
template <class NumericType>
class Tokenizer
{
public:
Tokenizer( istream & is ) : in( is ) { }
Token<NumericType> getToken( );
private:
istream & in;
};
/////////////////////////////////////////////////////
template <class NumericType>
class Evaluator
{
public:
Evaluator( const string & s ) : str( s )
{ opStack.push( EOL ); }
// The only publicly visible routine
NumericType getValue( ); // Do the evaluation
private:
// vector<TokenType> opStack; // Operator stack for conversion
// vector<NumericType> postFixStack; // Stack for postfix machine
Stack opStack; // Operator stack for conversion
Stack postFixStack; // Stack for postfix machine
istringstream str; // String stream
// Internal routines
NumericType getTop( ); // Get top of postfix stack
void binaryOp( TokenType topOp ); // Process an operator
void processToken( const Token<NumericType> & lastToken ); // Handle LastToken
};
// PREC_TABLE matches order of Token enumeration
struct Precedence
{
int inputSymbol;
int topOfStack;
} PREC_TABLE [ ] =
{
{ 0, -1 }, { 0, 0 }, // EOL, VALUE
{ 100, 0 }, { 0, 99 }, // OPAREN, CPAREN
{ 6, 5 }, // EXP
{ 3, 4 }, { 3, 4 }, // MULT, DIV
{ 1, 2 }, { 1, 2 } // PLUS, MINUS
};
// Public routine that performs the evaluation.
// Examines the postfix machine to see if a single result
// is left and if so, returns it; otherwise prints error.
template <class NumericType>
NumericType Evaluator<NumericType>::getValue( )
{
Tokenizer<NumericType> tok( str );
Token<NumericType> lastToken;
do
{
lastToken = tok.getToken( );
processToken( lastToken );
} while( lastToken.getType( ) != EOL );
if( postFixStack.isEmpty( ) )
{
cerr << "Missing operand!" << endl;
return 0;
}
NumericType theResult = postFixStack.top();
postFixStack.pop( );
if( !postFixStack.isEmpty( ) )
cerr << "Warning: missing operators!" << endl;
return theResult;
}
// After token is read, use operator precedence parsing
// algorithm to process it; missing opening parentheses
// are detected here.
template <class NumericType>
void Evaluator<NumericType>::processToken( const Token<NumericType> & lastToken )
{
TokenType topOp;
TokenType lastType = lastToken.getType( );
switch( lastType )
{
case VALUE:
postFixStack.push( lastToken.getValue( ) );
return;
case CPAREN:
while( ( topOp = opStack.top( ) ) != OPAREN && topOp != EOL )
binaryOp( topOp );
if( topOp == OPAREN )
opStack.pop( ); // Get rid of opening parentheseis
else
cerr << "Missing open parenthesis" << endl;
break;
default: // General operator case
while( PREC_TABLE[ lastType ].inputSymbol <=
PREC_TABLE[ topOp = opStack.top( ) ].topOfStack )
binaryOp( topOp );
if( lastType != EOL )
opStack.push( lastType );
break;
}
}
// top and pop the postfix machine stack; return the result.
// If the stack is empty, print an error message.
template <class NumericType>
NumericType Evaluator<NumericType>::getTop( )
{
if( postFixStack.isEmpty( ) )
{
cerr << "Missing operand" << endl;
return 0;
}
NumericType tmp = postFixStack.top( );
postFixStack.pop( );
return tmp;
}
// Process an operator by taking two items off the postfix
// stack, applying the operator, and pushing the result.
// Print error if missing closing parenthesis or division by 0.
template <class NumericType>
void Evaluator<NumericType>::binaryOp( TokenType topOp )
{
if( topOp == OPAREN )
{
cerr << "Unbalanced parentheses" << endl;
opStack.pop( );
return;
}
NumericType rhs = getTop( );
NumericType lhs = getTop( );
if( topOp == EXP )
postFixStack.push( pow( lhs, rhs ) );
else if( topOp == PLUS )
postFixStack.push( lhs + rhs );
else if( topOp == MINUS )
postFixStack.push( lhs - rhs );
else if( topOp == MULT )
postFixStack.push( lhs * rhs );
else if( topOp == DIV )
if( rhs != 0 )
postFixStack.push( lhs / rhs );
else
{
cerr << "Division by zero" << endl;
postFixStack.push( lhs );
}
opStack.pop( );
}
// Find the next token, skipping blanks, and return it.
// Print error message if input is unrecognized.
template <class NumericType>
Token<NumericType> Tokenizer<NumericType>::getToken( )
{
char ch;
NumericType theValue;
// Skip blanks
while( in.get( ch ) && ch == ' ' )
;
if( in.good( ) && ch != '\n' && ch != '\0' )
{
switch( ch )
{
case '^': return EXP;
case '/': return DIV;
case '*': return MULT;
case '(': return OPAREN;
case ')': return CPAREN;
case '+': return PLUS;
case '-': return MINUS;
default:
in.putback( ch );
if( !( in >> theValue ) )
{
cerr << "Parse error" << endl;
return EOL;
}
return Token<NumericType>( VALUE, theValue );
}
}
return EOL;
}
// A simple main to exercise Evaluator class.
int main( )
{
string str;
while( getline( cin, str ) )
{
Evaluator<int> e( str );
cout << e.getValue( ) << endl;
}
return 0;
}