224. 基本计算器

山不辞土，故能成其高；海不辞水，故能成其深！

参考224. 基本计算器。

题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

输入：s = " 2-1 + 2 "
输出：3
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

解题思路

• 枚举去除括号：枚举时入栈,直到碰到右括号,运算到栈顶的左括号,最后计算一次。
• 括号展开：对左括号前面的符号入栈,右括号时出栈,因为只有+-,可以对括号里面的数进行最终的符号确定。

枚举去除括号

class Solution {
    public int calculate(String s) {
        //考虑栈 因为没有乘除只需要考虑括号先执行
        StringBuilder ans = new StringBuilder();
        for(char c : s.toCharArray()) {
            if(c == ' ') continue;
            if(c == ')') { //右括号开始计算到栈顶的左括号
                int index = ans.lastIndexOf("(");
                int res = eval(ans.substring(index+1));
                ans.delete(ans.lastIndexOf("("),ans.length());//左括号出栈
                ans.append(String.valueOf(res));//结果入栈
            }else {
                ans.append(c);
            }
        }
        return eval(ans.toString());
    }
    //计算不含括号的+/- 主要注意多位数字的计算
    public int eval(String s) {
        char lastCalc = '+',lastChar = 0;
        int res = 0,lastNum = 0;
        for(char c : s.toCharArray()) {
            if(c == '+' || c == '-'){
                if(lastCalc == '+') res += lastNum;
                else res -= lastNum;
                lastNum = 0;
                if(lastChar == c) lastCalc = '+';//简化判断 lastChar == '-' && c == '-'
                //else if(lastChar == '-' && c == '+')lastCalc = '-';//不合法
                else lastCalc = c;
            }else {
                lastNum = lastNum*10 + (c-'0');
            }
            lastChar = c;
        }
        return res + (lastCalc == '+'?lastNum : -lastNum);
    }
}

复杂度分析

• 时间复杂度：O(n)，n为表达式字符串长度,最坏的情况下字符串会被访问两次耗时2n。
• 空间复杂度：O(n)，中间使用空间不超过n。

括号展开

class Solution {
    public int calculate(String s) {
        Deque<Integer> st = new ArrayDeque<Integer>(); // 存储正负号
        int ans = 0, num = 0, op = 1;//符号可用op或sign表示
        st.push(op);
        for (char c : s.toCharArray()) {
            if (c == ' ') continue;
            else if (c >= '0' && c <= '9') num = num * 10 + (c - '0');
            else {
                ans += op * num;
                num = 0; //重置上次记录

                if (c == '+') op = st.peek();
                else if (c == '-') op = -st.peek();
                else if (c == '(') st.push(op); // 将括号前符号放入栈顶
                else st.pop();//')'
            }
        }
        return ans + op * num;
    }
}

复杂度分析

• 时间复杂度：O(n)，一重循环遍历。
• 空间复杂度：O(k)，k为左括号数量。