LeetCode-227. Basic Calculator II [C++][Java]

LeetCode-227. Basic Calculator II https://leetcode.com/problems/basic-calculator-ii/

Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

Constraints:

• 1 <= s.length <= 3 * 10^5
• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
• s represents a valid expression.
• All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
• The answer is guaranteed to fit in a 32-bit integer.

class Solution {
public:
    int calculate(string s) {
        int i = 0;
        return parseExpr(s, i);
    }

    // 辅函数- 递归parse从位置i开始的剩余字符串
    int parseExpr(const string& s, int& i) {
        char op = '+';
        long left = 0, right = 0;
        while (i < s.length()) {
            if (s[i] != ' ') {
                long n = parseNum(s, i);
                switch (op) {
                    case '+' : left += right; right = n; break;
                    case '-' : left += right; right = -n; break;
                    case '*' : right *= n; break;
                    case '/' : right /= n; break;
                }
                if (i < s.length()) {op = s[i];}
            }
            ++i;
        }
        return left + right;
    }

    // 辅函数- parse从位置i开始的一个数字
    long parseNum(const string& s, int& i) {
        long n = 0;
        while (i < s.length() && isdigit(s[i])) {
            n = 10 * n + (s[i++] - '0');
        }
        return n;
    }
};

class Solution {
    public int calculate(String s) {
        int i = 0;
        return parseExpr(s, i);
    }

    // 辅函数- 递归parse从位置i开始的剩余字符串
    int parseExpr(String s, int i) {
        char op = '+';
        long left = 0, right = 0;
        while (i < s.length()) {
            if (s.charAt(i) != ' ') {
                long n = parseNum(s, i);
                switch (op) {
                    case '+' : left += right; right = n; break;
                    case '-' : left += right; right = -n; break;
                    case '*' : right *= n; break;
                    case '/' : right /= n; break;
                }
                if (i < s.length()) {op = s.charAt(i);}
            }
            ++i;
        }
        long res = left + right;
        return (int)res;
    }

    // 辅函数- parse从位置i开始的一个数字
    long parseNum(String s, int i) {
        long n = 0;
        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            n = 10 * n + (s.charAt(i++) - '0');
        }
        return n;
    }
}

参考文献

【1】Java中long（Long）与int（Integer）之间的转换