/*
 * โครงสร้างข้อมูล : ฉบับวาจาวา
 * http://www.cp.eng.chula.ac.th/~somchai/books
 */
package dataStructures;

/**
 * คลาสที่สร้างนิพจน์คณิตศาสตร์ด้วยต้นไม้นิพจน์
 * @author สมชาย ประสิทธิ์จูตระกูล
 */
public class Expression extends BinaryTree {

  public Expression(Expression e) {
    root = copy(e.root);
  }
  public Expression(List infix) {
    List postfix = infix2Postfix(infix);
    Stack s = new ArrayStack(10);
    for (int i=0; i<postfix.size(); i++) {
      String token = (String)postfix.get(i);
      if (!isOperator(token)) {
        s.push(new Node(token, null, null));
      } else {
        Node right = (Node) s.pop();
        Node left = (Node) s.pop();
        s.push(new Node(token, left, right));
      }
    }
    root = (Node) s.pop();
  }
  //--------------------------------------------------------
  public double eval() {
    return eval(root);
  }
  private double eval(Node r) {
    if (r == null) return 0;
    if (r.isLeaf())
      return Double.parseDouble((String) r.element);
    double vLeft = eval(r.left);
    double vRight = eval(r.right);
    if (r.element.equals("+")) return vLeft + vRight;
    if (r.element.equals("-")) return vLeft - vRight;
    if (r.element.equals("*")) return vLeft * vRight;
    if (r.element.equals("/")) return vLeft / vRight;
    if (r.element.equals("^")) return Math.pow(vLeft,vRight);
    throw new IllegalStateException();
  }
  //--------------------------------------------------------
  public void diff() {
    root = diff(root);
  }
  private Node diff(Node r) {
    if (r == null) return null;
    String s = (String) r.element;
    if ( r.isLeaf() ) {
      r.element = (s.equals("x") ? "1" : "0");
    } else {
      if (s.equals("+"))      r = diffSum(r);
      else if (s.equals("-")) r = diffSum(r);
      else if (s.equals("^")) r = diffExpo(r);
      else if (s.equals("*")) r = diffMult(r);
      else if (s.equals("/")) r = diffDiv(r);
    }
    return r;
  }
  private Node diffSum(Node r) {
    r.left = diff(r.left);
    r.right = diff(r.right);
    return r;
  }
  private Node diffMult(Node r) {
    Node u = copy(r.left);
    Node v = copy(r.right);
    Node du = diff(r.left);
    Node dv = diff(r.right);
    Node t1 = new Node("*", u, dv);
    Node t2 = new Node("*", v, du);
    return new Node("+", t1, t2);
  }
  private Node diffExpo(Node r) {
    //... exercise 
    return r;
  }
  private Node diffDiv(Node r) {
    //... exercise
    return r;
  }
  //--------------------------------------------------------
  public static List infix2Postfix(List infix) {
    List postfix = new ArrayList(infix.size());
    Stack s = new ArrayStack(infix.size());
    for (int i = 0; i < infix.size(); ++i) {
      String token = (String) infix.get(i);
      if (!isOperator(token)) {
        postfix.add(token);
      } else {
        int p = outPriority(token);
        while (!s.isEmpty() && inPriority((String) s.peek()) >= p) {
          postfix.add(s.pop());
        }
        if (token.equals(")")) s.pop(); else s.push(token);
      }
    }
    while (!s.isEmpty()) postfix.add(s.pop());
    return postfix;
  }

  private static String operators = "+-*/^()";
  private static int[] outPriority = { 3, 3, 5, 5, 7, 9, 1 };
  private static int[] inPriority = { 3, 3, 5, 5, 7, 0 };
  private static int outPriority(String x) {
    return outPriority[operators.indexOf(x)];
  }
  private static int inPriority(String x) {
    return inPriority[operators.indexOf(x)];
  }
  private static boolean isOperator(String x) {
    return operators.indexOf(x) >= 0;
  }

}