package basictype;

import java.util.HashMap;
import java.util.Map;

public class DijkstraEval {
  // Give priority to / over * over -  over +
  private static final Map<String, Integer> priority;
  static {
    priority = new HashMap<String, Integer>();
    priority.put("(", -1); // opening parenthesis are processed only when a closing parenthesis is met
    priority.put("+", 0);
    priority.put("-", 1);
    priority.put("*", 2);
    priority.put("/", 3);
  }
  
  //@ Process an operator: get its arguments and push the result on the operands stack.
  private static void processOperator(Stack<Double> values, String op) {
    Double res = values.pop();
    switch (op) {
      case "+" :
	res = values.pop() + res;
	break;
      case "-" :
	res = values.pop() - res;
	break;
      case "*" :
	res = values.pop() * res;
	break;
      case "/" :
	res = values.pop() / res;
	break;
      default :
	throw new RuntimeException("Unknown operator \""+op+"\"");
    }
    values.push(res);
  }
  
  // With args = ( 2.1 + 3.2 - 1.5 ) * 5.7
  // we get (2.1+3.2-1.5)*5.7 = 21.660000000000004
  public static void main(String[] args) {
    Stack<String> operators = new LinkedStack<String>();
    Stack<Double> operands = new LinkedStack<Double>();
    for(String s : args) {
      System.out.print(s);
      switch (s) {
	case "(" :
	  // Push an opening parenthesis as a marker in the operators stack
	  operators.push(s);
	  break;
	case "+" :
	case "-" :
	case "*" :
	case "/" :
	  // It is an operator, push it on the operators stack
	  // but first, process any operator with a higher priority
	  int my_priority = priority.get(s);
	  while ((operators.size() > 0) && (priority.get(operators.top()) > my_priority)) {
	    processOperator(operands, operators.pop());
	  }
	  operators.push(s);
	  break;
	case ")" :
	  // A closing parenthesis: pop operators until an opening parenthesis is found
	  String op = operators.pop();
	  while (!op.equals("(")) {
	    processOperator(operands, op);
	    op = operators.pop();
	  }
	  break;
	default :  // Not a parenthesis nor an operator => it's a number
	  operands.push(Double.parseDouble(s));
      }
    }
    // At the end of the expression, process the operators to compute the value
    while (operators.size() > 0) {
      processOperator(operands, operators.pop());
    }
    if (operands.size() == 0) {
      // If the operands stack is empty, we did not compute anything
      System.out.println("No expression");
    } else if (operands.size() > 1) {
      // If the operands stack has more than one item, an operator is missing.
      System.out.println("Missing operator, or extra operand");
    } else {
      // Else, display the value of the expression
      System.out.println(" = " + operands.pop());
    }
  }
}