Leetcode高级挑战：简单计算器

《简单计算器》在Leetcode中难度为hard，看起来很简单，里面涉及很多状态记录和汇总，真正做出来还是花了一些时间

1，问题

原题链接 https://leetcode.com/problems/basic-calculator/description/

• 实现一个计算器来计算一个简单表达式。表达式中可以包含，左括号，右括号，加号，减号，数字或者空格

例1

Input: "1 + 1"
Output: 2

例2

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

例3

Input: "(3-(2-(5-(9-(4)))))"
Output: 1

2，分析

1. 看到问题我首先想到递归，依次深入，最后从最小的计算单位算起。思路没问题，但效率肯定不高。
2. 如果要效率最高，最好的算法一定是只经过一次遍历就可以得出结果，所以我开始从这个思路下手。
3. 这个问题可以分解为对每个数字进行加减法，没有括号的情况很简单。
4. 有括号的情况，特别是嵌套的时候，括号里的数字应该做加法还是减法，需要考虑之前的操作符号。
5. 比如例3中 "(3-(2-(5-(9-(4)))))"， 数字5， 因为前面2个括号前都是负号，所以对数字5应该做加法

3，算法

• 初始化，默认最近的计算符为加号

• 遍历表达式中的字符

  • 如果字符为数字，获取整个数字串转化为数字
    • 根据最近的计算符累加
  • 如果字符为：左括号
    • 括号前的操作符入栈
    • 计算出栈中所有操作符累计结果
    • 设置最近的计算符为加号
  • 如果字符为：加号
    • 设置最近的计算符为加号
  • 如果字符为：减号
    • 设置最近的计算符为负号
  • 如果字符为：右括号
    • 设置最近的计算符为加号
    • 括号前的操作符出栈

• 返回最终结果

4，完整代码

public int calculate(String s) {
        // 以下使用boolean类型来表示加加法，true为加法，false为减法
        boolean operArr[] = new boolean[s.length()];
        boolean finalOperInArr = true;
        int operOff = 0;

        int ret = 0;
        boolean lastOperPlus = true;

        for(int i=0; i<s.length(); i ++){
            if (Character.isDigit(s.charAt(i))) {
                // 获得整个数字
                int sum = s.charAt(i) - '0';
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    sum = sum * 10 + s.charAt(i + 1) - '0';
                    i++;
                }

                // 根据最近的操作符累加
                if(lastOperPlus == finalOperInArr)
                    ret += sum;
                else
                    ret -= sum;
            }

            if(s.charAt(i)=='('){
                // 操作符入栈
                operArr[operOff++] = lastOperPlus;
                finalOperInArr = finalOperInArr == lastOperPlus;
                lastOperPlus = true;
            }else if(s.charAt(i) == '+'){
                lastOperPlus = true;
            }else if(s.charAt(i) == '-') {
                lastOperPlus = false;
            }else if(s.charAt(i)==')'){
                lastOperPlus = true;
                // 操作符出栈
                finalOperInArr = finalOperInArr == operArr[--operOff];
            }
        }

        return ret;
    }