772. Basic Calculator III

Posted on Edited on In

772. Basic Calculator III

Description

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. 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 [-2^31, 2^31 - 1].

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

Example 1:

1
2
Input: s = "1+1"
Output: 2

Example 2:

1
2
Input: s = "6-4/2"
Output: 4

Example 3:

1
2
Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21

Constraints:

  • 1 <= s <= 10^4
  • s consists of digits, '+', '-', '*', '/', '(',and')'.
  • s is a valid expression.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
    unordered_map<char, int> op_priority = {
        {'+', 1},
        {'-', 1},
        {'*', 2},
        {'/', 2}
    };

    stack<char> ops;
    stack<long long> nums;

    int calculate(string s) {
        nums.push(0);
        int n = s.size();
        for (int i = 0; i < n; ) {
            if (s[i] == ' ') {
                i++;
                continue;
            } else if (s[i] == '(') {
                ops.push('(');
                if (s[i + 1] == '-') {
                    i++;
                    nums.push(0);
                    ops.push('-');
                }
                i++;
            } else if (s[i] == ')') {
                while (ops.top() != '(') {
                    cal();
                }
                ops.pop();
                i++;
            } else if (s[i] >= '0' && s[i] <= '9') {
                int l = i;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    i++;
                }
                nums.push(stoi(s.substr(l, i - l)));
            } else {
                while (!ops.empty() && ops.top() != '(' && op_priority[ops.top()] >= op_priority[s[i]]) {
                    cal();
                }
                ops.push(s[i]);
                i++;
            }
        }
        while (!ops.empty() && ops.top() != '(') {
            cal();
        }
        return nums.top();
    }

    void cal() {
        long long b = nums.top(); nums.pop();
        long long a = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        long long res;
        switch (op) {
            case '+': res = a + b; break;
            case '-': res = a - b; break;
            case '*': res = a * b; break;
            case '/': res = a / b; break;
        }
        nums.push(res);
    }
};