【Leetcode】224. Basic Calculator（计算等式问题：只包含括号与加减）（stack）

￡神魔★判官ぃ 2022-04-25 09:00 184阅读 0赞

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open `(` and closing parentheses `)`, the plus `+` or minus sign `-`, **non-negative**integers and empty spaces .

**Example 1:**

Input: "1 + 1"
    Output: 2

**Example 2:**

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

**Example 3:**

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

**Note:**

*  You may assume that the given expression is always valid.
 *  **Do not** use the `eval` built-in library function.

题目大意：

计算只包含括号+-的算式。

解题思路：

利用栈，将（）中的作为一个新的算式对待，保持前面的计算结果和计算状态（-1,1）。当遍历到）时，计算当前（）外面一层的结果。

class Solution {
    private:
        int ans = 0;
        stack<int> nums_state;
        
    public:
        int calculate(string s) {
            int len_n = s.length();
            if(len_n == 0) return 0;
            int cor_state = 1;
            int val = 0;
            for(int i=0;i<len_n;i++){
                
                if(s[i]>='0'&&s[i]<='9'){
                    val = (val*10 + (s[i]-'0'));
                }
                if(s[i]=='+' || s[i]=='-'){
                    ans += (val*cor_state);   
                    val = 0;
                    cor_state = s[i]=='+'?1:-1;
                }
                
                if(s[i]=='('){
                    nums_state.push(ans);
                    nums_state.push(cor_state);
                    ans = 0;
                    val = 0;
                    cor_state = 1;
                }
                
                if(s[i]==')'){
                    ans += val*cor_state;
                    cor_state = nums_state.top();
                    nums_state.pop();
                    val = ans;
                    ans = nums_state.top();
                    nums_state.pop();
                    
                    ans += val*cor_state;
                    val = 0;
                }
                
                
            }
            ans += (val*cor_state);
            return ans;
        }
    };