Basic Calculator II

Description

https://leetcode.com/problems/basic-calculator-ii/description/

Solution

class Solution {
public:
    int calculate(string s) {
        int ret = 0;
        bool shallow = true;
        this->calculateFromIndex(s, 0, ret, shallow);
        return ret;
    }
    
    int calculateFromIndex(string& s, int index, int& ret, bool shallow) {
        int number = 0;
        while(index < s.size()) {
            while(index < s.size() && s[index] == ' ') index += 1;
            if (index == s.size()) return -1;
            
            if (s[index] >= '0' && s[index] <= '9')
                index = this->extractNumber(s, index, ret);
            else {
                //Check the operator's priority
                char currentOp = s[index];
                index += 1;
                while(s[index] == ' ') index += 1;
                int numberIndex = index;
                index = this->extractNumber(s, index, number);
                while(index < s.size() && s[index] == ' ') index += 1;
                if (index >= s.size()) {
                    ret = this->operate(ret, number, currentOp);
                    return index;
                }
                char nextOp = s[index];
                int sign = this->check(currentOp, nextOp);
                int nested = 0;
                switch (sign) {
                    case -1:
                        index = this->calculateFromIndex(s, numberIndex, nested, false);
                        ret = this->operate(ret, nested, currentOp);
                        break;
                    case 1:
                        ret = this->operate(ret, number, currentOp);
                        break;
                    case 0:
                        ret = this->operate(ret, number, currentOp);
                        if (shallow)
                            break;
                        else
                            return index;
                }   
            } 
        }
        return -1;
    }
    
    int operate (int left, int right, char op) {
        if (op == '+') return left + right;
        if (op == '-') return left - right;
        if (op == '*') return left * right;
        if (op == '/') return left / right;
    }
    
    int check(char left, char right) {
        if ( ( (left == '-' || left == '+') && (right == '+' || right == '-') ) || \
            ( (left == '*' || left == '/') && (right == '*' || right == '/') ) )
            return 1;
        
        if ( (left == '-' || left == '+') && (right == '/' || right == '*') )
            return -1;
            
        if ( (left == '*' || left == '/') && (right == '+' || right == '-') )
            return 0;
    }
    
    int extractNumber(string& s, int index, int& number) {
        number = 0;
        while (s[index] >= '0' && s[index] <= '9' && index < s.size()) {
            number = number * 10 + (s[index] - '0');
            index += 1;
        }
        return index;
    }
    
};

Solution2 –Unrecursive

enum Type{
    INT,
    ADD,
    SUB,
    MUL,
    DIV
};
class Solution {
public:
    Type checkType(char ch) {
        if (ch >= '0' && ch <= '9') return INT;
        if (ch == '*') return MUL;
        if (ch == '/') return DIV;
        if (ch == '+') return ADD;
        if (ch == '-') return SUB;
    }
    int calculate(string s) {
        stack<int> numberSt;
        int index = 0;
        int ret = 0;
        while(index < s.size()) {
            while(index < s.size() && s[index] == ' ') index += 1;
            if (index == s.size()) return ret;
            Type type = this->checkType(s[index]);
            if (type != INT) index += 1;
            int nextNumber = this->extractNumber(s, index);
            int top;
            switch(type) {
                case INT:
                    numberSt.push(nextNumber);
                    break;
                case MUL:
                    top = numberSt.top();
                    numberSt.pop();
                    numberSt.push(top * nextNumber);
                    break;
                case DIV:
                    top = numberSt.top();
                    numberSt.pop();
                    numberSt.push(top / nextNumber);
                    break;
                case ADD:
                    numberSt.push(nextNumber);
                    break;
                case SUB:
                    numberSt.push(-nextNumber);
                    break;
            }
        }
        while(numberSt.size() >= 2) {
            int right = numberSt.top();
            numberSt.pop();
            int left = numberSt.top();
            numberSt.pop();
            numberSt.push(left + right);
        }
        return numberSt.top();
    }
    
    int extractNumber(string& s, int& index) {
        while(index < s.size() && s[index] == ' ') index += 1;
        int ret = 0;
        while (index < s.size() 
               && s[index] <= '9'
               && s[index] >= '0') {
            ret  = ret * 10 + (s[index] - '0');
            index += 1;
        }
        while(index < s.size() && s[index] == ' ') index += 1;
        return ret;
    }
};