题解 | #表达式求值#

啃了一下午A了，不容易啊，记录下思路：
1、preExecute() 预处理函数，先将字符串处理成List集合，主要为了转换多位整数
2、buildTree() 递归建树，将表达式转换为表达式树，其中易错点在处理负数的地方
3、print() 将表达式树后序遍历，将遍历结果存放在List中
4、calculate() 计算后序遍历List,从左到右遍历若元素是运算符，则将栈顶部前两个数字出栈并计算，否则，将该元素入栈，遍历完毕取栈顶元素返回。
5、打印结果

public class ExpressionTree {
    private static int maxn = 1000;
    private static int lch[] = new int[maxn], rch[] = new int[maxn];
    private static String op[] = new String[maxn];
    private static int nc = 0;
    private static List<String> postStr = new ArrayList<>();
    private static Set<String> set = new HashSet<>();

    static {
        set.addAll(Arrays.asList("+", "-", "*", "/"));
        lch[0] = rch[0] = 100000;
    }

    private static int buildTree(List<String> expression, int x, int y) {
        int i, c1 = -1, c2 = -1, p = 0;
        int u;
        if (y - x == 1) {//only rest one char,set num of calculated.
            u = ++nc;
            lch[u] = 100000;
            rch[u] = 100000;
            op[u] = expression.get(x);
            return u;
        }
        else if (y - x == 0) {//可能出现负数的情况，如：-1*(-1-1)，此时c1在第一个'-'号的位置，而起点x与之相同
            u = ++nc;
            lch[u] = 100000;
            rch[u] = 100000;
            op[u] = "0";
            return u;
        }
        for (i = x; i < y; i++) {
            switch (expression.get(i)) {
                case "(":
                    p++;
                    break;
                case ")":
                    p--;
                    break;
                case "-":
                case "+":
                    if (p == 0) c1 = i;
                    break;
                case "*":
                case "/":
                    if (p == 0) c2 = i;
                    break;
            }
        }
        if (c1 < 0) c1 = c2;
        if (c1 < 0) return buildTree(expression, x + 1, y - 1);
        u = ++nc;
        lch[u] = buildTree(expression, x, c1);
        rch[u] = buildTree(expression, c1 + 1, y);
        op[u] = expression.get(c1);//set sign of calculated;
        return u;
    }

    //(a+b)*c
    private static void print(int root) {
        if (root == 100000) return;
        print(lch[root]);
        print(rch[root]);
        if(op[root]!=null)postStr.add(op[root]);
//        System.out.println(op[root]);
    }


    /**
     * 后缀表达式计算结果，a b + c * d e / +
     * 从左到右开始计算，
     * 遇到数字进栈，遇到运算符时将栈顶前2个元素出栈计算再将结果入栈。
     *
     * @param postStr
     * @return
     */
    private static int calculate(List<String> postStr) {
        Stack<String> stack = new Stack<>();
        for (String item : postStr) {
            if (set.contains(item)) {
                int operNum2 = Integer.valueOf(stack.pop());
                int operNum1 = Integer.valueOf(stack.pop());
                int result = 0;
                switch (item) {
                    case "+":
                        result = operNum1 + operNum2;
                        break;
                    case "-":
                        result = operNum1 - operNum2;
                        break;
                    case "*":
                        result = operNum1 * operNum2;
                        break;
                    case "/":
                        result = operNum1 / operNum2;
                        break;
                }
                stack.push(String.valueOf(result));
            } else {
                stack.push(item);
            }
        }
        return Integer.valueOf(stack.pop());
    }

    //-1*(-1-1)
    private static List<String> preExecute(String e) {
        List<String> result = new ArrayList<>();
        int index = 0;
        int i;
        for (i = 0; i < e.length(); i++) {
            if (!Character.isDigit(e.charAt(i))) {
                if (index < i) result.add(e.substring(index, i));
                result.add(String.valueOf(e.charAt(i)));
                index = i + 1;
            }
        }
        if (index < i) result.add(e.substring(index, i));
        return result;
    }

    public static void main(String[] args) {
        Scanner sa = new Scanner(System.in);
        while (sa.hasNext()) {
            String expression = sa.next();
            List<String> list = preExecute(expression);
            int root = buildTree(list, 0, list.size());
            print(root);
            int result = calculate(postStr);
            System.out.println(result);
        }
    }
}