基本计算器

224. 基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。

示例 1：

1 2	输入：s = "1 + 1" 输出：2

示例 2：

1 2	输入：s = " 2-1 + 2 " 输出：3

示例 3：

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

提示：

1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式

方法一：栈

基本计算器只包含加减法，括号对一个数只影响其正负。以示例三为例：

数字 1 前面没有符号，记为 +1
数字 4 前面有一个 + 号，记为 +4
数字 5 和数字 2 前面有两个 + 号，记为 +5，+2
数字 3 前面有一个 + 号（不包括（4 + 5 + 2）里的 + 号）和一个 - 号，记为 -3
数字 6 前面有一个 + 号，记为 +6
数字 8 前面有两个 + 号，记为 + 8

将这些数字加起来，我们得到最终结果 23。

我们使用一个栈 ops 来记录当前位置所处的每个括号所共同形成的符号，同时使用 sign 来表示当前的符号（sign 为 1 代表正数）。

如果当前遇到了 + 号，当前符号为 ops.peek()；如果当前遇到了 - 号，当前符号为 - ops.peek()。

每当遇到 ( 时，都要将当前 sign 取值压入栈中；每当遇到）时，都从栈中弹出一个元素。

class Solution {
    public int calculate(String s) {
        Deque<Integer> ops = new LinkedList<Integer>();
        ops.push(1);
        int sign = 1;

        int ret = 0;
        int n = s.length();
        int i = 0;
        while (i < n) {
            if (s.charAt(i) == ' ') {
                i++;
            } else if (s.charAt(i) == '+') {
                sign = ops.peek();
                i++;
            } else if (s.charAt(i) == '-') {
                sign = -ops.peek();
                i++;
            } else if (s.charAt(i) == '(') {
                ops.push(sign);
                i++;
            } else if (s.charAt(i) == ')') {
                ops.pop();
                i++;
            } else {//遇到一个数，直接加入结果
                long num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                ret += sign * num;
            }
        }
        return ret;
    }
}

时间复杂度O(n)
空间复杂度O(n)