import java.io.*;
import java.util.*;

public class Evaluator {
    Stack stack;
    StringTokenizer st;
    
    public Evaluator (String line) {
	st = new StringTokenizer (line, "+-*/ ", true);
	stack = new Stack ();
    }

    // evaluate: evaluate the expression and return an integer
    // might print a warning message and return or print an
    // error message and quit.
    public Tree evaluate () {	
	while (st.hasMoreTokens ()) {
	    String s = st.nextToken ();
	    
	    if (isOperand (s)) {
		stack.push (new Tree (new Token(s), null, null));
	    } else if (isOperator (s)) {
		Tree op2 = popTree ();
		Tree op1 = popTree ();
		stack.push (new Tree (new Token (s), op1, op2));
	    } else if (isWhitespace (s)) {
		// do nothing
	    } else {
		error ("unrecognized token " + s);
	    }
	}
	
	// get the result
	if (stack.empty ()) error ("no result left on stack.");	
	Tree result = popTree ();
	
	// if there are extra items on the stack, warn the user and
	// pop the excess
	while (!stack.empty ()) {
	    System.out.print ("Warning: item left on the stack: ");
	    System.out.println (popTree ());
	}  
	return result;
    }

    // isOperator: check if the token contains a single character that
    // is an operator
    private boolean isOperator (String s) {
	if (s.length() != 1) return false;
	switch (s.charAt(0)) {
	case '+': case '-': case '*': case '/':
	    return true;
	default:
	    return false;
	}
    }

    // isOperand: check if all the characters in the token are digits
    private boolean isOperand (String s) {
	for (int i=0; i<s.length(); i++) {
	    if (!Character.isDigit (s.charAt (i))) {
		return false;
	    }
	}
	return true;
    }
  
    // isWhitespace: check if all the characters in the token are
    // whitespace (spaces, tabs or newlines)
    private boolean isWhitespace (String s) {
	for (int i=0; i<s.length(); i++) {
	    if (!Character.isWhitespace (s.charAt (i))) {
		return false;
	    }
	}
	return true;
    }

    // popTree: pop a Tree off the stack or report an error
    private Tree popTree () {
	if (stack.empty ()) error ("not enough operands on the stack.");
	return ((Tree) stack.pop());
    }

    // error: print an error message and quit
    private void error (String s) {
	System.out.println ("Error: " + s);
	System.exit(1);
    }	
}