// ---------------------------------------------------------------
// Node - Base class of our expression evaluator, subclasses
//        must provide: 'evaluate' and 'toString'
// ---------------------------------------------------------------

import java.util.ArrayList;
import java.util.HashMap;

public abstract class Node
{
   public Token getToken() { return(null); }

   public abstract double evaluate(HashMap<String, Double> env) throws Exception;

   public abstract String toString();

   public static void dump(ArrayList<Node> items)
   {
      System.out.println();
      System.out.println("items");
      System.out.println("=====");

      for(Node n : items)
         System.out.println("item: " + n);
   }

   // ----------------------------------------------------
   // getNode - Try to convert the input string into a
   //           a root Node object
   // ----------------------------------------------------

   public static Node getNode(String theString) throws Exception
   {
      return(getNode(Token.getTokens(theString)));
   }

   // ----------------------------------------------------
   // getNode - Try to convert the supplied array of tokens
   //           into a root Node object
   // ----------------------------------------------------

   public static Node getNode(Token[] theTokens) throws Exception
   {
      if(theTokens == null || theTokens.length == 0)
         throw new Exception("No tokens supplied");

      ArrayList<Node> items = new ArrayList<Node>();

      for(int i = 0; i < theTokens.length; i ++)
      {
         Node theNode = null;

         Token.Type type = theTokens[i].getType();
         String text     = theTokens[i].getText();

         if(type == Token.Type.NUMBER)
         {
            theNode = new NumberNode(text);
         }
         else if(type == Token.Type.IDENTIFIER)
         {
            // If we're not followed by a '(', this
            // is a variable (not a function call)

            if(i + 1 == theTokens.length ||
               theTokens[i + 1].getType() != Token.Type.LEFT_PARENTHESIS)
            {
               theNode = new VariableNode(text);
            }
         }

         if(theNode == null)
            theNode = new TokenNode(theTokens[i]);

         items.add(theNode);
      }

      if(false)
      {
         dump(items);
      }

      return(process(items));
   }

   // Given: 'items' (a list of Tokens and Node objects), we return
   // a single, root Node object

