[LeetCode] Basic Calculator II 基本计算器之二

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negativeintegers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"

Output: 7

Example 2:

Input: " 3/2 "

Output: 1

Example 3:

Input: " 3+5 / 2 "

Output: 5

Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

这道题是之前那道 Basic Calculator 的拓展，不同之处在于那道题的计算符号只有加和减，而这题加上了乘除，那么就牵扯到了运算优先级的问题，好在这道题去掉了括号，还适当的降低了难度，估计再出一道的话就该加上括号了。不管那么多，这道题先按木有有括号来处理，由于存在运算优先级，我们采取的措施是使用一个栈保存数字，如果该数字之前的符号是加或减，那么把当前数字压入栈中，注意如果是减号，则加入当前数字的相反数，因为减法相当于加上一个相反数。如果之前的符号是乘或除，那么从栈顶取出一个数字和当前数字进行乘或除的运算，再把结果压入栈中，那么完成一遍遍历后，所有的乘或除都运算完了，再把栈中所有的数字都加起来就是最终结果了，参见代码如下：

解法一：

class Solution {

public:

    int calculate(string s) {

        long res = , num = , n = s.size();

        char op = '+';

        stack<int> st;

        for (int i = ; i < n; ++i) {

            if (s[i] >= '') {

                num = num *  + s[i] - '';

            }

            if ((s[i] < '' && s[i] != ' ') || i == n - ) {

                if (op == '+') st.push(num);

                if (op == '-') st.push(-num);

                if (op == '*' || op == '/') {

                    int tmp = (op == '*') ? st.top() * num : st.top() / num;

                    st.pop();

                    st.push(tmp);

                }

                op = s[i];

                num = ;

            }

        }

        while (!st.empty()) {

            res += st.top();

            st.pop();

        }

        return res;

    }

};

在做了 Basic Calculator III 之后，再反过头来看这道题，发现只要将处理括号的部分去掉直接就可以在这道题上使用，参见代码如下：

解法二：

class Solution {

public:

    int calculate(string s) {

        long res = , curRes = , num = , n = s.size();

        char op = '+';

        for (int i = ; i < n; ++i) {

            char c = s[i];

            if (c >= '' && c <= '') {

                num = num *  + c - '';

            }

            if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - ) {

                switch (op) {

                    case '+': curRes += num; break;

                    case '-': curRes -= num; break;

                    case '*': curRes *= num; break;

                    case '/': curRes /= num; break;

                }

                if (c == '+' || c == '-' || i == n - ) {

                    res += curRes;

                    curRes = ;

                }

                op = c;

                num = ;

            }

        }

        return res;

    }

};