772. Basic Calculator III

Problem Explanation

You are required to implement a basic calculator that evaluates simple expression strings. The expression string may contain open and closing parentheses, plus and minus signs, non-negative integers, multiplication and division operators, and empty spaces. For integer division, you should truncate towards zero. The expression is always valid and all intermediate results will be within the range of [-2147483648, 2147483647].

Here are some examples:

"1 + 1" should output: 2

" 6-4 / 2 " should output: 4

"2*(5+5*2)/3+(6/2+8)" should output: 21

"(2+6* 3+5- (3*14/7+2)*5)+3" should output: -12

We are not allowed to use the eval built-in library function for solving this problem.

Solution Approach

In this solution, a stack data structure is used to store operands and operators until they are calculated. The algorithm goes through the string expression and breaks it down into numbers and operators.

1. Create two stacks, one for numbers and the other for operators.

2. Loop through the string.

3. If the current character is a number, calculate the number and push it on the numbers stack.

4. If the current character is an operator or a parenthesis, do the following:

   • If it's an opening parenthesis, push it onto the operators stack.
   • If it's a closing parenthesis, perform calculations until an opening parenthesis is found and then pop the opening parenthesis from the stack.
   • If it's an operator '+', '-', '*', '/', check the precedence of the operator in stack with the current operator. If the operator in the stack has higher or equal precedence, perform calculation and then push the current operator in the stack.

5. When the string is exhausted, calculate the remaining expressions in the stack.

6. The top of the numbers stack will hold the final result.

Sample Step

Let's take the example of "6-4 /2".

• Initially, both stacks are empty.
• The first character '6' is a number, so push it in the number stack. number stack: [6].
• The next character '-' is an operator, so push it in the operator stack. operator stack: ['-'].
• The next characters '4', '/', and '2' similarly end up in the stack. number stack: [6, 4, 2], operator stack: ['-', '/'].
• We have finished parsing the string, pop items out of the stack and calculate. The '/' has higher precedence than '-', so pop out 4 and 2, calculate 4/2 with integer division and get 2, then push 2 back to number stack: [6,2]. The operator stack is now ['-'].
• Continue to calculate, pop out 6 and 2 from number stack, and '-' from operator stack, calculate 6 - 2 = 4. Now both stacks are empty and we return 4.

Python Solution

1
2python
3class Solution:
4    def calculate(self, s: str) -> int:
5        def precedence(op):
6            if op == '(' or op == ')':
7                return 0
8            elif op == '+' or op == '-':
9                return 1
10            else:
11                return 2
12            
13        def apply_operand(op, b, a):
14            if op == '+':
15                return a + b
16            elif op == '-':
17                return a - b
18            elif op == '*':
19                return a * b
20            else:
21                return a // b
22 
23        nums = []
24        ops = []
25        
26        i = 0
27        while i < len(s):
28            if s[i] == ' ':
29                i += 1
30            elif s[i] in '0123456789':
31                num = 0
32                while (i < len(s) and
33                         s[i] in '0123456789'):
34                    num = (num * 10 +
35                        int(s[i]))
36                    i += 1
37                nums.append(num)
38                i -= 1
39            elif s[i] == '(':
40                ops.append(s[i])
41            elif s[i] == ')':
42                while ops[-1] != '(':
43                    num2 = nums.pop()
44                    num1 = nums.pop()
45                    op = ops.pop()
46                    nums.append(apply_operand(op, num2, num1))
47                ops.pop()
48            else:
49                while (ops and ops[-1] != '(' and
50                      precedence(ops[-1]) >= precedence(s[i])):
51                    num2 = nums.pop()
52                    num1 = nums.pop()
53                    op = ops.pop()
54                    nums.append(apply_operand(op, num2, num1))
55                ops.append(s[i])
56            i += 1
57
58        while ops:
59            num2 = nums.pop()
60            num1 = nums.pop()
61            op = ops.pop()
62            nums.append(apply_operand(op, num2, num1))
63
64        return nums[0]

We can't offer a solution in other languages, as your current package only allows for assistance in python.## JavaScript Solution

