package expr;

import ccj.*;

public class Expression
{  public Expression(String expr)
   {  parser = new Parser(expr);
      opstack = new java.util.Stack();
      numstack = new java.util.Stack();
   }

   public double eval()
   {    while (true)
      {  int type = parser.nextTokenType();
         String s = parser.nextToken();
         if (type == Parser.OPERATOR)
         {  if (opstack.empty())
               opstack.push(s);
            else
            {  String old = (String)opstack.pop();
               if (Parser.precedence(s) > Parser.precedence(old))
                  opstack.push(old);
               else
                  evalOperator(old);
               opstack.push(s);
            }
         }
         else if (type == Parser.LEFT_PAREN)
            opstack.push(s);
         else if (type == Parser.RIGHT_PAREN)
         {  boolean more = true;
            while (more)
            {  if (opstack.empty())
                  throw new IllegalArgumentException("Too many )");
               String old = (String)opstack.pop();
               if (old.equals("(")) more = false;
               else evalOperator(old);
            }
         }
         else if (type == Parser.END_OF_STRING)
         {  while (!opstack.empty())
            {  String old = (String)opstack.pop();
               if (old.equals("("))
                  throw new IllegalArgumentException("Too many (");
               else evalOperator(old);
            }
            if (numstack.empty())
               throw new IllegalArgumentException("Syntax error");
            double x = Numeric.parseDouble((String)numstack.pop());
         
            if (!numstack.empty())
               throw new IllegalArgumentException("Syntax error");
            return x;
         }
         else if (type == Parser.NUMBER)
            numstack.push(s);
         else
            throw new IllegalArgumentException("Bad token");
      }
   }

   private void evalOperator(String op)
   {  if (numstack.empty())
         throw new IllegalArgumentException("Syntax error");
      double y = Numeric.parseDouble((String)numstack.pop());
      if (numstack.empty())
         throw new IllegalArgumentException("Syntax error");
      double x = Numeric.parseDouble((String)numstack.pop());

      double z;
      if (op.equals("^")) z = Math.pow(x, y);
      else if (op.equals("*")) z = x * y;
      else if (op.equals("/"))
      {  if (y == 0)
            throw new IllegalArgumentException("Divide by 0");
         else z = x / y;
      }
      else if (op.equals("+")) z = x + y;
      else if (op.equals("-")) z = x - y;
      else
         throw new IllegalArgumentException("Bad token");
      numstack.push("" + z);
   }

   private java.util.Stack opstack;
   private java.util.Stack numstack;
   private Parser parser;
}

class Parser
{  Parser(String toParse)
   {  input = toParse;
      pos = 0;
   }

   public int nextTokenType()
   {  skipWhiteSpace();
      if (pos >= input.length()) return END_OF_STRING;
      String ch = input.substring(pos, pos + 1);
      if (ch.equals("(")) return LEFT_PAREN;
      if (ch.equals(")")) return RIGHT_PAREN;
      if ("+-*/^".indexOf(ch) != -1) return OPERATOR;
      if ("1234567890".indexOf(ch) != -1) return NUMBER;
      return BAD_TOKEN;
   }

   public String nextToken()
   {  int i = nextTokenType();
      if (i == END_OF_STRING || i == BAD_TOKEN) return "";
      if (i == NUMBER)
      {  int end = pos + 1;
         boolean more = true;
         while (more && end < input.length())
         {  String ch = input.substring(end, end + 1);
            if (ch.equals(".") || "1234567890".indexOf(ch) != -1)
               end++;
            else
               more = false;
         }
         String r = input.substring(pos, end);
         pos = end;
         return r;
      }
      else
      {  String r = input.substring(pos, pos + 1);
         pos++;
         return r;
      }
   }
   
   public static int precedence(String operator)
   {  if (operator.equals("+") || operator.equals("-")) return 1;
      if (operator.equals("*") || operator.equals("/")) return 2;
      if (operator.equals("^")) return 3;
      return 0; 
   }

   public static final int OPERATOR = 1;
   public static final int NUMBER = 2;
   public static final int LEFT_PAREN = 3;
   public static final int RIGHT_PAREN = 4;
   public static final int END_OF_STRING = 5;
   public static final int BAD_TOKEN = 6;

   private void skipWhiteSpace()
   {  while (pos < input.length() && input.substring(pos, pos + 1).equals(" "))
         pos++;
   }

   private String input;
   private int pos;
}