抽象语法树解析四则运算

package lang;
import java.util.Stack;

/**
 * @author wanqilin
 * @date 2019/6/14
 * @description
    一次抽象语法树(AST)的练习，进行四则运算的分析和运算
    方法很简单，倒序搜索字符串中优先级最低的运算符，将该运算符提出来作为父节点，两边的字符串作为子节点
    若没有搜索到操作符，那么该节点为数字
    接着对子节点也进行相同的操作，这样我们能得到一个抽象语法树

    其中数的节点分为操作符和数字，而数的root节点一定是操作符
    我们对该数进行前序遍历，最终计算出返回值
 
    ComputeUnit有两个还未完善的地方，一是valueOf方法还未支持浮点数
    另外是Operator::compute 同样为支持浮点数
 */
public class ComputeUnit {
    public static void main(String[] args) {
        ComputeUnit compute = new ComputeUnit();
        System.out.println(compute.compute("(5 + 11 + 485 / 15 + 46 * (15 + 20  )- 156 - 60 * 20)"));
        System.out.println((5 + 11 + 485 / 15 + 46 * (15 + 20  )- 156 - 60 * 20));
    }

    public String compute(String str){
        Stack<Node> s = new Stack<>();
        Node head = new Node(0,str.length() - 1);
        s.push(head);
        while (!s.isEmpty()){
            Node n = s.pop();
            clearBracketOutSideAndSpace(n,str);
            int bracketCnt = 0;
            int op = 0,opPriority = Integer.MAX_VALUE;
            boolean isOpLast = false;
            for (int i = n.ep; i >= n.sp; i--) {
                char c = str.charAt(i);
                if (c == ')') bracketCnt ++;
                else if (c == '('){
                    bracketCnt--;
                    if (bracketCnt < 0) return "err1";
                }
                if (bracketCnt == 0){
                    switch (c){
                        case ' ':
                            break;
                        default:
                            if (Operate.isOperate(c)){
                                Operate operate = Operate.valueOf(c);
                                if (isOpLast && operate.priority == 1){
                                    return "err2";
                                }
                                isOpLast = true;
                                if (opPriority > operate.priority){
                                    opPriority = operate.priority;
                                    op = i;
                                }
                            }else isOpLast = false;
                    }
                }
            }
            if (bracketCnt > 0) return "err3";

            if (opPriority == Integer.MAX_VALUE){
                Number val = valueOf(n,str);
                if (val == null) return "err4";

                NumberNode tmp = new NumberNode(n.parent,n.left,n.right,n.sp,n.ep);
                tmp.number = val;
                if (n.parent == null) head = tmp;
                else{
                    if (n.parent.left == n) n.parent.left = tmp;
                    else n.parent.right = tmp;
                }
                continue;
            }

            OperatorNode operatorNode = new OperatorNode(n.parent,n.left,n.right,op,op);
            operatorNode.operate = Operate.valueOf(str.charAt(op));

            if (n.parent == null) head = operatorNode;
            else{
                if (n.parent.left == n) n.parent.left = operatorNode;
                else n.parent.right = operatorNode;
            }

            Node left = new Node(operatorNode,null,null,n.sp,op - 1),right = new Node(operatorNode,null,null,op + 1,n.ep);
            operatorNode.left = left;operatorNode.right = right;
            s.push(left);s.push(right);
        }

        return computeNode(head);
    }

    private void clearBracketOutSideAndSpace(Node n, String str) {
        clearBracketOutSide(n,str);
        int si,ei;
        for (si = n.sp;si < n.ep && str.charAt(si) == ' ';si++);
        for (ei = n.ep;ei > n.sp && str.charAt(ei) == ' ';ei--);

        n.sp = si;n.ep = ei;
    }

    private String computeNode(Node head) {
        Stack<RecInfo> s = new Stack<>();
        s.push(new RecInfo(head,1));
        while (!s.isEmpty()){
            RecInfo rec = s.pop();
            switch (rec.state){
                case 1:
                    if (rec.cur instanceof NumberNode){
                        rec.state = 3;
                        s.push(rec);
                    }else{
                        rec.state++;
                        s.push(rec);
                        s.push(new RecInfo(rec.cur.left,1));
                    }
                    break;
                case 2:
                    rec.state++;
                    s.push(rec);
                    s.push(new RecInfo(rec.cur.right,1));
                    break;
                case 3:
                    Number res = null;
                    if (rec.cur instanceof NumberNode){
                        res = ((NumberNode) rec.cur).number;
                    }else{
                        res = ((OperatorNode) rec.cur).operate.compute(rec.left,rec.right);
                    }
                    if (s.isEmpty()){
                        return res.toString();
                    }
                    if (s.peek().cur.left == rec.cur) s.peek().left = res;
                    else s.peek().right = res;
                    break;
            }
        }
        return "err10";
    }

    private Number valueOf(Node n, String str) {
        return Integer.valueOf(str.substring(n.sp,n.ep+1));
    }

    private void clearBracketOutSide(Node n, String str) {
        int sp = n.sp,ep = n.ep,si = -1,ei = -1;
        for (int i = sp; i < ep; i++) {
            char c = str.charAt(i);
            if (c == '(') si = i;
            else if (c != ' ') break;
        }
        for (int i = ep; i > sp; i--) {
            char c = str.charAt(i);
            if (c == ')') ei = i;
            else if (c != ' ') break;
        }

        if (ei != -1 && si != -1){
            n.sp = si + 1;
            n.ep = ei - 1;
        }
    }

}
class Node{
    Node parent,left,right;
    int sp,ep; // start point , end point

    public Node(int sp, int ep) {
        this.sp = sp;
        this.ep = ep;
    }

    public Node(Node parent, Node left, Node right, int sp, int ep) {
        this.parent = parent;
        this.left = left;
        this.right = right;
        this.sp = sp;
        this.ep = ep;
    }
}
class OperatorNode extends Node{
    Operate operate;

    public OperatorNode(Node parent, Node left, Node right, int sp, int ep) {
        super(parent, left, right, sp, ep);
    }
}
class NumberNode extends Node{
    Number number;

    public NumberNode(Node parent, Node left, Node right, int sp, int ep) {
        super(parent, left, right, sp, ep);
    }
}
enum Operate{
    add(1),sub(1),mul(2),div(2),none(0);

    int priority;
    Operate(int priority){
        this.priority = priority;
    }
    static Operate valueOf(char ch){
        switch (ch){
            case '+':
                return add;
            case '-':
                return sub;
            case '*':
                return mul;
            case '/':
                return div;
            default:
                return none;
        }
    }

    Number compute(Number n1,Number n2){
        switch (this){
            case add:
                return (Integer)n1 + (Integer)n2;
            case sub:
                return (Integer)n1 - (Integer)n2;
            case mul:
                return (Integer)n1 * (Integer)n2;
            case div:
                return (Integer)n1 / (Integer)n2;
        }
        return null;
    }

    static boolean isOperate(char ch){
        return valueOf(ch) != none;
    }
}
//recursion information
class RecInfo{
    Node cur;
    int state;// 1:left 2: right 3: mid
    Number left,right;
    public RecInfo(Node cur, int state) {
        this.cur = cur;
        this.state = state;
    }
}