Skip to content

772. Basic Calculator III πŸ”’

DifficultyHard

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 [-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 = "1+1"
Output: 2

Example 2:

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

Example 3:

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

 

Constraints:

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

Solutions

Solution 1

Thinking

Evaluate \(+,-,*,/\) and parentheses. \(n\le 10^4\). Multiplication and division bind immediately to the stack top; addition pushes a signed term and we sum at the end.

A ( starts a recursive evaluation until ); the result is the current number. A deque consumes the string once.

\(\textit{sign}\) is the previous operator; at each new operator we apply it to \(\textit{num}\). Division truncates toward zero.

 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
class Solution:
    def calculate(self, s: str) -> int:
        def dfs(q):
            num, sign, stk = 0, "+", []
            while q:
                c = q.popleft()
                if c.isdigit():
                    num = num * 10 + int(c)
                if c == "(":
                    num = dfs(q)
                if c in "+-*/)" or not q:
                    match sign:
                        case "+":
                            stk.append(num)
                        case "-":
                            stk.append(-num)
                        case "*":
                            stk.append(stk.pop() * num)
                        case "/":
                            stk.append(int(stk.pop() / num))
                    num, sign = 0, c
                if c == ")":
                    break
            return sum(stk)

        return dfs(deque(s))

 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
class Solution {
    public int calculate(String s) {
        Deque<Character> q = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            q.offer(c);
        }
        return dfs(q);
    }

    private int dfs(Deque<Character> q) {
        long num = 0;
        char sign = '+';
        List<Long> stk = new ArrayList<>();
        while (!q.isEmpty()) {
            char c = q.poll();
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if (c == '(') {
                num = dfs(q);
            }
            if ("+-*/)".indexOf(c) >= 0 || q.isEmpty()) {
                if (sign == '+') {
                    stk.add(num);
                } else if (sign == '-') {
                    stk.add(-num);
                } else if (sign == '*') {
                    stk.set(stk.size() - 1, stk.get(stk.size() - 1) * num);
                } else {
                    stk.set(stk.size() - 1, stk.get(stk.size() - 1) / num);
                }
                num = 0;
                sign = c;
            }
            if (c == ')') {
                break;
            }
        }
        long ans = 0;
        for (long x : stk) {
            ans += x;
        }
        return (int) ans;
    }
}

 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
class Solution {
public:
    int calculate(string s) {
        queue<char> q;
        for (char c : s) {
            q.push(c);
        }
        return dfs(q);
    }

private:
    int dfs(queue<char>& q) {
        long long num = 0;
        char sign = '+';
        vector<long long> stk;
        while (!q.empty()) {
            char c = q.front();
            q.pop();
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            }
            if (c == '(') {
                num = dfs(q);
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || c == ')' || q.empty()) {
                if (sign == '+') {
                    stk.push_back(num);
                } else if (sign == '-') {
                    stk.push_back(-num);
                } else if (sign == '*') {
                    stk.back() *= num;
                } else {
                    stk.back() /= num;
                }
                num = 0;
                sign = c;
            }
            if (c == ')') {
                break;
            }
        }
        return accumulate(stk.begin(), stk.end(), 0LL);
    }
};

 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
func calculate(s string) int {
    q := []byte(s)
    var dfs func() int
    dfs = func() int {
        num, sign := 0, byte('+')
        var stk []int
        for len(q) > 0 {
            c := q[0]
            q = q[1:]
            if c >= '0' && c <= '9' {
                num = num*10 + int(c-'0')
            }
            if c == '(' {
                num = dfs()
            }
            if c == '+' || c == '-' || c == '*' || c == '/' || c == ')' || len(q) == 0 {
                switch sign {
                case '+':
                    stk = append(stk, num)
                case '-':
                    stk = append(stk, -num)
                case '*':
                    stk[len(stk)-1] *= num
                default:
                    stk[len(stk)-1] /= num
                }
                num, sign = 0, c
            }
            if c == ')' {
                break
            }
        }
        ans := 0
        for _, x := range stk {
            ans += x
        }
        return ans
    }
    return dfs()
}

Comments