基本计算器

发表于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

LeetCode每日一题，224. Basic Calculator

先看题目描述

6YhLhn.png

大意就是给定个字符串代表数学运算，让我们实现一个基本计算器计算其值

算法和思路

这题看了一会，不会做，就去看题解了

栈 + 括号展开

由于字符串除了数字与括号外，只有加号和减号两种运算符。因此，如果展开表达式中所有的括号，则得到的新表达式中，数字本身不会发生变化，只是每个数字前面的符号变化

因此，考虑使用一个取值为 {-1，1} 的整数 sign 代表当前的符号，根据括号表达式性质，它的取值：

  • 与字符串中当前位置的运算符有关
  • 如果当前位置处于一系列的括号内，则也与这些括号前面的运算符有关：每当遇到一个以 - 开头的括号，则意味着此后的符号都要被翻转

我们可以维护一个栈 ops，栈顶元素记录了当前位置所处的每个括号所共同形成的符号

  • 若遇到 +，则更新 sign 为 ops.peek()
  • 若遇到 -，则更新 sigh 为 -ops.peek()
  • 若遇到 (，则将 sigh 进栈
  • 若遇到 )，则将栈顶元素弹出

算法源码

栈 + 括号展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int calculate(String s) {
        Deque<Integer> ops = new ArrayDeque<>();
        char[] cs = s.toCharArray();
        int res = 0;
        int sign = 1;
        int index = 0;
        int len = cs.length;
        ops.push(sign);
        while (index < len) {
            char c = cs[index];
            if (c==' ') {
                index++;
            } else if (c == '+') {
                sign = ops.peek();
                index++;
            } else if (c == '-') {
                sign = -ops.peek();
                index++;
            } else if (c == '(') {
                ops.push(sign);
                index++;
            } else if (c == ')') {
                ops.pop();
                index++;
            } else {
                int num = 0;
                while (index < len && Character.isDigit(cs[index])) {
                    num = num * 10 + (cs[index] - '0');
                    index++;
                }
                res += sign * num;
            }
        }
        return res;
    }
}