   public static Node process(ArrayList<Node> items) throws Exception
   {
      // First, we need to deal with parenthesis so that we can
      // evaluate: (1+2)*3 correctly (should be 9, not 7)

      while(true)
      {
         // Find the index of the first '('

         int nItems    = items.size();
         int leftIndex = -1;

         for(int i = 0; leftIndex == -1 && i < nItems; i ++)
         {
            Token t = items.get(i).getToken();

            if(t != null && t.getType() == Token.Type.LEFT_PARENTHESIS)
               leftIndex = i;
         }

         // We didn't find one

         if(leftIndex == -1)
            break;

         // Find the matching ')' if there is one

         int rightIndex = -1;
         int nLeft      = 1;
         int nRight     = 0;

         for(int i = leftIndex + 1; rightIndex == -1 && i < nItems; i ++)
         {
            Token t = items.get(i).getToken();

            if(t != null)
            {
               Token.Type type = t.getType();

               if(type == Token.Type.LEFT_PARENTHESIS)
               {
                  nLeft++;
               }
               else if(type == Token.Type.RIGHT_PARENTHESIS)
               {
                  nRight++;

                  if(nLeft == nRight)
                     rightIndex = i;
               }
            }
         }

         if(rightIndex == -1)
            throw new Exception("No matching ')' found");

         // Ok, everything between leftIndex and rightIndex will
         // be replaced by the corresponding Node

         ArrayList<Node> list = new ArrayList<Node>();

         for(int i = leftIndex + 1; i < rightIndex; i ++)
            list.add(items.get(i));

         if(list.size() == 0)
            throw new Exception("Empty '(' ')' encountered");

         // Replace the '(' Token with the Node and then
         // remove all elements up to and including ')'

         Node theNode = process(list);
         int start    = leftIndex;

         if(leftIndex > 0)
         {
            // See if this is a function call

            Token t = items.get(leftIndex - 1).getToken();

            if(t != null && t.getType() == Token.Type.IDENTIFIER)
            {
               theNode = new MethodNode(t.getText(), theNode);
               start--;
            }
         }

         items.set(start, theNode);

         for(int i = start + 1, j = i; i <= rightIndex; i ++)
            items.remove(j);
      }

      if(false)
      {
         dump(items);
      }

      // Now, exponentiation - note that this operator is
      // right associative (all others are left-associative)

      while(true)
      {
         // Find the index of the first '^'

         int index = -1;

         for(int i = items.size() - 1; index == -1 && i >= 0; i --)
         {
            Token t = items.get(i).getToken();

            if(t != null && t.getType() == Token.Type.POWER)
               index = i;
         }

         // We didn't find one

         if(index == -1)
            break;

         // There must be a Node before and after our '^'

         if(index == 0 || index + 1 == items.size())
            throw new Exception("Two operands required for '^'");

         Node before = items.get(index - 1);
         Node after  = items.get(index + 1);

         if(before.getToken() != null || after.getToken() != null)
            throw new Exception("Invalid operand for '^'");

         Node powerNode = new PowerNode(before, after);

         items.set(index - 1, powerNode);
         items.remove(index);
         items.remove(index); 
      }

      if(false)
      {
         dump(items);
      }

      // Now, unary minus

      while(true)
      {
         boolean found = false;

         for(int i = 0; !found && i < items.size(); i ++)
         {
            Token t = items.get(i).getToken();

            if(t != null && t.getType() == Token.Type.MINUS)
            {
               if(i + 1 == items.size())
                  throw new Exception("Missing operand after '-'");

               // The '-' must be followed by a Node object, not a Token

               if(items.get(i + 1).getToken() == null)
               {
                  // If this is the first item it's a unary minus, it's also
                  // a unary minus if the thing before it is an operator

                  boolean isUnary = false;

                  if(i == 0)
                  {
                     isUnary = true;
                  }
                  else
                  {
                     Token previous = items.get(i - 1).getToken();

                     if(previous != null)
                     {
                        Token.Type theType = previous.getType();

                        if(theType == Token.Type.MINUS ||
                           theType == Token.Type.PLUS  ||
                           theType == Token.Type.TIMES ||
                           theType == Token.Type.DIVIDE)
                        {
                           isUnary = true;
                        }
                     }
                  }

                  if(isUnary)
                  {
                     items.set(i, new UnaryMinusNode(items.get(i + 1)));
                     items.remove(i + 1);
                     found = true;
                  }
               }
            }
         }

         if(!found)
            break;
      }

      if(false)
      {
         dump(items);
      }
      
      // Now, our binary operators: +, -, * and /, we need to handle
      // * and / first as they have precedence

      boolean doTimesAndDivide = true;

      while(true)
      {
         int nItems  = items.size();
         String text = null;
         int index   = -1;

         for(int i = 0; index == -1 && i < nItems; i ++)
         {
            Token t = items.get(i).getToken();

            if(t != null)
            {
               if(doTimesAndDivide)
               {
                  if(t.getType() == Token.Type.TIMES ||
                     t.getType() == Token.Type.DIVIDE)
                  {
                     index = i;
                  }
               }
               else
               {
                  if(t.getType() == Token.Type.PLUS ||
                     t.getType() == Token.Type.MINUS)
                  {
                     index = i;
                  }
               }

               if(index != -1)
                  text  = t.getText();
            }
         }

         if(index == -1)
         {
            // We didn't find what we were looking for

            if(doTimesAndDivide)
            {
               doTimesAndDivide = false;
            }
            else
               break;
         }
         else
         {
            // The items before and after items[index] should
            // be subclasses of Node

            if(index == 0)
            {
               throw new Exception(
                  "No left hand side found for: " + text
               );
            }

            if(index + 1 == nItems)
            {
               throw new Exception(
                  "No right hand side found for: " + text
               );
            }

            Token left  = items.get(index - 1).getToken();
            Token right = items.get(index + 1).getToken();

            if(left != null)
            {
               throw new Exception(
                  String.format(
                     "Invalid left hand side: '%s' found for: '%s'",
                     left.getText(), text
                  )
               );
            }

            if(right != null)
            {
               throw new Exception(
                  String.format(
                     "Invalid right hand side: '%s' found for: '%s'",
                     right.getText(), text
                  )
               );
            }

            Node n1 = items.get(index - 1);
            Node n2 = items.get(index + 1);

            Node theNode = null;

            if(doTimesAndDivide)
            {
               if(text.equals("*"))
                  theNode = new TimesNode(n1, n2);
               else
                  theNode = new DivideNode(n1, n2);
            }
            else
            {
               if(text.equals("+"))
                  theNode = new PlusNode(n1, n2);
               else
                  theNode = new MinusNode(n1, n2);
            }

            // Replace the left hand side with the Node and
            // then remove the next two items

            items.set(index - 1, theNode);

            items.remove(index);
            items.remove(index);

            if(false)
            {
               dump(items);
            }
         }
      }

      // At this point, we should be down to a single Node

      if(items.size() != 1)
         throw new Exception("Missing operator");

      return(items.get(0));
   }

   public static void main(String[] args)
   {
      String s = "";

      for(String arg : args)
         s += (s.equals("") ? "" : " ") + arg;

      Token[] list = null;

      try
      {
         list = Token.getTokens(s);
      }
      catch(Exception e)
      {
         System.out.println(e);
         return;
      }

      System.out.println("Tokens");
      System.out.println("------");
      System.out.println();

      for(Token t : list)
         System.out.println("   " + t);

      System.out.println();

      Node theNode = null;
      
      try
      {
         theNode = Node.getNode(list);
      }
      catch(Exception e)
      {
         System.out.println(String.format("'%s': %s", s, e.getMessage()));
         return;
      }

      System.out.println("Node");
      System.out.println("----");
      System.out.println();

      System.out.println("   " + theNode + "\n");

      HashMap<String, Double> env = new HashMap<>();

      try
      {
         System.out.println("Result: " + theNode.evaluate(env));
      }
      catch(Exception e)
      {
         System.out.println(e.getMessage());
      }
   }
}