849. Basic Calculator III

Description

中文English

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 .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . 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 [-2147483648, 2147483647]

Do not use the eval built-in library function.

Have you met this question in a real interview?  

Example

Example 1:

Input："1 + 1"
Output：2
Explanation：1 + 1 = 2

Example 2:

Input：" 6-4 / 2 "
Output：4
Explanation：4/2=2，6-2=4

Code(Language:C++) (Judger:ip-172-31-5-19)

class Solution {
public:
    /**
     * @param s: the expression string
     * @return: the answer
     */
       int calculate(string s) {
           //网上答案
        int n = s.size(), num = 0, curRes = 0, res = 0;
        char op = '+';
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                int j = i, cnt = 0;
                for (; i < n; ++i) {
                    if (s[i] == '(') ++cnt;
                    if (s[i] == ')') --cnt;
                    if (cnt == 0) break;
                }
                num = calculate(s.substr(j + 1, i - j - 1)); // recursion 
            }
              if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) { // c 和 op的使用有些绕
                switch (op) {
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-' || i == n - 1) {
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            }
        }
        return res;
    }
};