C++ 20ms O(n) time complexity, O(1) space


  • 0
    Z
      class Solution {
    public:
        int parseNum(const string &s, size_t &i, size_t n) {
            int digit = 0;
            while (i < n && s[i] <= '9' && s[i] >= '0') {
                digit = digit * 10 + s[i] - '0';
                i++;
            }
            i--;
            return digit;
        }
        int calculate(string s) {
            size_t ind = 0;
            size_t n = s.size();
            if (s.size() == 0) return 0;
            for (int i = 0; i < n; i++) {
                if (s[i] != ' ') {
                    s[ind] = s[i];
                    ind++;
                }
            }
            n = ind;
            size_t i = 0;
            int sign = 1, sum = 0, prev = 0;
            while (i < n) {
                if (s[i] == ' ') {}
                else if (s[i] >= '0' && s[i] <= '9') {
                    int digit = parseNum(s, i, n);
                    prev = sign * digit;
                    sum += sign * digit;
                }
                else if (s[i] == '+') { sign = 1;}
                else if (s[i] == '-') { sign = -1;}
                else if (s[i] == '*' || s[i] == '/') {
                    char op = s[i];
                    sum -= prev;
                    i++;
                    int b = parseNum(s, i, n);
                    prev = (op == '*')? (prev * b) : (prev / b);
                    sum += prev;
                }
                ++i;
            }
            return sum;
        }
    };

Log in to reply
 

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