Iterative c++ solution


  • 0
    R

    The key idea is to keep a neg flag and a pre character.

    1. Once we have '(', if its pre is '-', we will flip neg. And we will aways push the pre of '(' into stack.
    2. Once we have ')', if the top of the stack is '-', we will flip neg. And we will always pop the top.
    3. Based on the pre sign of a number and the neg flag, to determine whether to add or subtract the number.
    int calculate(string s) {
            int ret = 0;
            bool neg = false;
            stack<char> st;
            char pre = '+';
            for (int i = 0; i < s.size(); ++i) {
                switch(s[i]) {
                    case ' ': break;
                    case '+':
                    case '-':
                        pre = s[i]; break;
                    case '(': 
                        if (pre == '-') neg = !neg;
                        st.push(pre);
                        pre = '('; break;
                    case ')':
                        if (st.top() == '-') neg = !neg;
                        st.pop(); break;
                    default:
                        int start = i;
                        while(i < s.size() && isdigit(s[i])) ++i;
                        int num = stoi(s.substr(start, i-start));
                        --i;
                        if ((pre == '-') ^ neg) ret -= num;
                        else ret += num;
                        break;
                }
            }
            return ret;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.