// Purpose.  Interpreter aside.  "The pattern doesn't address parsing."  "When
// the grammer is very complex, other techniques (such as a parser) are more
// appropriate." [GOF, p247]

public class InterpreterDemo {
   public static boolean precedence( char a, char b ) {
      String high = "*/", low = "+-";
      if (a == '(') return false;     // if (a == '(' && b == ')') return false;
      if (a == ')'  &&  b == '(') { System.out.println( ")-(" ); return false; }
      if (b == '(') return false;
      if (b == ')') return true;
      if (high.indexOf( a ) > -1  &&  low.indexOf( b )  > -1) return true;
      if (high.indexOf( a ) > -1  &&  high.indexOf( b ) > -1) return true;
      if (low.indexOf( a ) > -1   &&  low.indexOf( b )  > -1) return true;
      return false;
   }
   public static String convertToPostfix( String in ) {
      StkChar      opstk  = new StkChar();
      StringBuffer out    = new StringBuffer();
      String       opers  = "+-*/()";
      char         topsym = '+';
      boolean      empty;

      for (int i = 0; i < in.length(); i++)
         if (opers.indexOf( in.charAt(i) ) == -1)
            out.append( in.charAt(i) );
         else {
            while ( ! (empty = opstk.isEmpty())
                    &&  precedence( topsym = opstk.pop(), in.charAt(i) ))
               out.append( topsym );
            if ( ! empty)                     opstk.push( topsym );
            if (empty || in.charAt(i) != ')') opstk.push( in.charAt(i) );
            else                              topsym = opstk.pop();
         }
      while ( ! opstk.isEmpty()) out.append( opstk.pop() );
      return out.toString();
   }
   public static int evaluate( String in ) {
      StkInt stack = new StkInt();
      String opers = "+-*/";
      for (int a, b, i=0; i < in.length(); i++)
         if (opers.indexOf( in.charAt(i) ) == -1)
            stack.push( in.charAt(i)-48 );
         else {
            b = stack.pop();  a = stack.pop();
            if      (in.charAt(i) == '+') a = a + b;
            else if (in.charAt(i) == '-') a = a - b;
            else if (in.charAt(i) == '*') a = a * b;
            else if (in.charAt(i) == '/') a = a / b;
            stack.push( a );
         }
      return stack.pop();
   }
   public static void main( String[] args ) {
      System.out.print( args[0] );
      String postfix = convertToPostfix( args[0] );
      System.out.print( " -- " + postfix );
      System.out.println( " -- " + evaluate( postfix ) );
}  }

// 2+3*4-5+6 -- 234*+5-6+ -- 15
// (2+3)*4-5+6 -- 23+4*5-6+ -- 21
// 2+3*(4-5)+6 -- 2345-*+6+ -- 5
// 2+3*((4-5)+6) -- 2345-6+*+ -- 17
// (3-(4*(5+6))/(7-8))*9/4 -- 3456+*78-/-9*4/ -- 105

class StkChar {
   private char[] arr = new char[9];
   private int    sp  = -1;
   void    push( char ch ) { if ( ! isFull()) arr[++sp] = ch; }
   char    pop()           { if (isEmpty()) return '\0';  return arr[sp--]; }
   boolean isFull()        { return sp == arr.length-1; }
   boolean isEmpty()       { return sp == -1; }
}

class StkInt {
   private int[] arr = new int[9];
   private int   sp  = -1;
   void    push( int ch ) { if ( ! isFull()) arr[++sp] = ch; }
   int     pop()          { if (isEmpty()) return 0;  return arr[sp--]; }
   boolean isFull()       { return sp == arr.length-1; }
   boolean isEmpty()      { return sp == -1; }
}