Clean one pass 12ms C++ O(n) & constant space solution, beating 97%


  • 2
    C

    The evaluation of the input expression can be done in O(n) with one pass since there's no brackets to elevate precedence of certain operators. Basic idea is this:

    We keep track of our current right operand and previous operator. When we meet a non-numeric char, meaning this would be a operator, we compute the previous operation with current right operand and then update the current operator and reset current operand.

    Since multiplication and division has higher precedence than addition and subtractions, we also keep track of the value of last addition/subtraction operation. This value will be used to be associated with multiplication/division because those operators have higher precedence. For example: a + b + c*d/e

    Step1: result = a + b, pvalue = b, operator = +
    Step2: result = a + b + c, pvalue = c, opeator = *
    Step3: result = a + b + c - c + c * d, pvalue = c * d, operator = /
    Step3: result = a + b + c * d - c * d + c * d / e, pvalue = c * d / e, operator = ' '

    Code:

        int calculate(string s) {
            char ops = '+';
            int result = 0;
            int pvalue = 0;
            int operand = 0;
            for (int i=0; i<s.size(); i++) {
                char c = s[i];
                if (c == ' ') continue;
                if (c <= '9' && c >= '0') {
                    operand = operand * 10 + c - '0';
                } else {
                    calculate(operand, ops, result, pvalue);
                    ops = c;
                    operand = 0;
                }
            }
            calculate(operand, ops, result, pvalue);
            return result;
        }
        
        inline void calculate(int operand, char ops, int& result, int& pvalue) {
            if (ops == '+') {
                result += operand;
                pvalue = operand;
            } else if (ops == '-') {
                result -= operand;
                pvalue = -operand;
            } else if (ops == '*') {
                result -= pvalue;
                pvalue *= operand;
                result += pvalue;
            } else if (ops == '/') {
                result -= pvalue;
                pvalue /= operand;
                result += pvalue;
            }
        }
    

Log in to reply
 

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