基本计算器

2021-03-10

224. 基本计算器

难度困难441

实现一个基本的计算器来计算一个简单的字符串表达式 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 表示一个有效的表达式

递归代替栈


class Solution {
    public int calculate(String s) {
        return calBucket(s,0)[0];
    }
    public int[] calBucket(String s,int index){
        int n=s.length();
        int sum=0;
        char last='0';
        for(int i=index;i<n;i++){
            char c=s.charAt(i);
            // 遇到数字，需要对原来的符号和数字进行清算
            if('0'<=c&&c<='9'){
                // 获取当前的数字
                int j=i;
                while(j<n&&'0'<=s.charAt(j)&&s.charAt(j)<='9')j++;
                int val=Integer.parseInt(s.substring(i,j));
                i=--j;
                // 计算最新的结果
                if(last=='+'){
                    sum+=val;
                }else if(last=='-'){
                    sum-=val;
                }else{
                    sum+=val;
                }

            }else if(s.charAt(i)=='+'){// 遇到符号,更新当前的运算符
                last='+';
            }else if(s.charAt(i)=='-'){// 遇到符号,更新当前的运算符
                last='-';
            }else if(s.charAt(i)=='('){
                // 左括号,使用递归代替栈处理
                // 返回的第一个数字是括号中处理的和,第二个数字是括号末尾的index
               int [] val = calBucket(s,i+1);
                if(last=='+'){
                    sum+=val[0];
                }else if(last=='-'){
                    sum-=val[0];
                }else{
                    sum+=val[0];
                }
                i=val[1];
            }else if(s.charAt(i)==')'){
                // 右括号,当前的递归结束标志
                return new int[]{sum,i};
            }
            index=i;
        }
        return new int []{sum,index};
    }

}

栈

我们需要维护一个栈 $\textit{ops}$，其中栈顶元素记录了当前位置所处的每个括号所「共同形成」的符号。例如，对于字符串 $\text{1+2+(3-(4+5))}$：

扫描到$ \text{1+2}$ 时，由于当前位置没有被任何括号所包含，则栈顶元素为初始值 $+1$；
扫描到 $\text{1+2+(3}$时，当前位置被一个括号所包含，该括号前面的符号为 ++ 号，因此栈顶元素依然 $+1$；
扫描到 $\text{1+2+(3-(4}$时，当前位置被两个括号所包含，分别对应着 + 号和 − 号，由于 + 号和 − 号合并的结果为 − 号，因此栈顶元素变为 $−1$。
在得到栈 $\textit{ops}$之后， $\textit{sign}$的取值就能够确定了：如果当前遇到了 + 号，则更新 $\textit{sign} \leftarrow \text{ops.top()}$；如果遇到了遇到了 − 号，则更新 $\textit{sign} \leftarrow -\text{ops.top()}$。

然后，每当遇到 (时，都要将当前的$ \textit{sign}$ 取值压入栈中；每当遇到 ) 时，都从栈中弹出一个元素。这样，我们能够在扫描字符串的时候，即时地更新 $\textit{ops}$ 中的元素。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/basic-calculator/solution/ji-ben-ji-suan-qi-by-leetcode-solution-jvir/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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) == '+') {// 如果是加号,那么当前的符号就是+1
                sign = ops.peek();
                i++;
            } else if (s.charAt(i) == '-') {// 如果是减号,那么当前的符号就是-1
                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;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/basic-calculator/solution/ji-ben-ji-suan-qi-by-leetcode-solution-jvir/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。