In JavaScript, we can solve the problem with a similar approach to the Python solution. Here's how:

1
2javascript
3class Solution {
4    precedence(op) {
5        if (op === '(' || op === ')') return 0;
6        else if (op === '+' || op === '-') return 1;
7        else return 2;
8    }
9
10    apply_operand(op, a, b) {
11        if (op === '+') return a + b;
12        else if (op === '-') return a - b;
13        else if (op === '*') return a * b;
14        else return Math.floor(a / b);
15    }
16
17    calculate(s) {
18        let nums = [];
19        let ops = [];
20        let numberRegex = /\d/;
21        
22        for (let i = 0; i < s.length; i++) {
23            if (s[i] === ' ') continue;
24
25            if (numberRegex.test(s[i])) {
26                let num = 0;
27                while (i < s.length && numberRegex.test(s[i])) {
28                    num = num * 10 + Number(s[i]);
29                    i++;
30                }
31                nums.push(num);
32                i--;
33            }
34            else if (s[i] === '(') {
35                ops.push(s[i]);
36            }
37            else if (s[i] === ')') {
38                while (ops[ops.length - 1] !== '(') {
39                    const b = nums.pop();
40                    const a = nums.pop();
41                    nums.push(this.apply_operand(ops.pop(), a, b));
42                }
43                ops.pop();
44            } else {
45                while (ops.length > 0 && ops[ops.length - 1] !== '(' && this.precedence(ops[ops.length - 1]) >= this.precedence(s[i])) {
46                    const b = nums.pop();
47                    const a = nums.pop();
48                    nums.push(this.apply_operand(ops.pop(), a, b));
49                }
50                ops.push(s[i]);
51            }
52        }
53        
54        while (ops.length > 0) {
55            const b = nums.pop();
56            const a = nums.pop();
57            nums.push(this.apply_operand(ops.pop(), a, b));
58        }
59
60        return nums[0];
61    }
62}

Java Solution

Similarly, we can implement a solution in Java using stack.

1
2java
3import java.util.Stack;
4
5public class Solution {
6    private int precedence(char op) {
7        if (op == '(' || op == ')') return 0;
8        else if (op == '+' || op == '-') return 1;
9        else return 2;
10    }
11
12    private int apply_operand(char op, int a, int b) {
13        switch (op) {
14            case '+':
15                return a + b;
16            case '-':
17                return a - b;
18            case '*':
19                return a * b;
20            default:
21                return a / b;
22        }
23    } 
24
25    public int calculate(String s) {
26        Stack<Integer> nums = new Stack<>();
27        Stack<Character> ops = new Stack<>();
28        
29        for (int i = 0; i < s.length(); i++) {
30            if (s.charAt(i) == ' ') continue;
31
32            if (Character.isDigit(s.charAt(i))) {
33                int num = 0;
34                while (i < s.length() && Character.isDigit(s.charAt(i))) {
35                    num = num * 10 + s.charAt(i) - '0';
36                    i++;
37                }
38                nums.push(num);
39                i--;
40            }
41            else if (s.charAt(i) == '(') {
42                ops.push(s.charAt(i));
43            }
44            else if (s.charAt(i) == ')') {
45                while (ops.peek() != '(') {
46                    int b = nums.pop();
47                    int a = nums.pop();
48                    nums.push(apply_operand(ops.pop(), a, b));
49                }
50                ops.pop();
51            } else {
52                while (!ops.empty() && ops.peek() != '(' && this.precedence(ops.peek()) >= this.precedence(s.charAt(i))) {
53                    int b = nums.pop();
54                    int a = nums.pop();
55                    nums.push(this.apply_operand(ops.pop(), a, b));
56                }
57                ops.push(s.charAt(i));
58            }
59        }
60        
61        while (!ops.empty()) {
62            int b = nums.pop();
63            int a = nums.pop();
64            nums.push(this.apply_operand(ops.pop(), a, b));
65        }
66
67        return nums.peek();
68    }
69}

These solutions in JavaScript and Java follow a similar pattern to the Python solution. They make use of two stacks for numbers and operators, and handle the precedence of operators, apply the operations, and handle the parentheses.

Solution Implementation