题解 | #四则运算#

分享一下做题思路吧，很久之前做过类似的，花了很长时间才写出来。

发现很多题目还有很多漏洞，光是测试用例覆盖不了，因此我有时会根据测试用例写代码。不知道考试状态可不可以看到。

总体思路是 先算括号内的，再算* / ，再算+- 。那么怎么来区分呢 。我用了递归和栈

对于加号 直接压入栈中，对于－号，如果是运算符，我就把被减数*（-1）压入栈中，最后直接把所有结果弹出来相加。

对于× /号，我就直接运算完再放入栈中。

对于括号 就我再次递归调用，新起一个栈去计算，将结果返回压入到原来的栈中。

这样下来站内留下来的都是加法，最后运算即可。

我是倒着写入栈内的，其实顺着逻辑一样，

需要注意的地方：

    区分 减号是运算符还是正负号

    遇到* 和除号需要运算是，因为我们倒叙只是读取到了*号后面的数，前面的数字我们还没有读取到。

    因此就需要我们读取完成后面的数字之后才能运算。因此 用了一个标识位来表示上次遇到的符号。下次再遇到符号时，就把上次的符号对比是什么符号 从栈中取出两个值进行计算。将结果放入栈中。再把这次的符号复制给标识位。

    

    因为+号是最后处理，所以遇到标识位为加号时，只会将当前符号赋值给标识位。我们就可以默认给标识位一个+号（这很重要），因为其它符号会从栈中取出两个元素。而最开始的时候我们的栈内只有一个元素，其它符号就报错了。

    最后需要注意的是  我们循环计算完之后，往往我们的标识位还保留了一个符号，可能是 * / 就需要我们在循环外，再判断一下符号，将栈口的两个元素计算。  

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            char[] a = in.nextLine().
                       replace("{", "(").
                       replace("[", "(").
                       replace("}", ")").
                       replace("]", ")").
                       toCharArray();
            int res = 0;
            System.out.println( faction(a, a.length - 1)[0] );
        }
    }

    public static int[] faction(char[] a, int index) {
        Stack<Integer> stack = new Stack<Integer>();
        char sgin = '+';
        for (int i = index ; i >= 0 ; i--) {
// 判断是否是数字
            if ( Character.isDigit(a[i]) ) {
                int num = a[i] - '0';
                i--;
                int j = 10;
                while ( i >= 0 && Character.isDigit(a[i]) ) {
                    num = (a[i] - '0') * j + num;
                    j *= 10;
                    i--;
                }
                stack.add(num);
            }
            //当判断完数字之后，因为计算数字时操作了i指针已经指向了不是数字的符号
//             因此if执行完和开启新一轮循环一样 下面的情况都需要判断一下，也可能出了界限，因此需要判断一下。
            if (i < 0) {
                break;
            }
//             这里在计算结束之后，进行了continue 终止了这次操作，因为我们的方法给我们返回了左括号的下标，如果继续下去，我们的左括号又要当做外层的左括号去匹配，因此我们需要终止这次循环
            if (a[i] == ')') {
                i--;
                int[] d = faction(a, i);
                stack.push(d[0]);
                i = d[1];
                continue;
            }
//            判断到这里 不是符号就是左括号了，因此我们需要判断符号是正负号 是的话将栈口的值改为负号进行下一轮 
//             不是正负号就是左括号和运算符了，因为 即便是遇到了左括号，我们也需要把标识位的值计算了，再向加，
//             因此我们直接执行放到esle中执行，然后再判断是否是左括号
            if (i - 1 >= 0 && !Character.isDigit( a[i - 1] ) && a[i] == '-'  ) {
                stack.add( stack.pop() * (-1) );
            } else {
                if (sgin == '*') {
                    sgin = a[i];
                    stack.push(stack.pop() * stack.pop());
                } else if (sgin == '/') {
                    sgin = a[i];
                    stack.push(stack.pop() / stack.pop());
                } else if (sgin == '-') {
                    sgin = a[i];
                    int temp = stack.pop();
                    stack.push( stack.pop() * (-1));
                    stack.push(temp);

                } else {
                    sgin = a[i];
                }

            // 判断是否是左括号
                if (a[i] == '(') {
                    while (stack.size() > 1) {
                        stack.push(stack.pop() + stack.pop());
                    }
                    return new int[] {stack.pop(), i};
                }
            }

        }

        if (a[0] == '-' ) {
            stack.add( stack.pop() * (-1) );
        }
        if (sgin == '*') {
            stack.push(stack.pop() * stack.pop());
        } else if (sgin == '/') {
            stack.push(stack.pop() / stack.pop());
        } else if (sgin == '-') {
            int temp = stack.pop();
            stack.push( stack.pop() * (-1));
            stack.push(temp);
        }
        while (stack.size() > 1) {
            stack.push(stack.pop() + stack.pop());
        }
        return new int[] {stack.pop(), 0};
    }
}