1 package problems_2016_08_10;  2   3 import java.util.LinkedList;  4 /*  5 总述：  6 一共有五个函数分别是：  7                       8                     getvalue（）：  9                           参数：待求的字符串、 10                           作用：一个启动函数，调用value函数 11                           返回值：返回value函数返回值的第一个参数，就是求出的值 12  13                     value（）： 14                           参数：总的待求的字符串，从哪一个位置开始求 15                           作用：这个函数只是可以求不加小括号的情况。 16                                   在这种情况下，把数字和加减乘除放进que双端链表中，并且在放的时候用addnum方法，将乘除处理掉，只剩加减和数字，再将que链表通过getnum方法求出具体的值，返回给上一层。 17                                   因为不能处理小括号，所以碰见小括号就将括号里面的内容抛给下一层递归（value函数）。 18                                   这个value函数只有当发现右括号就停止 19                           返回值：value函数在返回求出的结果的时候，还要返回处理的右括号的位置的索引值 20                     addnum() 21                           参数：que双端链表（这个是在value函数里面定义的），一个待添加进来的数字（value里面的pre） 22                           作用：将字符串中紧挨的数字（表示是一个多位数字）转化为一个数字，并且将他加入到que中，在加入时处理掉que中的乘除号 23                           返回值：没有返回值。因为是在value内部调用的，将当层递归的que变成了只包含加减和数字的字符 24  25                     getnum() 26                           参数：只包含加减和数字的que 27                           作用：将只包含加减和数字的que求出结果 28                           返回值：返回的是每一层小括号中（也是每一层递归当中）的结果 29                     main() 30                           用来进行检测代码功能的函数 31                      32  33 */ 34 public class ExpressionCompute { 35  36     public static int getValue(String str) { 37         return value(str.toCharArray(), 0)[0]; 38     } 39  40     public static int[] value(char[] str, int i) { 41         LinkedList<String> que = new LinkedList<String>(); 42         int pre = 0; 43         int[] bra = null; 44         while (i < str.length && str[i] != ‘)‘) {//如果i（当前操作位置）还没有到达最有端，并且还没有碰到右边的括号，那就继续执行这个递归函数 45             if (str[i] >= ‘0‘ && str[i] <= ‘9‘) {//如果当前操作的是两个运算符号之间的数字 46                 pre = pre * 10 + str[i++] - ‘0‘;//将字符串格式的数字转换为int，减‘0‘相当于减了这个字符的ascii码的值，字符串就变成数字了 47             } else if (str[i] != ‘(‘) {//如果发现也没有碰到了左括号，那说明碰到的是运算符 48                 addNum(que, pre);//这个函数的功能是在pre加入que时看一下que的最后一个字符（肯定是运算符）是否为乘除，是的话进行结算 49                 que.addLast(String.valueOf(str[i++]));//在上面获取到结算的结果加入之后下一位肯定是运算符，也加入 50                 pre = 0;//把pre（用来存放两个运算符之间的数值的变量）清零 51             } else {//说明遇到左括号里  52                 bra = value(str, i + 1);//碰到了左括号，那么就调用这个函数本身，将左括号之后的内容加入到内层递归中（传入的是左括号的下一个位置的索引） 53                 pre = bra[0];//value函数返回一个数组（第29行）   第一个参数为处理过的值 54                 i = bra[1] + 1;//第二个是处理到的值，+1表示下次开始处理的位置 55             } 56         } 57         addNum(que, pre);//最后没有遇到加减乘除  所以还要再来一次addnum 58         return new int[] { getNum(que), i };//返回这一层递归中的值和 处理到的位置i 59     } 60  61     public static void addNum(LinkedList<String> que, int num) {//这个函数的作用可以看成和que.addLast类似，que.addLast是直接把符号插入到que中需要用到的方法，当时当你想插入数字时需要看一下前一个符号的情况，所以自己封装了一个稍微复杂点儿的类似的方法 62         if (!que.isEmpty()) {//判断是否为空 63             int cur = 0; 64             String top = que.pollLast();//先弹出一个 65             if (top.equals("+") || top.equals("-")) { 66                 que.addLast(top);//如果之前是加减，直接把这个数字放进去就可以了 67             } else {//如果之前的符号为乘除，那需要运算之后才能放入（保证que里面始终只放加减符号和数字） 68                 cur = Integer.valueOf(que.pollLast());//再弹出一个 69                 num = top.equals("*") ? (cur * num) : (cur / num);//将第二次弹出的（肯定是一个数字，由19  20行可知） 70             } 71         } 72         que.addLast(String.valueOf(num));//为空的话直接插入num，不为空让算出的结果等于num，好巧妙，又省了几行代码 73     } 74  75     public static int getNum(LinkedList<String> que) {//getnum的方法的作用仅仅是求一个只包含加减和数字的数组，的运算结果 76         int res = 0;//用来保存结果 77         boolean add = true;//用来描述一种状态，其实就是区分加减 78         String cur = null;//用来存放每次新的pollFirst()出来的值（是string类型的） 79         int num = 0;//用来保存cur转换回来的num类型 80         while (!que.isEmpty()) {//判断que里面是不是空的 81             cur = que.pollFirst();//弹出双向列表第一个 82             if (cur.equals("+")) {//如果弹出的是加号 83                 add = true;//将add设置为true，用于下一个检测到数字的时候使用 84             } else if (cur.equals("-")) {//如果弹出的是减号 85                 add = false;//将add设置为false，用于下一个检测到数字的时候使用 86             } else {//如果不为加减那么肯定就是数字了 87                 num = Integer.valueOf(cur);//将字符类型的准换成数字类型 88                 res += add ? num : (-num);//res+=(+num或者-num)，三目运算符大大减少代码数量 89             } 90         } 91         return res;//返回最后求出的结果 92     } 93  94     public static void main(String[] args) {//进行一些测试 95         String exp = "48*((70-65)-43)+8*1"; 96         System.out.println(getValue(exp)); 97  98         exp = "4*(6+78)+53-9/2+45*8"; 99         System.out.println(getValue(exp));100 101         exp = "10-5*3";102         System.out.println(getValue(exp));103 104         exp = "-3*4";105         System.out.println(getValue(exp));106 107         exp = "3+1*4";108         System.out.println(getValue(exp));109 110     }111 112 }