import java.util.Stack;
import java.util.StringTokenizer;

import java.io.IOException;
import java.util.Scanner;
import java.io.InputStreamReader;


// Evaluator class interface: evaluate infix expressions
//
// CONSTRUCTION: with a String
//
// ******************PUBLIC OPERATIONS***********************
// long getValue( )      --> Return value of infix expression
// ******************ERRORS**********************************
// Some error checking is performed


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

    private static class Precedence
    {
        public int inputSymbol;
        public int topOfStack;

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

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

    private static class Token
    {
        public Token( )
        {
            this( EOL );
        }
        
        public Token( int t )
        {
            this( t, 0 );
        }
        
        public Token( int t, long v )
        {
            type = t;
            value = v;
        }
        
        public int getType( )
        {
            return type;
        }
        
        public long getValue( )
        {
            return value;
        }
        
        private int type = EOL;
        private long value = 0;
    }    

    private static class EvalTokenizer
    {
        public EvalTokenizer( StringTokenizer is )
        {
            str = is;
        }
        
        /**
         * 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.
         */
        public Token getToken( )
        {
            long theValue;           

            if( !str.hasMoreTokens( ) )
                return new Token( );

            String s = str.nextToken( );
            if( s.equals( " " ) ) return getToken( );
            if( s.equals( "^" ) ) return new Token( EXP );
            if( s.equals( "/" ) ) return new Token( DIV );
            if( s.equals( "*" ) ) return new Token( MULT );
            if( s.equals( "(" ) ) return new Token( OPAREN );
            if( s.equals( ")" ) ) return new Token( CPAREN );
            if( s.equals( "+" ) ) return new Token( PLUS );
            if( s.equals( "-" ) ) return new Token( MINUS );

            try
              { theValue = Long.parseLong( s ); }
            catch( NumberFormatException e )
            {
                System.err.println( "Parse error" );
                return new Token( );
            }
            
            return new Token( VALUE, theValue );
        }
        
        private StringTokenizer str;
        
    }
    
    /**
     * Construct an evaluator object.
     * @param s the string containing the expression.
     */
    public Evaluator( String s )
    {
        opStack = new Stack<Integer>( );
        postfixStack = new Stack<Long>( );

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

        opStack.push( 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( )
    {
        EvalTokenizer tok = new EvalTokenizer( str );
        Token lastToken;
        
        do
        {
            lastToken = tok.getToken( );
            processToken( lastToken );
        } while( lastToken.getType( ) != EOL );

        if( postfixStack.isEmpty( ) )
        {
            System.err.println( "Missing operand!" );
            return 0;
        }

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

        return theResult;
    }


    private Stack<Integer> opStack;       // Operator stack for conversion
    private Stack<Long>    postfixStack;  // Stack for postfix machine
    private StringTokenizer str; // StringTokenizer stream


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

          case CPAREN:
            while( ( topOp = opStack.peek( ) ) != 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[ lastType ].inputSymbol <=
                   precTable[ topOp = opStack.peek( ) ].topOfStack )
                binaryOp( topOp );
            if( lastType != EOL )
                opStack.push( lastType );
            break;
        }
    }

    /*
     * topAndPop the postfix machine stack; return the result.
     * If the stack is empty, print an error message.
     */
    private long postfixPop( )
    {
        if ( postfixStack.isEmpty( ) )
        {
            System.err.println( "Missing operand" );
            return 0;
        }
        return postfixStack.pop( );
    }

    /**
     * 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" );
            opStack.pop( );
            return;
        }
        long rhs = postfixPop( );
        long lhs = postfixPop( );

        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
            {
                System.err.println( "Division by zero" );
                postfixStack.push( lhs );
            }
        opStack.pop( );
    }

    /**
     * Simple main to exercise Evaluator class.
     */
    public static void main( String [ ] args )
    {
        String str;
        Scanner in = new Scanner( System.in );

        System.out.println( "Enter expressions, one per line:" );
        while( in.hasNextLine( ) )
        {
            str = in.nextLine( );
            System.out.println( "Read: " + str );
            Evaluator ev = new Evaluator( str );
            System.out.println( ev.getValue( ) );
            System.out.println( "Enter next expression:" );
        }
    }
}