Leetcode 224 / Leetcode 227: basic calculatorI //II

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

算术表达式的计算， 解决方法： 用一个stack 存 数字，一个stack存 运算符，
存数字的时候要注意，如果字符串是234这类的需要将str->int；
存运算符的时候要注意， 由于有 +/-/(/)的存在，要对（， ）进行特殊的处理，如果是‘（’，那么可以直接入栈，如果是 +/-/)，并且top不是（,那么就可以先对stack里面的运算符进行处理，把结果计算出来之后再将当前字符入栈,
这种解决方法关键点是， 只有遇到了下一个运算符的时候才计算栈里面的运算符，其实这样做的目的是为了处理运算符优先级的问题， 如果运算符里有 +、-、*、/的时候，只有当top() >> current op的时候才会先把优先级高的，即把栈里面的运算符处理完再将当前的op入栈， 如果发现top() << current op的时候，说明此时current op优先级高，那么把current op入栈， 这样的话，下次计算会先计算优先级高的current op。 这个思想在calculator II里面有体现。 

这个问题里面由于是碰到第二个操作符才进行第一次运算，所以我们需要考虑string的 ‘\0’最后那个字符来作为结束标志进行最后一次运算。

class Solution {
private:
    int calc(int i, int j, char c) {
        int rst = 0;
        switch(c) {
            case '+': return i+j;
            case '-': return i-j;
        }
        return rst;
    }
public:
//stk_opt : ( : push, ) : cal to (, +/- : cal
//stk_val
    int calculate(string s) {
        stack<int> stk_val;
        stack<char> stk_opt;
        int rst = 0;
        for (int i = 0; i <= s.size(); i++) {
           //case 1: store int to s
           if (i < s.size() && isdigit(s[i])) {
               rst = 0;
               while (i < s.size() && isdigit(s[i])) {
                   rst *= 10;
                   rst += s[i]-'0';
                   i++;
               }
               stk_val.push(rst);
           }
            int tmp = 0;
            //case 2: store char into s
            if (i == s.size() || s[i] == '+' || s[i] == '-' || s[i] == ')') {
                while (!stk_opt.empty() && stk_opt.top() != '(') {
                    tmp = stk_val.top();
                    stk_val.pop();
                    stk_val.top() = calc(stk_val.top(), tmp, stk_opt.top());
                    stk_opt.pop();
                }
                if (i == s.size()) break;
                else if (s[i] == ')') stk_opt.pop();
                else stk_opt.push(s[i]);
            } else if (s[i] == '('){
                stk_opt.push(s[i]);
            }
        }
        return stk_val.top();
    }
};

calculator II

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

与calculator I 不同的地方在于， 需要考虑 运算符之间的优先级，再进行运算之前先比较优先级的高低再运算， 而且这个题目 省去了（）的设置，使得题目简化了。

 class Solution {
private:
    int cal(int v1, int v2, char opt) {
        switch (opt) {
            case '+': return v1+v2;
            case '-': return v1-v2;
            case '*': return v1*v2;
            case '/': return v1/v2;
        }
        return -1;
    }
    bool isOK(char opt1, char opt2) {
        //opt1 >> opt2
        if (opt1 == '*' || opt1 == '/') return true;
        else return (opt2 == '+' || opt2 == '-');
    }
public:
    int calculate(string s) {
        //sanity check
        if (s.size() == 0) return 0;
        stack<int> stk_val;
        stack<char> stk_opt;
        for (int i = 0; i <= s.size(); i++) {
            //push val into stck_val
            if (isdigit(s[i])) {
                int rst = 0;
                while (i < s.size() && isdigit(s[i])) {
                    rst *= 10;
                    rst += s[i++]-'0';
                }
                stk_val.push(rst);
            }
            //push opt into stk_opt
            if (i == s.size() || (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')) {
               while (!stk_opt.empty() && (i == s.size() || isOK(stk_opt.top(), s[i]))) {
                    int tmp = stk_val.top();
                    stk_val.pop();
                    stk_val.top() = cal( stk_val.top(),tmp,stk_opt.top());
                    stk_opt.pop();
                }
                if ( i == s.size()) break;
                stk_opt.push(s[i]);
            }
        }
        return stk_val.top();
    }
};

下面的代码是当将 +、-、*、/、（、）还有空格全部考虑进去，假设数字都是非负的情况下的处理过程，其实是将上面的两个代码进行结合的结果：

class Solution {
private:
    bool isOK(char op1, char op2) {
        if (op1 == '*' || op1 == '/' || op2 == ')') return true;
        else return op2 == '+' || op2 == '-';
    }
    int calc(int a, int b, char op) {
        if (op == '+') return a + b;
        else if (op == '-') return a - b;
        else if (op == '*') return a * b;
        else return a / b;
    }
public:
    int calculate(string s) {
        stack<int> stk_val;
        stack<char> stk_op;
        int res = 0, tmp;
        for (int i = 0; i <= s.length(); ++i) {
            //操作数
            if (i < s.length() && isdigit(s[i])) {
                res = 0;
                while (i < s.length() && isdigit(s[i])) {
                    res *= 10;
                    res += s[i++] - '0';
                }
                stk_val.push(res);
            }
            //运算符
            if (i == s.length() || s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == ')') {
                while (!stk_op.empty() && stk_op.top() != '(' && (i == s.length() || isOK(stk_op.top(), s[i]))) {
                    tmp = stk_val.top();
                    stk_val.pop();
                    stk_val.top() = calc(stk_val.top(), tmp, stk_op.top());
                    stk_op.pop();
                }
                if (i == s.length()) break;
                else if (s[i] == ')') stk_op.pop();
                else stk_op.push(s[i]);
            } else if (s[i] == '(') {
                stk_op.push(s[i]);
            }
        }
        return stk_val.top();
    }
};