https://leetcode.com/problems/basic-calculator/?tab=Description
不容易写的一道题。由于没有乘除,所以关键点就在于如何去括号,因为去完所有括号就可以挨个相加了。去括号的要点在于弄清括号内的每一个加数的正负号,比如-(2-3)
,2的符号是-
,3的符号是+
,就是说,如果要序列化做加法,一个加数的符号由以下两个因素决定:
- 该加数本身的符号
- 该加数所在最内层括号的符号
- 加数本身的符号很容易获取,因为在扫描的过程中就可以实时得到
- 加数所在最内层括号的符号则需要保存起来,由于括号是层层镶嵌的,所以栈是合适的数据结构
- 当遇到
(
时,就把新一层符号压栈,它可以通过当前层的符号(也就是实时获取的符号)与前一层符号(栈顶)计算得到,计算方法是“相同为正,相异为负” - 当遇到
)
,表示一层符号处理完,pop一个栈顶元素
Time complexity: O(n)
Space complexity: O(n)
基本操作:去除字符串中所有空格,将字符串转换为整数
class Solution {
public:int calculate(string s) {if (s.empty()) return 0;// remove all the blanks in the strings.erase(std::remove(s.begin(), s.end(), ' '), s.end());stack<int> stk;stk.push(1); // assume there this a `()` outside the stringint ret = 0, sign = 1, i = 0;while (i < s.size()) {char c = s[i];if (c == '+') {sign = 1; i++;} else if (c == '-') {sign = -1; i++;} else if (c == '(') {stk.push(sign * stk.top()); i++;sign = 1; // remember to reset the sign} else if (c == ')') {stk.pop(); i++;} else {int num = 0;while (i < s.size() && isdigit(s[i])) {num = num * 10 + (s[i] - '0');i++;}ret += sign * num * stk.top();}}return ret;}
};