问题描述：

        给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右括号，返回公式的计算结果。
【举例】

        str="48*((70-65)-43)+81"，返回-1816。
        str="3+1*4"，返回7。
        str="3+(1*4)"，返回7。
【说明】

        1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。

        2.如果是负数，就需要用括号括起来，比如"4*(-3)"。但如果负数作为公式的开头 或括号部分的开头，则可以没有括号，比如"-3*4"和"(-3*4)"都是合法的。

        3.不用考虑计算过程中会发生溢出的情况。

思想：

        本题可以使用递归的方法。从左到右遍历str，如果遇到左括号就进入递归，相当于将括号里的内容当成一个新的公式，等括号里的内容计算完成后将结果返回，此时再接着继续遍历str，直到str遍历完或者遇到右括号，这样就相当于str中不再包含左右括号。递归过程需要返回两个结果，一个是当前子公式计算的结果，一个是当前遍历到的str的位置。这样上级递归函数就可以根据这两个数据继续向后遍历。计算公式的结果时，先将乘法和除法计算完，最后再统一计算计算加法和减法。

代码：

    public static int getValue(String str) {return value(str.toCharArray(), 0)[0];}//从str[i...]往下算，遇到字符串终止为止或者右括号就停止//返回两个数，长度为2的数组//0）负责这一段的结果是多少//1）负责这一段计算到了那个位置public static int[] value(char[] str, int i) {LinkedList que = new LinkedList<>();int cur = 0;int[] bra = null;//从i出发，开始撸串while (i < str.length && str[i] != ')') {if (str[i] >= '0' && str[i] <= '9') {cur = cur * 10 + str[i++] - '0';} else if (str[i] != '(') {//遇到的是运算符号addNum(que, cur);que.addLast(String.valueOf(str[i++]));cur = 0;} else {//遇到左括号bra = value(str, i + 1);cur = bra[0];i = bra[1] + 1;}}addNum(que, cur);return new int[]{getNum(que), i};}public static void addNum(LinkedList que, int num) {if (!que.isEmpty()) {int cur = 0;String top = que.pollLast();if (top.equals("+") || top.equals("-")) {que.addLast(top);} else {cur = Integer.valueOf(que.pollLast());num = top.equals("*") ? (cur * num) : (cur / num);}}que.addLast(String.valueOf(num));}public static int getNum(LinkedList que) {int res = 0;boolean add = true;String cur = null;int num = 0;while (!que.isEmpty()) {cur = que.pollFirst();if (cur.equals("+")) {add = true;} else if (cur.equals("-")) {add = false;} else {num = Integer.valueOf(cur);res += add ? num : (-num);}}return res;}public static void main(String[] args) {String exp = "48*((70-65)-43)+8*1";System.out.println(getValue(exp));exp = "4*(6+78)+53-9/2+45*8";System.out.println(getValue(exp));exp = "10-5*3";System.out.println(getValue(exp));exp = "-3*4";System.out.println(getValue(exp));exp = "3+1*4";System.out.println(getValue(exp));}