import java.util.*;

/**
 * Skeleton for the second assignment of the course Datastructuren
 * 2007/2008 at the University of Amsterdam.
 *
 * <ul>
 *   <li>Usage: <code>java Assignment2 [-infix | -rpn]</code>
 * </ul>
 *
 * By default the program expects infix expressions.
 */
public final class Assignment2 {
  /**
   * Usage message to be displayed in case of invalid arguments.
   */
  public static final String USAGE_MSG =
      "Usage:\n    java Assignment2 [-infix | -rpn]";
  /**
   * Default command line prompt.
   */
  public static final String PROMPT_STRING = ">> ";
  /**
   * Flag to indicate use of infix notation.
   */
  public static final int INFIX_NOTATION = 0;
  /**
   * Flag to indicate use of RPN notation.
   */
  public static final int RPN_NOTATION = 1;
  /**
   * Flag of default notation.
   */
  public static final int DEFAULT_NOTATION = INFIX_NOTATION;

  /**
   * Inspects the given string and returns an appropriate instance of a
   * subclass of {@link Token}.
   *
   * @param tok the token to evaluate.
   * @return <code>Token</code> representation of <code>tok</code>.
   * @throws java.lang.RuntimeException
   *             if the token is not a known operator nor parseable
   *             as a number.
   */
  public static Token toToken(String tok) throws RuntimeException {
    if (tok.equals("+") || tok.equals("-") 
        || tok.equals("*") || tok.equals("/"))
      return new Operator(tok);
    else
      return new Operand(Double.parseDouble(tok));
  }

  /**
   * Returns the sequence of tokens in the given expression as a
   * {@link TokenQueue}.
   *
   * The expression is evaluated according to the supplied notation type.
   *
   * @param expr         the expression the parse
   * @param notationType the type of syntax used by the expression, i.e. {@link
   *                     #INFIX_NOTATION} or {@link #RPN_NOTATION}
   * @return             a queue containing all tokens, in left-to-rght order
   * @throws java.lang.RuntimeException
   *             if the expression is syntactically incorrect
   */
  public static TokenQueue parseExpr(String expr, int notationType) {

    TokenQueue tokens = new TokenStacksQueue();
    int start = 0, pos = 0;
    while (pos <= expr.length()-1) {
        //look for either a number or minus sign
        if (isNum(expr.charAt(pos)) || expr.charAt(pos) == '-' ) {
          start = pos;
          while ((pos <= expr.length()-1) && isNum(expr.charAt(pos))) 
            pos++;
          //System.out.println("'" + expr.substring(start, pos) + "'");
          tokens.enqueue(toToken(expr.substring(start, pos)));
        } else if (isOp(expr.charAt(pos))) {
          //System.out.println("'" + expr.substring(pos, pos+1) + "'");
          tokens.enqueue(toToken(expr.substring(pos, pos+1)));
          pos++;
        } else if (expr.charAt(pos) == ' ') {
          pos++;
        } else {
	  throw new java.lang.RuntimeException(
            "Illegal character in expression: " + expr.substring(pos, pos+1));
        }
    }
    return tokens;
  }

  private static boolean isNum(char n) {
    return ((n >= '0' && n <= '9') || n == '.');
  }
  private static boolean isOp(char n) {
    return (n == '+' || n == '-' || n == '*' || n == '/');
  }


  /**
   * Evaluates the given expression, assuming the specified notation format.
   *
   * @param expr         the expression to evaluate
   * @param notationType the type of syntax used by the expression that must be
   *                     evaluated, i.e. {@link #INFIX_NOTATION} or {@link
   *                     #RPN_NOTATION}
   * @return             the result of the calculation
   */
  public static double calc(TokenQueue expr, int notationType) {
    if (notationType == INFIX_NOTATION)
      return calcInfix(expr);
    return calcRPN(expr);
  }

  /**
   * Evaluate the given expression as if it were in infix notation.
   *
   * This methods applies Dijkstra's Shunting Yard algorithm as a first step,
   * thus converting the infix expression to an equivalent RPN expression. The
   * RPN expression is then evaluated using {@link #calcRPN}.
   *
   * @param expr the expression to evaluate
   * @return     the result of the calculation
   */
  public static double calcInfix(TokenQueue expr) {
    // shunting yard
    TokenQueue rpnexpr = new TokenStacksQueue();
    return calcRPN(rpnexpr);
  }

