LintCode 980 · Basic Calculator II (计算器，栈好题)

980 · Basic Calculator II
Algorithms
Medium
Description
Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . Division of integers should round off decimals.

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

Example
Example 1:

Input:
“3+2*2”
Output:
7
Example 2:

Input:
" 3/2 "
Output:
1
Tags
Company
Airbnb
Related Problems

849
Basic Calculator III
Hard

978
Basic Calculator
Medium

解法1：这题相对来说容易一点，因为没有括号。

class Solution {
public:
    /**
     * @param s: the given expression
     * @return: the result of expression
     */
    int calculate(string &s) {
        int index = 0;
        char op = '+';
        int num = 0;
        vector<int> nums;
        while (index < s.size()) {
            if (s[index] == ' ') {
                index++;
                continue;
            }
            while (isdigit(s[index])) {
                num = num * 10 + (s[index] - '0');
                index++;
            } //else { //+ - * /  注意：这里不能用else,不然s最后是数字的话就不会调用下面的代码了。
            
            switch(op) { //note: it is not switch(c) !
                case '+':
                    nums.push_back(num);
                    break;
                case '-':
                    nums.push_back(-num);
                    break;
                case '*':
                    nums.back() *= num;
                    break;
                case '/':
                    nums.back() /= num;
                    break;
            }
            op = s[index];
            num = 0; //这里要清零
            index++;
        }
        int res = 0;
        for (auto n : nums) {
            res += n;
        }
        return res;
    }
};

解法2：也可以先找到优先级最低的字符，如果有并列的，就先处理右边的。比如说”3+2-65“。先找到+号，将其分为"3"和"2-65", 然后再分别递归。

解法3：先转换成逆波兰，然后evaluate。