/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ *
 * Andrew Hays                                                                *
 * T00405507                                                                  *
 * CPSC 3371-11                                                               *
 * Fall 2009                                                                  *
 * Net-centric Computing: Language Concepts                                   *
 * Project 1: Interpreter / Command Driven Calculator                         *
 * Written: August 25, 2009                                                   *
 * Revised:                                                                   *
 *  - August 27, 2009                                                         *
 *  - August 29, 2009                                                         *
 *  - September 1, 2009                                                       *
 *  - September 11, 2009
 * Description:                                                               *
 *  This is a command driven calculator.  You can type in mathematical        *
 *  commands and then it will evaluate and give the answer.  It's made to be  *
 *  an interpreter, so the response is immediate after you key it in.  The    *
 *  calculator current supports addition, subtraction, multiplication,        *
 *  division, exponentiation, parentheses, and modulus.  You can also         *
 *  currently edit variables X, Y, and Z.  Any further improvements will be   *
 *  added and then updated on as needed.                                      *
 *                                                                            *
 * Licensing:                                                                 *                                                                           
 *  This code is licensed under a WTFPL and is completely open-source.        *
 *  Do with it whatever you want.  For more information about the WTFPL,      *
 *  please visit  http://sam.zoy.org/wtfpl/ (bear in mind, there's a          *
 *  lot of language, given the name of the license).  The full text of the    *
 *  license reads:                                                            *
 *                                                                            *
 *  DO WHAT THE (FRIG) YOU WANT TO PUBLIC LICENSE                             *
 *  Version 2, December 2004                                                  *
 *                                                                            *
 *  Copyright (C) 2004 Sam Hocevar                                            *
 *   14 rue de Plaisance, 75014 Paris, France                                 *
 *  Everyone is permitted to copy and distribute verbatim or modified         *
 *  copies of this license document, and changing it is allowed as long as    *
 *  the name is changed.                                                      *
 *                                                                            *
 *  DO WHAT THE (FRIG) YOU WANT TO PUBLIC LICENSE TERMS AND CONDITIONS FOR    *
 *  COPYING, DISTRIBUTION AND MODIFICATION                                    *
 *                                                                            *
 *  0. You just DO WHAT THE (FRIG) YOU WANT TO.                               *
 *                                                                            *
 *  This program is free software. It comes without any warranty, to          *
 *  the extent permitted by applicable law. You can redistribute it           *
 *  and/or modify it under the terms of the Do What The (Frig) You Want       *
 *  To Public License, Version 2, as published by Sam Hocevar. See            *
 *  http://sam.zoy.org/wtfpl/COPYING for more details.                        *
 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */

import java.io.*;
import java.util.*;
import java.util.regex.Pattern;

