// Evaluator clas interface: evaluate infix expression
// Type: Must have usual repertoire of arithmetic operators
//
// CONSTRUCTION: with a String
//
// ******************PUBLIC OPERATIONS***********************
// Type getValue( )      --> Return value of infix expression
// ******************ERRORS**********************************
// Some error checking is performed

import DataStructures.*;
import Exceptions.*;
import java.io.*;
import java.util.StringTokenizer;

class Precedence
{
    int inputSymbol;
    int topOfStack;

    Precedence( int inSymbol, int topSymbol )
    {
        inputSymbol = inSymbol;
        topOfStack  = topSymbol;
    }
}

public class Evaluator
{
    static final int EOL     = 0;
    static final int VALUE   = 1;
    static final int OPAREN  = 2;
    static final int CPAREN  = 3;
    static final int EXP     = 4;
    static final int MULT    = 5;
    static final int DIV     = 6;
    static final int PLUS    = 7;
    static final int MINUS   = 8;

        // PrecTable matches order of Token enumeration
    static Precedence [ ] precTable = new Precedence[ 9 ];
    static
    {
        precTable[ 0 ] = new Precedence(   0, -1 );  // EOL
        precTable[ 1 ] = new Precedence(   0,  0 );  // VALUE
        precTable[ 2 ] = new Precedence( 100,  0 );  // OPAREN
        precTable[ 3 ] = new Precedence(   0, 99 );  // CPAREN
        precTable[ 4 ] = new Precedence(   6,  5 );  // EXP
        precTable[ 5 ] = new Precedence(   3,  4 );  // MULT
        precTable[ 6 ] = new Precedence(   3,  4 );  // DIV
        precTable[ 7 ] = new Precedence(   1,  2 );  // PLUS
        precTable[ 8 ] = new Precedence(   1,  2 );  // MINUS
    }


    /**
     * Construct an evaluator object.
     * @param s the string containing the expression.
     */
    public Evaluator( String s )
    {
        opStack = new StackAr( );
        postfixStack = new StackAr( );

        str = new StringTokenizer( s, "+*-/^() ", true );

        opStack.push( new Integer( EOL ) );
    }

        // The only publicly visible routine

    /** 
     * Public routine that performs the evaluation.
     * Examine the  postfix machine to see if a single result is
     * left and if so, return it; otherwise print error.
     * @return the result.
     */
    public long getValue( )
    {
        long theResult = 0;

        do
        {
            lastToken = getToken( );
            processToken( );
        } while( lastToken != EOL );

        try
          { theResult = postFixTopAndPop( ); }
        catch( Underflow e )
        {
            System.err.println( "Missing operand!" );
            return 0;
        }

        if( !postfixStack.isEmpty( ) )
            System.err.println( "Warning: missing operators!" );

        return theResult;
    }


    private Stack opStack;      // Operator stack for conversion
    private Stack postfixStack; // Stack for postfix machine

    StringTokenizer str;        // The character stream
    long currentValue;          // Current operand
    int lastToken;              // Last token read
 
    /**
     * Internal method that hides type-casting.
     */
    private long postFixTopAndPop( ) throws Underflow
    {
        return ( (Long) ( postfixStack.topAndPop( ) ) ).longValue( );
    }

    /**
     * Another internal method that hides type-casting.
     */
    private int opStackTop( ) throws Underflow
    {
        return ( (Integer) ( opStack.top( ) ) ).intValue( );
    }

    /**
     * After a token is read, use operator precedence parsing
     * algorithm to process it; missing opening parentheses
     * are detected here.
     */
    private void processToken( )
    {
        int topOp;
      
        try
        {
            switch( lastToken )
            {
              case VALUE:
                postfixStack.push( new Long( currentValue ) );
                return;

              case CPAREN:
                while( ( topOp = opStackTop( ) ) != OPAREN && topOp != EOL )
                    binaryOp( topOp );
                if( topOp == OPAREN )
                    opStack.pop( );  // Get rid of opening parentheseis
                else
                    System.err.println( "Missing open parenthesis" );
                break;

              default:    // General operator case
                while( precTable[ lastToken ].inputSymbol <=
                       precTable[ topOp = opStackTop( ) ].topOfStack )
                    binaryOp( topOp );
                if( lastToken != EOL )
                    opStack.push( new Integer( lastToken ) );
                break;
            }
        }
        catch( Underflow e ) { }  // Cannot happen 
    }

    /*
     * topAndPop the postfix machine stack; return the result.
     * If the stack is empty, print an error message.
     */
    private long getTop( )
    {
        try
          { return postFixTopAndPop( ); }
        catch( Underflow e )
          { System.err.println( "Missing operand" ); }
        return 0;
    }

    /**
     * Internal routine to compute x^n.
     */
    private static long pow( long x, long n )
    {
        if( x == 0 )
        {
            if( n == 0 )
                System.err.println( "0^0 is undefined" );
            return 0;
        }
        if( n < 0 )
        {
            System.err.println( "Negative exponent" );
            return 0;
        }
        if( n == 0 )
            return 1;
        if( n % 2 == 0 )
            return pow( x * x, n / 2  );
        else
            return x * pow( x, n - 1 );
    }

    /**
     * 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.
     */
    private void binaryOp( int topOp )
    {
        if( topOp == OPAREN )
        {
            System.err.println( "Unbalanced parentheses" );
            try
              { opStack.pop( ); }
            catch( Underflow e ) { }  // Cannot happen
            return;
        }
        long rhs = getTop( );
        long lhs = getTop( );

        if( topOp == EXP )
            postfixStack.push( new Long( pow( lhs, rhs ) ) );
        else if( topOp == PLUS )
            postfixStack.push( new Long( lhs + rhs ) );
        else if( topOp == MINUS )
            postfixStack.push( new Long( lhs - rhs ) );
        else if( topOp == MULT )
            postfixStack.push( new Long( lhs * rhs ) );
        else if( topOp == DIV )
            if( rhs != 0 )
                postfixStack.push( new Long( lhs / rhs ) );
            else
            {
                System.err.println( "Division by zero" );
                postfixStack.push( new Long( lhs ) );
            }
        try
          { opStack.pop( ); }
        catch( Underflow e ) { }
    }

    /**
     * Find the next token, skipping blanks, and return it.
     * For VALUE token, place the processed value in currentValue.
     * Print error message if input is unrecognized.
     */
    private int getToken( )
    {
        String s = "";

        try
          { s = str.nextToken( ); }
        catch( java.util.NoSuchElementException e )
          { return EOL; }

        if( s.equals( " " ) ) return getToken( );
        if( s.equals( "^" ) ) return EXP;
        if( s.equals( "/" ) ) return DIV;
        if( s.equals( "*" ) ) return MULT;
        if( s.equals( "(" ) ) return OPAREN;
        if( s.equals( ")" ) ) return CPAREN;
        if( s.equals( "+" ) ) return PLUS;
        if( s.equals( "-" ) ) return MINUS;

        try
          { currentValue = Long.parseLong( s ); }
        catch( NumberFormatException e )
        {
            System.err.println( "Parse error" );
            return EOL;
        }
        return VALUE;
    }

    /**
     * Quick and dirty main
     */
    public static void main( String [ ] args )
    {
        String str;
        BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );

        try
        {
            System.out.println( "Enter expressions, one per line:" );
            while( ( str = in.readLine( ) ) != null )
            {
                System.out.println( "Read: " + str );
                Evaluator ev = new Evaluator( str );
                System.out.println( ev.getValue( ) );
                System.out.println( "Enter next expression:" );
            }
        }
        catch( IOException e ) { }
    }
}