java实现的四则运算解析器

#java #tech

学过编译原理的同学都知道有最开始的一步就是词法分析.
下面就是一次入门级的实践.(看之前需要了解一下什么是二叉树)

主要有三个类:

  • Node.java 二叉树的java model
public class Node {

    Node     left  = null;
    Node     right = null;
    String   value;
    NodeType nodeType;
    // 是否在括号中
    Boolean  isBlock;

    public Node(String value, NodeType nodeType){
        super();
        this.value = value;
        this.nodeType = nodeType;
        this.isBlock = false;
    }

    public Node(String value, NodeType nodeType, Boolean isBlock){
        super();
        this.value = value;
        this.nodeType = nodeType;
        this.isBlock = isBlock;
    }

    public Node(){
        super();
    }

    @Override
    public String toString() {
        return value + ":" + nodeType;
    }

    public void setIsBlock(Boolean isBlock) {
        this.isBlock = isBlock;
    }

    public boolean isHigerThanOther(Node other) {
        if (other.isBlock) {
            return false;
        }
        if (("*".equals(value) || "/".equals(value)) && ("+".equals(other.value) || "-".equals(other.value))) {
            return true;
        }
        return false;
    }

}
  • NodeType.java 节点的枚举类型,四则运算中有数字和运算符两种
public enum NodeType {
    num, op;
}
  • Parser.java 关键类,paser的实现
public class Parser {

    private char[] ca;
    private int    total;
    private int    point = 0;

    public Parser(String s){
        s = s.replaceAll("\\s+", "");
        ca = s.toCharArray();
        total = ca.length;
    }

    public Node parse() {
        Node root = getNode();
        while (true) {
            Node node = getNode();
            if (null == node) {
                break;
            }
            if (!NodeType.op.equals(node.nodeType)) {
                throw new RuntimeException("格式错误!");
            }
            Node nextNode = getNode();
            if (nextNode == null) {
                throw new RuntimeException("操作符后面不能为空!");
            }
            node.right = nextNode;
            if (node.isHigerThanOther(root)) {
                node.left = root.right;
                root.right = node;
            } else {
                node.left = root;
                root = node;
            }
        }

        return root;
    }

    /**
     * 获取单个node
     *
     * @return
     */
    Node getNode() {
        String v = "";
        while (true) {
            if (point == total) {
                break;
            }
            char c = ca[point];
            point++;
            if (c == '(') {
                String sub = subStringInBracket();
                Parser parser = new Parser(sub);
                Node subNode = parser.parse();
                subNode.setIsBlock(true);
                return subNode;
            }
            if (isOp(c)) {
                if ("".equals(v)) {
                    return new Node(String.valueOf(c), NodeType.op);
                } else {
                    point--;
                    return new Node(v, NodeType.num);
                }
            }
            v += c;
        }
        return "".equals(v) ? null : new Node(v, NodeType.num);
    }

    public boolean isOp(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    /**
     * 获取括号中的字符串
     *
     * @return
     */
    public String subStringInBracket() {
        StringBuilder sb = new StringBuilder();
        if (ca[point - 1] != '(') {
            throw new RuntimeException("4");
        }
        int bracketFlag = 0;
        for (;;) {
            char c = ca[point];
            if (c == ')' && bracketFlag == 0) {
                point++;
                return sb.toString();
            }
            if (c == '(') {
                bracketFlag++;
            }
            if (c == ')' && bracketFlag > 0) {
                bracketFlag--;
            }
            sb.append(c);
            point++;
            if (point == total) {
                throw new RuntimeException("找不到')',格式错误");
            }
        }
    }

    /**
     * 递归计算node的值
     *
     * @param node
     * @return
     */
    public Integer getResult(Node node) {
        Integer left = null;
        Integer right = null;
        if (NodeType.num.equals(node.left.nodeType)) {
            left = Integer.valueOf(node.left.value);
        } else {
            left = getResult(node.left);
        }
        if (NodeType.num.equals(node.right.nodeType)) {
            right = Integer.valueOf(node.right.value);
        } else {
            right = getResult(node.right);
        }

        String op = node.value;

        if ("+".equals(op)) {
            return left + right;
        }
        if ("-".equals(op)) {
            return left - right;
        }
        if ("*".equals(op)) {
            return left * right;
        }
        if ("/".equals(op)) {
            return left / right;
        }
        throw new RuntimeException("3");
    }
}
  • ParserTest.java 测试
public class ParserTest extends TestCase {

    public void test_getResult() {

        Parser parser = new Parser("1+2+3");
        assertEquals(6, parser.getResult(parser.parse()).intValue());

        parser = new Parser("1*2*3");
        assertEquals(6, parser.getResult(parser.parse()).intValue());

        parser = new Parser("4/2/1");
        assertEquals(2, parser.getResult(parser.parse()).intValue());

        parser = new Parser("1+2*3-1+100/2");
        assertEquals(56, parser.getResult(parser.parse()).intValue());

        parser = new Parser("(1+2)*3/9");
        assertEquals(1, parser.getResult(parser.parse()).intValue());

        parser = new Parser("(1+2)*(2+3)/(5-2)");
        assertEquals(5, parser.getResult(parser.parse()).intValue());

        parser = new Parser("200*73/(543-178)");
        assertEquals(40, parser.getResult(parser.parse()).intValue());

        parser = new Parser("200*73/(543-178)-(2+2)/2*(((4-1)*2+(3-1))+1)");
        assertEquals(22, parser.getResult(parser.parse()).intValue());

        parser = new Parser("(2+2)/2*(((4-1)*2+(3-1))+1)");
        assertEquals(18, parser.getResult(parser.parse()).intValue());

        parser = new Parser("200*73/(543-178)-(2+2)/2*(((4-1)*2+(3-1))+1)-(1+2)*(2+3)/(5-2)");
        assertEquals(17, parser.getResult(parser.parse()).intValue());

        parser = new Parser("(((((1+2)*(2+3)/(5-2)+1)*(1+1))/4-1)*3+4)*10");
        assertEquals(100, parser.getResult(parser.parse()).intValue());
    }

}