infix evaluation using stack

hi to all,
i need to write a code in C++ which takes infix expressions and after converting to postfix equivalent it will evaluate the expression by using a stack implemented with linked list. can you help me?
>the inputs which includes definitions and expressions are given in a file let say input.txt
>the input is like this:

> defineop $ ; a $ b = ( a + b ) * a ^ b ; 0 $ a = a + 1 ; a $ 0 = 0 ; prec = 7 ; assoc = left ; end
> defineop ^ ; a ^ b = a ^ ( b - 1 ) * a ; 0 ^ a = 0 ; a ^ 0 = 1 ; prec = 32 ; assoc = right ;
end
> defineop ~ ; ~ a = 0 - a ; ~ 0 = 0 ; prec = 45 ; end
> evaluate ; 3 * ( 2 + 2 ^ 3 ) ; end
> evaluate ; ~ 2 + 3 $ 2 ; end

For 0 op 0, 0 op p1 is used.


there is 1 blank between each token. an operator can be unary or binary.prec is precedence and assoc is associativity.input is error free.for example there is no 1/0 case.

i will just deal with integers.so divisions are integer division.operators are {~,!,@,#,$,%,^,&,_}

in an input file there can be some of these operators or all of these operators.

>the output will be printed on the screen each separated with new line.



best regards


p.s.
the following is the code that i wrote.it has errors and not complete.the code must compile in g++

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

---