Sharing two clean C++ solutions: iterative with stack (13ms) and recursive (16ms)


  • 0
    C

    Iterative approach:

    Basic idea is to keep a stack of expressions, each expression contains left operand and operator. And we keep a "num" as our right operand.

    If we meet a "(" we push stack.
    If we meet a ")" we compute and pop stack, assign computed value to num.
    If we meet a "+" or "-" we need to compute top of the stack and update the operand.
    After we are done with the string, we need to check if there's a right operand remaining, if yes, we compute the last one.

        struct Expr {
            int left;
            int op;
            Expr() : left(0), op(1) {}
            int compute(int right) { 
                left = left + op * right;
                return left;
            }
        };
        int calculate(string s) {
            /* using stack */
            vector<Expr> history;
            history.push_back(Expr());
            int num = 0;
            bool hasNum = false;
            for (int i=0; i<s.size(); i++) {
                char c = s[i];
                if (c == ' ') continue;
                if (c == '(') {
                    history.push_back(Expr());
                } else if (c == ')') {
                    num = history.back().compute(num);
                    history.pop_back();
                } else if (c == '+' || c == '-') {
                    int value = history.back().compute(num);
                    history.back().op = c == '+' ? 1 : -1;
                    num = 0;
                    hasNum = false;
                } else {
                    num = num * 10 + c - '0';
                    hasNum = true;
                }
            }
            
            if (hasNum) num = history.back().compute(num);
            return num;
        }
    

    The recursive approach:
    If we meet a "(" we call recursion and when we meet a ")" we return computed value and next position to upper level.
    At each level, if there's no "(" and ")" we compute like we do in the iterative approach.

        int calculate(string s) {
            int nextPos = 0;
            return calculateSub(s, 0, nextPos);
        }
        
        int calculateSub(const string& s, int pos, int& nextPos) {
            int sum = 0;
            int num = 0;
            int sign = 1;
            for (int i=pos; i<s.size(); i++) {
                if (s[i] == ' ') {
                    continue;
                } else if (s[i] == '(') {
                    int nextPos = i+1;
                    sum += sign * calculateSub(s, i+1, nextPos);
                    i = nextPos;
                } else if (s[i] == ')') {
                    sum += sign * num;
                    nextPos = i;
                    return sum;
                } else if (isNum(s[i])) {
                    num = num * 10 + s[i] - '0';
                } else {
                    sum += sign * num;
                    num = 0;
                    sign = s[i] == '+' ? 1 : -1;
                }
            }
            
            sum += sign * num;
            
            return sum;
        }
        
        inline bool isNum(char c) {
            return c <= '9' && c >= '0';
        }
    

Log in to reply
 

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