[LeetCode] 224. 基本计算器

[Animenzzzz]

题目描述：

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。

示例 1:

输入: "1 + 1"
输出: 2

示例 2:

输入: " 2-1 + 2 "
输出: 3

示例 3:

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

解题思路：首先分两个栈，一个栈存操作符(ss)：减、加、左括号，另一栈存数字(nums)。
大概思路：每次计算一对括号之后，将结果重新存进nums中，最后再对nums进行操作。
详细步骤：当遇到右括号时，说明要开始计算了：使用一个中间变量result，需要注意的情况：因为加减，参与加减的是两个数，而操作符是一个，所以当最后一次加减的时候，ss的栈顶是左括号时，要再进行一次操作，nums多出栈一次，最后这一对括号计算完成，讲结果存进nums

C++解题：

class Solution {
public:
    int calculate(string s) { 
        stack<char> ss;
        stack<int> nums;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == ')')
            {
                int result = 0;
                if(ss.top() == '('){//这个情况说明，括号里面只有一个数，如1+(5)
                    ss.pop();
                    continue;
                }
                while (!ss.empty() && ss.top() != '(')
                {
                    if(ss.top() == '-'){
                        result = result - nums.top();
                    }else{
                        result = result + nums.top();
                    }
                    if(!nums.empty()) nums.pop();
                    if(!ss.empty()){
                        ss.pop();
                    } 
                    if(ss.top() == '('){
                        if(!nums.empty()){
                            result = result + nums.top();
                            nums.pop();
                        }
                    }
                }
                nums.push(result);
                if(ss.top() == '(') ss.pop();
            }else if(s[i] >= '0' && s[i] <= '9'){
                int num = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    num = num*10 + (s[i] - 48);
                    i++;
                }
                i--;
                nums.push(num);
            }else if(s[i] != ' ' && s[i] != ')'){
                ss.push(s[i]);
            }
        }
        int result = 0;
        while(!ss.empty() || !nums.empty()){
            if(!ss.empty() && ss.top() == '-'){
                result = result-nums.top();
            }else{
                if(!nums.empty()){
                    result = result + nums.top();
                }
            }
            if(!nums.empty()) nums.pop();
            if(!ss.empty()) ss.pop();
        }
        return result;
    }
};