import java.util.*;

/** Class that can evaluate a postfix expression.
 *  @author Koffman and Wolfgang
 * */

public class PostfixEvaluator {

  // Nested Class
  /** Class to report a syntax error. */
  public static class SyntaxErrorException
      extends Exception {
    /** Construct a SyntaxErrorException with the specified message.
        @param message The message
     */
    SyntaxErrorException(String message) {
      super(message);
    }
  }


  /** A list of operators. */
  private static final String OPERATORS = "+-*/";

  // Data Field
  /** The operand stack. */
  private ArrayStack operandStack;

  // Methods
  /** Evaluates the current operation.
      This function pops the two operands off the operand
      stack and applies the operator.
      @param op A character representing the operator
      @return The result of applying the operator
      @throws EmptyStackException if pop is attempted on
              an empty stack.
   */
  private int evalOp(char op) {
    // Pop the two operands off the stack.
    Integer rhs = (Integer) operandStack.pop();
    Integer lhs = (Integer) operandStack.pop();
    int result = 0;
    // Evaluate the operator.
    switch (op) {
      case '+':  result = lhs.intValue() + rhs.intValue();  break;
      case '-':  result = lhs.intValue() - rhs.intValue();   break;
      case '/':  result = lhs.intValue() / rhs.intValue();   break;
      case '*':  result = lhs.intValue() * rhs.intValue();   break;
    }
    return result;
  }

  /** Determines whether a character is an operator.
      @param op The character to be tested
      @return true if the character is an operator
   */
  private boolean isOperator(char ch) {
    return OPERATORS.indexOf(ch) != -1;
  }

  /** Evaluates a postfix expression.
      @param expression The expression to be evaluated
      @return The value of the expression
      @throws SyntaxErrorException if a syntax error is detected
   */
  public int eval(String expression) throws SyntaxErrorException {
 
    operandStack = new ArrayStack();   // Create an empty stack.

    StringTokenizer tokens = new StringTokenizer(expression);
    try {
      while (tokens.hasMoreTokens()) {
        String nextToken = tokens.nextToken();
        if (Character.isDigit(nextToken.charAt(0))) {
              int value = Integer.parseInt(nextToken);
              operandStack.push(new Integer(value));
        } // Is it an operator?
        else if (isOperator(nextToken.charAt(0))) {
            int result = evalOp(nextToken.charAt(0));
            operandStack.push(new Integer(result));
        }
        else {  throw new SyntaxErrorException(  "Invalid character encountered");   }
      } // End while.

      Integer answer = (Integer) operandStack.pop();
      
      if (operandStack.empty()) {   return answer.intValue();      }
      
      else {   throw new SyntaxErrorException(  "Syntax Error: Stack should be empty");      }
    }
    catch (EmptyStackException ex) {  throw new SyntaxErrorException(  "Syntax Error: The stack is empty");
    }
  }
}