  /**
   * Evaluate the given expression as if it were in RPN notation.
   *
   * @param expr the expression to evaluate
   * @return     the result of the calculation
   * @throws java.lang.RuntimeException
   *             if the expression is syntactically incorrect
   */
  public static double calcRPN(TokenQueue expr) {
    Token tok = new Operand(0);
    TokenArrayStack stack = new TokenArrayStack();

    while (!expr.isEmpty()) {
      tok = expr.dequeue();
      if (tok instanceof Operand) {
        stack.push(tok);
        System.out.println(tok);
      } else if (tok instanceof Operator) {
        apply(stack, tok);
      } else {
        throw new java.lang.RuntimeException("unexpected token in stack");
      }
    }
    return ((Operand)stack.pop()).getValue();
  }
  
  private static double apply(TokenStack stack, Token tok) {
    double a, b;
    while (1==1) {
      if (stack.isEmpty()) {
        // in case there is no operand
        // the result should be the identity
        // of the operator in question.
        switch(tok.toString().charAt(0)) {
          case '*': stack.push(new Operand(1)); break;
          case '/': stack.push(new Operand(1)); break;
          default: stack.push(new Operand(0));
        }
      } else {
        a = ((Operand)stack.pop()).getValue();
        System.out.println(a);
        if (stack.isEmpty())
          return a;
        else if (stack.peek() instanceof Operand)
          b = ((Operand)stack.pop()).getValue();
        else
          // in case there is only one operand
          // the second operand should default to the identity
          // of the operator in question.
          switch(tok.toString().charAt(0)) {
            case '*': b = 1; break;
            case '/': b = 1; break;
            default: b = 0;        // this goes for plus and minus.
          }
        System.out.println(b);
        // Java can not switch strings!
        switch(tok.toString().charAt(0)) {
          case '+': stack.push(new Operand(a+b)); break;
          case '-': stack.push(new Operand(a-b)); break;
          case '*': stack.push(new Operand(a*b)); break;
         case '/': stack.push(new Operand(a/b)); break;
        }
      }
    }
  }

  /**
   * Show command prompt and evaluate expressions.
   *
   * The prompt will keep on returning, until either EOF from stdin is
   * received, or an exception is thrown.
   *
   * @param notationType the type of syntax expected on the command line, i.e.
   *                     {@link #INFIX_NOTATION} or {@link #RPN_NOTATION}
   */
  public static void prompt(int notationType) {
    Scanner stdin = new Scanner(System.in);

    /*
     * Evaluate each line after 'return' has been pressed, print the output,
     * and show the prompt again.
     */
    System.out.print(PROMPT_STRING);
    while (stdin.hasNextLine()) {
      //try {
        System.out.println(calc(parseExpr(stdin.nextLine(), notationType),
                                notationType));
      //} catch (RuntimeException ex) {
      //  System.out.printf("Error: %s\n", ex.getMessage());
      //}

      System.out.print(PROMPT_STRING);
    }
  }

  /**
   * Print a message to stderr and exit with value 1.
   *
   * @param msg the error message
   */
  private static void errorExit(String msg) {
    System.err.printf("Error: %s\n", msg);
    System.exit(1);
  }

  /**
   * Main method of the program.
   *
   * Parses the command line options and starts the command line interface.
   *
   * See the {@link Assignment2 class description} for an overview of the
   * accepted paramers.
   *
   * @param args the command line arguments passed to the program
   */
  public static void main(String[] args) {
    int notationType = DEFAULT_NOTATION;

    /* Parse command line arguments. */
    if (args.length > 0) {
      if (args.length > 1) {
        errorExit(String.format("too many arguments.\n%s", USAGE_MSG));
      }

      /* Determine what kind of notation to use. */
      if (args[0].equals("-infix")) {
        notationType = INFIX_NOTATION;
      }
      else if (args[0].equals("-rpn")) {
        notationType = RPN_NOTATION;
      }
      else {
        errorExit(String.format("unknown argument '%s'.\n%s", args[0],
                                USAGE_MSG));
      }
    }

    /* Start the interface. */
    prompt(notationType);
  }
}