public class CommandDrivenCalculator
{
  public static void main(String [] args) throws IOException
  {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // Read data in from the keyboard. (System.in)
    Map<String, String> variablelist = new HashMap<String,String>();
    variablelist.put("X","0");
    variablelist.put("Y","0");
    variablelist.put("Z","0");
    // All user variables should be initialized to zero. (X, Y, and Z);
    System.out.println("************************************************" +
        "\nAndrew Hays\nT00405507\nCommand-Driven Calculator v3.5.1\n" +
        "The command driven calculator takes in commands for calculation " +
        "\n(such as \"(2*(3*4)-6/2)/21\") and returns the answer to the " +
        " screen. \nWorking variables that can be assigned are X, Y, and Z " +
        "(case insensitive, \nassigned using X=3, etc.) and you can create " +
        "your own variables as long as they start with $.  Allowed keys are " +
        "0-9 A-Z $ * / + - ^ % . ( ).  \nProgram is case insensitive.  " +
        "To quit, just type \"quit\".\n" + 
        "************************************************");
    // The introduction
    System.out.print("\n\n$ ");
    String input = br.readLine().replaceAll(" ","").toUpperCase();
    // Read a line from the buffer, strip all spaces, 
    // and change it to uppercase.
    String answer = "";
    String [] splitAns;
    // get the answer read.
    while (!(input.equals("QUIT") || input.equals("EXIT") || 
          input.equals(":Q") || input.equals(":WQ")))
    // If you don't use QUIT or EXIT as your input...
    {
      input = input.replaceAll("(\\$[A-Z\\_]+)([0-9])","$1*$2");
      input = input.replaceAll("([0-9])(\\$[A-Z\\_])","$1*$2");
      input = input.replaceAll("(\\$[A-Z\\_]+)(\\$[A-Z\\_]+)","$1*$2");
      input = input.replaceAll("([X-Z])([0-9])","$1*$2");
      input = input.replaceAll("([0-9])([X-Z])","$1*$2");
      if (input.indexOf('=') != -1)
      // Using the assignment operator.
      {
        splitAns = input.split("=",2);
        // Split it up into the left side and right sides of the equation.
        if (Pattern.matches("[X-Z]",splitAns[0]) || 
                Pattern.matches("\\$[A-Z\\_]+",splitAns[0]))
        // Is the left side of the equation either X, Y, or Z
        // Is it of the form $new_var_name?
        {
          for (String key : variablelist.keySet())
          {
            // iterate through the set in a foreach loop
            splitAns[1] = splitAns[1].replaceAll(key, variablelist.get(key));
            // replace all instances of each variable with their value.
          }
          try
          {
            answer = eval(rpn(splitAns[1]));
            // evaluate the answer
            if (answer.indexOf("ERROR") == -1)
            // if we didn't get an error
            {
              variablelist.put(splitAns[0],answer);
              // put the answer in the variable list
              System.out.println(splitAns[0] + ": " + answer);
              // print the answer
            }
          }
          catch(NumberFormatException e)
          // Did you come across a number formatting exception? 
          // (I should've caught all this.)
          {
            e.printStackTrace();
          }
        }
        else
          answer = "ERROR-VAR-CHOICE";
      }
      else
      // If we didn't error, and you're not assigning anything...
      {
        for (String key : variablelist.keySet())
        {
          input = input.replaceAll(key, variablelist.get(key));
        }
        answer = eval(rpn(input));
        // evalute the RPN and where all 'X', 'Y', and 'Z' variables 
        // are replaced with their values.
        if (answer.indexOf("ERROR") == -1)
        // No error?  give the answer.
        {
          System.out.println(": " + answer);
        }
      }

      if (answer.indexOf("ERROR") != -1)
      // Did you get an error in the program?
      {
        if (answer.equals("ERROR-ASSIGNMENT"))
        // If there was a problem using the '=' sign.
        {
          System.out.println("There was an error using the assignment "+ 
              "operator.  Are you using it correctly? (ex. \"X=(3+4)*Z-Y\").");
        }
        else if (answer.equals("ERROR-VAR-CHOICE"))
        // If there was a problem in variable choice.
        {
          System.out.println("Variables must either by X, Y, or Z or be " +
              "preceded with a dollar sign and only contain letters and " +
              "underscores. To set them, try \"$var=(3+4)*Z-Y+X\".");
        }
        else if (answer.equals("ERROR-PARENS"))
        // Don't match all your parens?
        {
          System.out.println("Parentheses error.  Make sure that you " +
              "didn't close an extra parenthesis.");
        }
        else if (answer.equals("ERROR-EVAL"))
        // Error in the evaluation, more than likely by typing 
        // something like '2+'
        {
          System.out.println("Error in the evaluation.   Check your binary " +
              "operators and close all parentheses.");
        }
        else if (answer.equals("ERROR-NON-NUMERICAL"))
        // If there was a problem using un-implemented symbols (like '@')
        {
          System.out.println("Error, you have used a symbol or variable " +
              "that does not exist in this program.  Allowed keys are " +
              "( ) X Y Z 0-9 . + - / * ^ % =.");
        }
        else
        // Or if all else fails...
        {
          System.out.println("Unknown error.  Please try again.");
        }
      }

      System.out.print("\n$ ");
      // start over
      input = br.readLine().replaceAll(" ","").toUpperCase();
      // read the next line
    }
  }

  private static String rpn(String input)
  // The function that puts everything in reverse polish notation.
  {
    char [] operationStack = new char[input.length()];
    // This is our stack of operations to push and pop on.
    int stackPtr = -1;
    // Start your stackpointer at negative one (nothing on the stack).
    String output = "";
    // No output yet.
    char next;
    for (int i = 0; i < input.length(); i++)
    // For each character in the input.
    {
      next = input.charAt(i);
      // So that I don't have to keep typing input.charAt(i)...
      if ((next <= '9' && next >= '0') || next == '.' || (next == '-' && 
            ( i == 0 || input.charAt(i-1) == '(')))
      // Dealing with a numeric character?
      {
        if (next == '-')
        // Negative number?
        {
          output += "0 ";
          // 0 - n == -n (read the comment at the end of this if statement 
          // section.
          if ( stackPtr != -1 && 
              opPrecedence('+', operationStack[stackPtr]) <= 0)
          // Does another operation take precedence?
          {
            output += operationStack[stackPtr--] + " ";
            // add the operation from the queue on the stack.
          }
          stackPtr++;
          operationStack[stackPtr] = '-';
          // This section basically goes to try to say that all 
          // negative numbers, -n, can be written as 0 - n, 
          // so they're treated as such.
        }
        else
        {
          output += next;
          // if it's not negative, then it's easy, just add it to the queue.
        }
      }
      else if (next == '*' || next == '/' || next == '%' || next == '+' || 
          next == '-' || next == '^')
      // Are we deaing with a binary operator?
      {
        output += " ";
        // get the output ready.
        if ( stackPtr != -1 && 
            opPrecedence(next, operationStack[stackPtr]) <= 0)
        // Does the operator on top of the stack take precedence?
        {
          output += operationStack[stackPtr--] + " ";
          // pop that operator off the stack onto the queue.
        }
        stackPtr++;
        operationStack[stackPtr] = next;
        // add the new operator onto the stack.
      }
      else if (next == '(')
      // open parenthesis?
      {
        if (i > 0 && !(input.charAt(i-1) == '*' || input.charAt(i-1) == '/' || 
              input.charAt(i-1) == '%' || input.charAt(i-1) == '+' || 
              input.charAt(i-1) == '-' || input.charAt(i-1) == '^'))
        // Are we dealing with an implied multiplication? Like 2(3) = 6...
        {
          if ( input.charAt(i-1) == '(')
          {
            output += "1";
            // Read multiple sets of parens as * 1 * 
            // in this case, so that 2((3)) is read as 2 * 1 * 3.
          }
          output += " ";
          if ( stackPtr != -1 && 
              opPrecedence('*', operationStack[stackPtr]) <= 0)
          // Does another operator take precedence?
          {
            output += operationStack[stackPtr--] + " ";
            // pop it off the stack
          }
          stackPtr++;
          operationStack[stackPtr] = '*';
          // add multiplication to the stack
        }

        stackPtr++;
        operationStack[stackPtr] = next;
        // add the parenthesis to the stack
      }
      else if (next == ')')
      // close parenthesis?
      {
        while (stackPtr > -1 && operationStack[stackPtr] != '(')
        {
          output += " " + operationStack[stackPtr--];
          // pop all the operators of the stack until we reach the end 
          // or a '('
        }
        if (stackPtr == -1)
        // Did we fall off the stack?  Must be a parenthesis error.
        {
          return "ERROR-PARENS";
        }
        stackPtr--;
        // remove the '(' from the stack.
        if ( (i < (input.length() - 1)) && !(input.charAt(i+1) == '+' ||
              input.charAt(i+1) == '-' || input.charAt(i+1) == '*' || 
              input.charAt(i+1) == '/' || input.charAt(i+1) == '^' ||
              input.charAt(i+1) == '%' || input.charAt(i+1) == '(' || 
              input.charAt(i+1) == ')'))
        // Check for an implied multiiplies like (2)2 = 4.
        {
          output += " ";
          if (stackPtr != -1 && 
              opPrecedence('*', operationStack[stackPtr]) <= 0)
          {
            output += operationStack[stackPtr--] + " ";
          }
          stackPtr++;
          operationStack[stackPtr] = '*';
        }
      }
      else
      // A different character?  Send an error.
      {
        return "ERROR-NON-NUMERICAL";
      }
    }

    while (stackPtr > -1)
    {
      output += " " + operationStack[stackPtr--];
      // Pop all other operators off the stack.
    }
    return output;
    // Return the RPN'd value.
  }

