美文网首页
抽象语法树解析四则运算

抽象语法树解析四则运算

作者: ssochi | 来源:发表于2019-06-14 15:23 被阅读0次
    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;
        }
    }
    

    相关文章

      网友评论

          本文标题:抽象语法树解析四则运算

          本文链接:https://www.haomeiwen.com/subject/imkpfctx.html