题目描述
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
- 遇到
(
:表示我们需要先计算括号后的结果再对当前局部和进行更新,因此将当前局部和以及符号压入一个栈中,并且重置局部和和符号用于括号内计算 - 遇到
)
:表示括号内计算已结束,将当前局部和用之前计算的方法更新到上一个局部和中,上一个局部和以及相应的操作在栈顶中
代码如下:
#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