leetcode 224. Basic Calculator

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 .

You may assume that the given expression is always valid.

Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

可能之前做过类似的题目，一直觉得一个符号栈，一个数字栈就能搞定，所以一直用栈去模拟，倪马啊....是我不够熟练

我用了2个vector2个栈最后终于搞定了....看了看其他人的代码，真是简便啊。

一开始没有考虑好这种情况的出现3-(3-(1+1)) 导致两个vector的时候不能处理括号嵌括号的情况,后来又加上两个临时的stack进行反转就ok了。

那我贴下我的代码吧，都是时间啊

class Solution {
public:
    
    int calculate(string s) {
        vector<int> a;
        vector<char> b;
        int num = 0, mark = 0;
        string t = "";
        for (int i = 0; i < s.size(); ++i) {
            while (i < s.size() && s[i] >= '0' && s[i] <= '9') {
                t += s[i];
                ++i;
                mark = 1;
            }
            if (mark) {
                //cout << "s " << t << endl;
                a.push_back(stoi(t));
                t = "";
                mark = 0;
            }
            if (s[i] == '+') b.push_back(s[i]);
            if (s[i] == '-') b.push_back(s[i]);
            if (s[i] == '(') b.push_back(s[i]);
            if (s[i] == ')')  {
                stack <int> w;
                stack <char> q;
                int tot = 1;
                while (!b.empty()) {
                    char c = b.back();
                    b.pop_back();
                    if (c != '(') {
                        tot++;
                        q.push(c);
                    } else break;
                }
                while (!a.empty() && tot > 0) {
                    --tot;
                    //cout << "a " << a.back() << endl;
                    w.push(a.back()); a.pop_back();
                }
                //if (!w.empty()) w.push(a.back()),a.pop_back();
                while (!q.empty()) {
                    int x = w.top(); w.pop();
                    int y = w.top(); w.pop();
                    char c = q.top();q.pop();
                    if (c == '+') w.push(x+y);
                    else w.push(x-y);
                }
                a.push_back(w.top());
                w.pop();
            }
        }
        int j = 0;
        int ans = 0;
        if (a.size()) ans = a[0];
        for (int i = 1; i < a.size(); ++i) {
            if (b[j] == '-') {
                ans -= a[i];
            } else {
                ans += a[i];
            }
            ++j;
            cout << "ans " <<ans <<endl;
        }
        return ans;
    }
};

好长...

这里再贴一个他人的优秀的代码。
遇到 '(' 就把之前的结果和符号push进stack. 遇到')'就把 当前结果*stack中的符号 再加上stack中之前的结果.

public class Solution {
    // "1 + 1"
    public int calculate(String s) {
        if(s==null || s.length() == 0) return 0;
        
        Stack<Integer> stack = new Stack<Integer>();
        int res = 0;
        int sign = 1;
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(Character.isDigit(c)) {
                int cur = c-'0';
                while(i+1<s.length() && Character.isDigit(s.charAt(i+1))) {
                    cur = 10*cur + s.charAt(++i) - '0';
                }
                res += sign * cur;
            } else if(c=='-') {
                sign = -1;
            } else if(c=='+') {
                sign = 1;
            } else if( c=='(') {
                stack.push(res);
                res = 0;
                stack.push(sign);
                sign = 1;
            } else if(c==')') {
                res = stack.pop() * res + stack.pop();
                sign = 1;
            }
        }
        return res;
    }
}