Problem

Implement a basic calculator to evaluate a simple expression string.

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 [-2^31, 2^31 - 1].

Examples

Example 1:

Input: "1 + 1"  
Output: 2

Example 2:

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

Example 3:

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

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
  • s represents a valid expression.
  • All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
  • The answer is guaranteed to fit in a 32-bit integer.

Solution

Method 1 - Using Operand and Operator Stack - Calculating Answer as Soon as Possible

We can proceed similar to Basic Calculator 2 Problem. But this time along with numStack, we take operator stack as well.

  1. Each time we see digit, we make a number out of it , we push it numStack
  2. If we see operator, we push it to opStack.
    1. But before pushing it, we check if there are any higher precedence operator already in stack. If so, we should first process them, by poping them out and corresponding numbers from numStack
  3. If we see ) , we just push it to opStack
  4. If we see (, we should pop everything out from opStack until we see ) in stack. Finally we pop out ) as well, marking one set of parenthesis as done.

Also, note that I have used lambda expressions in java for isOperator() function and hasPrecedence(). They can be simple functions, I just wanted to learn about them.

Code

Java
public class Solution {
    public int calculate(String s) {  
        if (s == null || s.length() == 0) {  
            return 0;  
        }  
    
        Stack<Character> opStack = new Stack<>();  
        Stack<Integer> numStack = new Stack<>();  

        for (int i = 0; i < s.length(); i++) {  
            char ch = s.charAt(i);  
            if (ch == ' ') continue;  
            if (Character.isDigit(ch)) {  
                int num = ch - '0';  
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {  
                    num = num * 10 + s.charAt(i + 1) - '0';  
                    i++;  
                }  
                numStack.push(num);  
            } else if (ch == '(') {  
                opStack.push(ch);  
            } else if (ch == ')') {  
                while (opStack.peek() != '(') {  
                    numStack.push(calculateOperation(opStack.pop(), numStack.pop(), numStack.pop()));  
                }  
                opStack.pop(); 
            } else if (isOperator(ch)) {  
                while (!opStack.isEmpty() && hasPrecedence(ch, opStack.peek())) {  
                    numStack.push(calculateOperation(opStack.pop(), numStack.pop(), numStack.pop()));  
                }  
                opStack.push(ch);  
            }  
        }  
    
        while (!opStack.isEmpty()) {  
            numStack.push(calculateOperation(opStack.pop(), numStack.pop(), numStack.pop()));  
        }  

        return numStack.pop();  
    }  

    private boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }
    
    private boolean hasPrecedence(char op1, char op2) {  
        if (op2 == '(' || op2 == ')') {  
            return false;  
        }  
        if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) {  
            return false;  
        }  
        return true;  
    }  

    private int calculateOperation(char operator, int num1, int num2) {  
        switch (operator) {  
            case '+': return num1 + num2;  
            case '-': return num2 - num1;  
            case '*': return num1 * num2;  
            case '/': return num2 / num1;  
        }  
        return 0;  
    }
}
Gotcha: While Calculating Numbers

While calculating number, this will not work, as we are calculating i++ twice. Hence we check for i+1 in above and not i

while (i < s.length() && Character.isDigit(s.charAt(i))) {
	num = num * 10 + Character.getNumericValue(s.charAt(i));
	i++;
}
Changing Calculate Function a Bit

As the calculateOperation method takes operator and numbers, that also works. But we can just pass the 2 stack, and let it do the operation as well. But the function returns void, and modifies stack in place, which is not good when we see functional coding.

private void calculateOperation(Stack<Integer> numStack, Stack<Character> opStack) {
	int num2 = numStack.pop();
	int num1 = numStack.pop();
	 
	char op = opStack.pop();
	 
	int ans = 0;
	 
	switch(op) {
		case '+':
			ans = num1 + num2;
		break;
		case '-':
			ans = num1 - num2;
		break;
		case '*':
			ans = num1 * num2;
		break;
		case '/':
			ans = num1 / num2;
		break;
	}
	 
	numStack.push(ans);
}
Python
class Solution:
    def calculate(self, s: str) -> int:
        def calculate_operation(op: str, num1: int, num2: int) -> int:
            if op == '+':
                return num1 + num2
            elif op == '-':
                return num2 - num1
            elif op == '*':
                return num1 * num2
            elif op == '/':
                return int(num2 / num1)  # Ensure integer division truncates towards zero
        
        def is_operator(ch: str) -> bool:
            return ch in {'+', '-', '*', '/'}
        
        def has_precedence(op1: str, op2: str) -> bool:
            if op2 in {'(', ')'}:
                return False
            if (op1 in {'*', '/'} and op2 in {'+', '-'}):
                return False
            return True
        
        num_stack: List[int] = []
        op_stack: List[str] = []

        i = 0
        while i < len(s):
            ch = s[i]
            if ch == ' ':
                i += 1
                continue
            if ch.isdigit():
                num = int(ch)
                while i + 1 < len(s) and s[i + 1].isdigit():
                    num = num * 10 + int(s[i + 1])
                    i += 1
                num_stack.append(num)
            elif ch == '(':
                op_stack.append(ch)
            elif ch == ')':
                while op_stack and op_stack[-1] != '(':
                    num_stack.append(calculate_operation(op_stack.pop(), num_stack.pop(), num_stack.pop()))
                op_stack.pop()  # remove the '('
            elif is_operator(ch):
                while op_stack and has_precedence(ch, op_stack[-1]):
                    num_stack.append(calculate_operation(op_stack.pop(), num_stack.pop(), num_stack.pop()))
                op_stack.append(ch)
            i += 1

        while op_stack:
            num_stack.append(calculate_operation(op_stack.pop(), num_stack.pop(), num_stack.pop()))

        return num_stack[-1]

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the expression string.
  • 🧺 Space complexity: O(n), due to the stacks holding operators and numbers.