  private static String eval(String rpnExpression)
  {
    if (rpnExpression.indexOf("ERROR") == -1)
    // We don't already have an error, do we?  If not, continue.
    {
      double [] solnStack = new double[rpnExpression.length()];
      // This is the stack that we hold the solution on.
      int stackPtr = -1;
      // Since nothing is on the stack, move the stack pointer off of it.
      String [] tkns = rpnExpression.split(" ");
      // Split our string around the spaces we made in the RPN method.
      String next;
      for (int i = 0; i < tkns.length; i++)
      // For each token that the split made...
      {
        next = tkns[i];
        // to keep me from writing tkns[i] over and over...
        if ( !(next.equals("*") || next.equals("/") || next.equals("%") || 
              next.equals("+") || next.equals("-") || next.equals("^")) )
        // Assuming what we're dealing with is numeric 
        // and not a binary operator...
        {
          try
          {
            stackPtr++;
            solnStack[stackPtr] = Double.parseDouble(next);
            // Pop the answers onto the solution stack.
          }
          catch(NumberFormatException e)
          // If there's a problem, it's because of evaluation failing.
          {
            return "ERROR-EVAL";
          }
        }
        else if (next.equals("+") && stackPtr > 0)
        // If we're adding,
        {
          solnStack[stackPtr-1] = solnStack[stackPtr-1] + solnStack[stackPtr];
          stackPtr--;
          // pop two variabes off, add them, 
          // pop the answer on (just move the pointer by one).
        }
        else if (next.equals("-") && stackPtr > 0)
        // if we're subtracting, similar to addition.
        {
          solnStack[stackPtr-1] = solnStack[stackPtr-1] - solnStack[stackPtr];
          stackPtr--;
        }
        else if (next.equals("-") && stackPtr > -1)
        // if only one number on the stack, 
        // and we have a '-' it's probably negative.
        {
          solnStack[stackPtr] = 0 - solnStack[stackPtr];
        }
        else if (next.equals("*") && stackPtr > 0)
        // if we're multiplying, similar to addition.
        {
          solnStack[stackPtr-1] = solnStack[stackPtr-1] * solnStack[stackPtr];
          stackPtr--;
        }
        else if (next.equals("/") && stackPtr > 0)
        // if we're dividing, similar to addition.
        {
          solnStack[stackPtr-1] = solnStack[stackPtr-1] / solnStack[stackPtr];
          stackPtr--;
        }
        else if (next.equals("^") && stackPtr > 0)
        // if we're using exponents, similar to addition
        {
          solnStack[stackPtr-1] = Math.pow(solnStack[stackPtr-1],
              solnStack[stackPtr]);
          stackPtr--;
        }
        else if (next.equals("%") && stackPtr > 0)
        // modulus, similar to addition.
        {
          solnStack[stackPtr-1] = solnStack[stackPtr-1] % solnStack[stackPtr];
          stackPtr--;
        }
      }
      return Double.toString(solnStack[0]);
      // Return our answer.
    }
    else
    // otherwise return the expression (if there was an error to start)
    {
      return rpnExpression;
    }
  }
      
  // If you aren't familiar with reverse polish notation (post fix)
  // http://en.wikipedia.org/wiki/Reverse_Polish_notation#Example

  private static int opPrecedence(char op1, char op2)
  // checking operator precedence of two operators.
  {
    if (op2 == '(' || op2 == ')')
    // parentheses have the highest precedence, they win.
    {
      return 1;
    }
    else if (op1 == '^')
    {
      if (op2 == '^')
      {
        return 0;
      }
      else
      {
        return 1;
      }
    }
    else if (op1 == '/' || op1 == '*' || op1 == '%')
    {
      if (op2 == '/' || op2 == '*' || op2 == '%')
      {
        return 0;
        // two operators have the same precedence ('*' or '/')
      }
      else
      {
        return 1;
        // otherwise operator 1 wins.
      }
    }
    else if (op2 == '/' || op2 == '*' || op2 == '%')
    {
      return -1;
      // operator 2 wins.
    }
    else
    {
      return 0;
      // They both have the same precedence ('+' or '-')
    }
  }
}