[LeetCode] Basic Calculator | 解析带括号的字符串加减运算表达式

https://leetcode.com/problems/basic-calculator/?tab=Description

不容易写的一道题。由于没有乘除，所以关键点就在于如何去括号，因为去完所有括号就可以挨个相加了。去括号的要点在于弄清括号内的每一个加数的正负号，比如-(2-3)，2的符号是-，3的符号是+，就是说，如果要序列化做加法，一个加数的符号由以下两个因素决定：

1. 该加数本身的符号
2. 该加数所在最内层括号的符号

• 加数本身的符号很容易获取，因为在扫描的过程中就可以实时得到
• 加数所在最内层括号的符号则需要保存起来，由于括号是层层镶嵌的，所以栈是合适的数据结构
• 当遇到(时，就把新一层符号压栈，它可以通过当前层的符号（也就是实时获取的符号）与前一层符号（栈顶）计算得到，计算方法是“相同为正，相异为负”
• 当遇到)，表示一层符号处理完，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;} };