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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30
Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