0%

[Leetcode]224. Basic Calculator(C++)

题目描述

题目链接:224. Basic Calculator

Given a string s representing an expression, implement a basic calculator to evaluate it.

例子

例子 1

Input: s = "1 + 1"
Output: 2

例子 2

Input: s = " 2-1 + 2 "
Output: 3

例子 3

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

Follow Up

Note

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.

解题思路

如果等式中没有等号的话那就很简单,只需要按照顺序:遍历数字作为第一个操作数 —> 取操作符设定下一个数字的符号 —> 遍历数字作为第二个操作数(乘上相应符号),并且和第一个数字进行相加作为下一次操作的第一个操作数,以此类推即可。在有括号时则改变了我们的操作顺序,我们可以做以下修改:

  • 初始化一个数字 result 作为当前(局部)总和,初始化符号为 sign = 1
  • 如果遇到数字,则遍历数字然后乘上相应的符号加在局部和中
  • 遇到 '+' 或者 '-',则更新符号 sign
  • 遇到 (:表示我们需要先计算括号后的结果再对当前局部和进行更新,因此将当前局部和以及符号压入一个栈中,并且重置局部和和符号用于括号内计算
  • 遇到 ):表示括号内计算已结束,将当前局部和用之前计算的方法更新到上一个局部和中,上一个局部和以及相应的操作在栈顶中

代码如下:

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
38
39
40
41
42
43
#include <stack>
#include <string>

class Solution {
public:
int calculate(std::string s) {
std::stack<int> stk;
int result = 0;
int sign = 1;
int idx = 0;
while (idx < s.length()) {
if (std::isdigit(s[idx])) {
int num = 0;
while (idx < s.length() && std::isdigit(s[idx])) {
num *= 10;
num += (s[idx] - '0');
idx++;
}
result += sign * num;
idx--;
} else if (s[idx] == '+') {
sign = 1;
} else if (s[idx] == '-') {
sign = -1;
} else if (s[idx] == '(') {
// use the top of stack as initial result and continue
// computation
stk.push(result);
stk.push(sign);
result = 0;
sign = 1;
} else if (s[idx] == ')') {
result *= stk.top();
stk.pop();
result += stk.top();
stk.pop();
}
idx++;
}

return result;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 224.BasicCalculator.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions