表达式求值算法

1、输入一个字符串，可以包含+ - * / ()、数字、空格，你的算法返回运算结果。

2、要符合运算法则，括号的优先级最高，先乘除后加减。

3、除号是整数除法，无论正负都向 0 取整（5/2=2，-5/2=-2）。

4、可以假定输入的算式一定合法，且计算过程不会出现整型溢出，不会出现除数为 0 的意外情况。

比如输入如下字符串，算法会返回 9：
1
2
>3 * (2-6 /(3 -7))
>

可以看到，这就已经非常接近我们实际生活中使用的计算器了，虽然我们以前肯定都用过计算器，但是如果简单思考一下其算法实现，就会大惊失色：

1、按照常理处理括号，要先计算最内层的括号，然后向外慢慢化简。这个过程我们手算都容易出错，何况写成算法呢！

2、要做到先乘除，后加减，这一点教会小朋友还不算难，但教给计算机恐怕有点困难。

3、要处理空格。我们为了美观，习惯性在数字和运算符之间打个空格，但是计算之中得想办法忽略这些空格。

static int i = 0;
 public int calculate(String s) {
     /*
         将 减法、乘法、除法 转换为 加法
         某个数 num, 如果前面的对应的运算符是 -，那么 将 -num 压入栈中
         这样，我们只需在最后将栈的元素全部弹出，完成加法操作，即可得到最终结果

         对于括号，它存在递归性质
         即
         3 * (2 + 4 * 3) + 2
       = 3 * calculate(2 + 4 * 3) + 2
       = 3 * 14 + 2
       即我们可以将括号内的字符串当作一个运算式，再递归调用本函数，最终返回一个数值
     */
     return dfs(s);
 }

 private int dfs(String s) {
     Deque<Integer> stack = new LinkedList<>();

     //记录某个连续的数，比如 "42"，那么我们首先 num = 4，然后遇到 2 ,num = num * 10 + 2 = 42
     int num = 0;
     char op = '+';
     for (; i < s.length(); i++) {
         char ch = s.charAt(i);

         //遇到左括号，递归运算内部子式
         if (ch == '(') {
             ++i;
             num = dfs(s);
         }

         if (Character.isDigit(ch)) {
             num = num * 10 + (ch - '0');
         }
         //不是数字，不是空格（运算符 或 '(' 或 ')' ） 或者 到了最后一个字符，那么根据前面记录的 op 操作符 将数字压栈，然后将新的运算符 ch 赋值给 op
         if (!Character.isDigit(ch) && ch != ' ' || i == s.length() - 1) {
             switch (op) {
                 case '+':
                     stack.push(num);
                     break;
                 case '-':
                     stack.push(-num);
                     break;
                 case '*':
                     int pre = stack.pop();
                     stack.push(pre * num);
                     break;
                 case '/':
                     pre = stack.pop();
                     stack.push(pre / num);
                     break;
             }
             num = 0;
             op = ch;
         }
         /*
         遇到右括号，退出循环，然后计算结果， 返回上一层 dfs
         这一步写在最后是因为，当 ch 为 右括号 时，那么我们需要先将前面已经得到的 num 压入栈中，再退出循环
         */
         if (ch == ')') {
             break;
         }
     }
     int res = 0;
     while (!stack.isEmpty()) {
         res += stack.pop();
     }
     return res;
 }