[C++] - Clean Code - Iterative & Recursion


  • 2

    Iterative Solution using stack

    /**
     * 1. update result - end of number; end of ')'
     *    res += sign * num;
     * 2. every operand num have a sign;
     * 3. push temp result & sign on stack - begin of another "("
     */
    
    class Solution {
    public:
        int calculate(string s) {
            stack<tuple<int, int>> stk;
            int res = 0;
            int sign = 1;
            for (int i = 0; i < s.length(); i++) {
                if (isdigit(s[i])) {
                    int start = i;
                    while (isdigit(s[i + 1])) { i++; }
                    res += sign * stoi(s.substr(start, i + 1 - start));
                }
                else {
                    if (s[i] == '+') {
                        sign = 1;
                    }
                    else if (s[i] == '-') {
                        sign = -1;
                    }
                    else if (s[i] == '(') {
                        stk.push(tuple<int, int>(sign, res));
                        sign = 1;
                        res = 0;
                    }
                    else if (s[i] == ')') {
                        res = res * get<0>(stk.top()) + get<1>(stk.top());
                        stk.pop();
                    }
                }
            }
            return res;
        }
    };
    

    StackFrame

    class Solution {
    public:
        int calculate(string s) {
            stack<StackFrame> stk;
            int res = 0;
            int sign = 1;
            for (int i = 0; i < s.length(); i++) {
                if (s[i] == '+') {
                    sign = 1;
                }
                else if (s[i] == '-') {
                    sign = -1;
                }
                else if (isdigit(s[i])) {
                    int start = i;
                    while (i + 1 < s.length() && isdigit(s[i + 1])) { i++; }
                    res += sign * stoi(s.substr(start, i + 1 - start));
                }
                else if (s[i] == '(') {
                    stk.push(StackFrame(res, sign));
                    res = 0;
                    sign = 1;
                }
                else if (s[i] == ')') {
                    res = stk.top().base + stk.top().sign * res;
                    stk.pop();
                }
            }
    
            return res;
        }
    
    private:
        struct StackFrame {
            int base;
            int sign;
            StackFrame(int base, int sign) : base(base), sign(sign) {};
        };
    };
    

    Recursion Solution

    class Solution {
    public:
        int calculate(string s) {
            int i = 0;
            return calculate(s, i);
        }
    
    private:
        int calculate(string& s, int& i) {
            int res = 0;
            int sign = 1;
            for (; i < s.length(); i++) {
                if (isdigit(s[i])) {
                    int start = i;
                    while (i + 1 < s.length() && isdigit(s[i + 1])) { i++; }
                    res += sign * stoi(s.substr(start, i + 1 - start));
                }
                else if (s[i] == '(') {
                    res += sign * calculate(s, ++i);
                }
                else if (s[i] == ')') {
                    return res;
                }
                else if (s[i] == '+') {
                    sign = 1;
                }
                else if (s[i] == '-') {
                    sign = -1;
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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