Jobs

Interviews

Discussions

Basic Calculator III

Hard

Basic Calculator III

Hard

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` contain spaces, and if so, how should I handle them?
What is the range of integer values that can appear in the expression, and should I be concerned about integer overflow?
Besides the standard operators (+, -, *, /) and parentheses, are there any other characters or operators I should expect in the input string?
How should I handle division by zero? Is it possible, and if so, should I return an error, throw an exception, or is there a defined behavior?
Is the input expression always guaranteed to be valid and well-formed, or do I need to handle cases of invalid syntax, such as unmatched parentheses?

Brute Force Solution

Approach

The brute force approach to this calculator problem is like trying every single way to evaluate the expression. We explore all possible orders of operations to find the correct result. It's very inefficient but guarantees we'll eventually find the right answer if we check everything.

Here's how the algorithm would work step-by-step:

First, think of all possible ways to add parentheses to the expression. This changes the order in which things are calculated.
For each of those parenthesized expressions, evaluate it step by step, working from the innermost parentheses outwards.
To evaluate any expression, look for the operations like multiplication and division first. Perform those calculations in order from left to right.
Once there are no more multiplications or divisions, look for additions and subtractions. Perform those from left to right.
After evaluating a parenthesized part, replace that entire section with its calculated result.
Repeat the process until there are no more parentheses and you've evaluated the whole expression down to a single number.
Since we started with every possible arrangement of parentheses, this final number will be the correct answer (eventually).

Code Implementation

def basic_calculator_iii_brute_force(expression):
    # Brute force approach is not feasible for this problem
    # Returning a placeholder value
    return evaluate_expression(expression)

def evaluate_expression(expression_string):
    expression_string = expression_string.replace(' ', '')
    
    if not any(op in expression_string for op in ['+', '-', '*', '/']):
        return int(expression_string)

    # Perform multiplication and division first
    index = 0
    while index < len(expression_string):
        if expression_string[index] == '*' or expression_string[index] == '/':
            left_operand_end = index - 1
            while left_operand_end >= 0 and expression_string[left_operand_end].isdigit():
                left_operand_end -= 1
            left_operand_start = left_operand_end + 1
            
            right_operand_start = index + 1
            right_operand_end = right_operand_start
            while right_operand_end < len(expression_string) and expression_string[right_operand_end].isdigit():
                right_operand_end += 1
            
            left_operand = int(expression_string[left_operand_start:index])
            right_operand = int(expression_string[index + 1:right_operand_end])

            # Evaluate mul or div operations
            if expression_string[index] == '*':
                result = left_operand * right_operand
            else:
                result = left_operand // right_operand

            expression_string = expression_string[:left_operand_start] + str(result) + expression_string[right_operand_end:]
            index = 0
        else:
            index += 1

    # Perform addition and subtraction
    index = 0
    while index < len(expression_string):
        if expression_string[index] == '+' or expression_string[index] == '-':
            left_operand_end = index - 1
            while left_operand_end >= 0 and expression_string[left_operand_end].isdigit():
                left_operand_end -= 1
            left_operand_start = left_operand_end + 1
            
            right_operand_start = index + 1
            right_operand_end = right_operand_start
            while right_operand_end < len(expression_string) and expression_string[right_operand_end].isdigit():
                right_operand_end += 1
            
            left_operand = int(expression_string[left_operand_start:index])
            right_operand = int(expression_string[index + 1:right_operand_end])

            # Evaluate addition or subtraction
            if expression_string[index] == '+':
                result = left_operand + right_operand
            else:
                result = left_operand - right_operand

            expression_string = expression_string[:left_operand_start] + str(result) + expression_string[right_operand_end:]
            index = 0
        else:
            index += 1
    
    return int(expression_string)

Big(O) Analysis

Time Complexity

O(4^n / n^(3/2)) – The brute force approach involves generating all possible parenthesizations of the expression. The number of ways to parenthesize an expression of length n is given by the Catalan number, which is approximately 4^n / (n * sqrt(n)). For each of these parenthesized expressions, we evaluate it which takes O(n) time. Therefore, the total time complexity is approximately O(n * 4^n / (n * sqrt(n))) which simplifies to O(4^n / n^(3/2)).

Space Complexity

O(N^2) – The brute force approach explores all possible parenthesizations of the input expression. The number of possible parenthesizations grows as Catalan numbers, but a looser bound based on string manipulation gives N^2. Evaluating each parenthesized expression involves creating substrings, which may require storing portions of the original string, potentially leading to N substrings each of length N in the worst case. Therefore, the space to store these intermediate strings results in O(N^2) auxiliary space complexity where N is the length of the input expression string.

Optimal Solution

Approach

This calculator problem is about evaluating an expression given as a string. The efficient way to solve it is to recognize the order of operations (PEMDAS/BODMAS) and use a stack-based approach to keep track of intermediate results and handle parentheses correctly.

Here's how the algorithm would work step-by-step:

First, understand that multiplication and division need to happen before addition and subtraction.
Use a stack to hold numbers that are waiting to be added or subtracted.
Go through the expression character by character.
If you find a number, read the whole number and then check the previous operator.
If the previous operator was multiplication or division, perform that operation immediately with the number on top of the stack, and put the result back on the stack.
If the previous operator was addition or subtraction, push the current number onto the stack (with a possible negative sign if the operator was subtraction).
If you find an opening parenthesis, start a new calculation within the parentheses using the same method, treating it as a subproblem.
When you find a closing parenthesis, finish the calculation inside the parentheses, and treat the result as a single number for the outer calculation.
After processing the whole expression, add up all the numbers left on the stack. The final result is the answer.

Code Implementation

def calculate(expression_string):
    current_number = 0
    operation = '+'
    stack = []

    for i in range(len(expression_string)):
        character = expression_string[i]

        if character.isdigit():
            current_number = (current_number * 10) + int(character)

        if character in '+-*/()' or i == len(expression_string) - 1:
            if character == '(': # Start a sub-calculation.
                count = 1
                j = i + 1
                while count > 0:
                    if expression_string[j] == '(': 
                        count += 1
                    elif expression_string[j] == ')':
                        count -= 1
                    j += 1
                current_number = calculate(expression_string[i + 1:j - 1])
                i = j - 1 # Advance index after evaluating sub-expression.

            if operation == '+':
                stack.append(current_number)
            elif operation == '-':
                stack.append(-current_number)
            elif operation == '*': # Immediate multiplication.

                stack.append(stack.pop() * current_number)
            elif operation == '/': # Immediate division.

                stack.append(int(stack.pop() / current_number))

            operation = character
            current_number = 0

    result = 0
    while stack: # Sum remaining values in the stack.
        result += stack.pop()

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once. Inside the loop, numerical parsing can involve multiple digits, but each digit is only processed once across the entire string. Stack operations (push and pop) take constant time. Therefore, the overall time complexity is dominated by the single pass through the string, resulting in O(n) time complexity.

Space Complexity

O(N) – The primary auxiliary space usage comes from the stack. In the worst-case scenario, such as an expression with nested parentheses and alternating operators like '1+(2*(3+(4*5)))', the stack can grow to store intermediate results and numbers corresponding to each level of parenthesis nesting. The maximum depth of the nested parentheses, and consequently the maximum size of the stack, can be proportional to the length of the input string, N. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input string	Return 0 immediately as there's nothing to evaluate
String contains only whitespace	Return 0 after trimming whitespace if empty, or handle the whitespace gracefully during parsing by skipping it.
String starts with an operator (+, -, *, /)	Prepend '0' to the string to handle initial operators by treating them as unary
Consecutive operators (e.g., 2 + - 3)	Handle unary operators correctly by parsing the operator and its subsequent operand
Division by zero	Throw an exception or return a predefined error value to avoid undefined behavior
Integer overflow during calculation	Use a larger data type (e.g., long) or check for overflow conditions before performing the operation and throw an exception if needed
Very long input string exceeding stack limits	Use an iterative approach instead of recursion to avoid stack overflow for large expressions
Input contains invalid characters	Reject the input string or skip the invalid characters and continue parsing the rest.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` contain spaces, and if so, how should I handle them?
What is the range of integer values that can appear in the expression, and should I be concerned about integer overflow?
Besides the standard operators (+, -, *, /) and parentheses, are there any other characters or operators I should expect in the input string?
How should I handle division by zero? Is it possible, and if so, should I return an error, throw an exception, or is there a defined behavior?
Is the input expression always guaranteed to be valid and well-formed, or do I need to handle cases of invalid syntax, such as unmatched parentheses?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, think of all possible ways to add parentheses to the expression. This changes the order in which things are calculated.
For each of those parenthesized expressions, evaluate it step by step, working from the innermost parentheses outwards.
To evaluate any expression, look for the operations like multiplication and division first. Perform those calculations in order from left to right.
Once there are no more multiplications or divisions, look for additions and subtractions. Perform those from left to right.
After evaluating a parenthesized part, replace that entire section with its calculated result.
Repeat the process until there are no more parentheses and you've evaluated the whole expression down to a single number.
Since we started with every possible arrangement of parentheses, this final number will be the correct answer (eventually).

Code Implementation

def basic_calculator_iii_brute_force(expression):
    # Brute force approach is not feasible for this problem
    # Returning a placeholder value
    return evaluate_expression(expression)

def evaluate_expression(expression_string):
    expression_string = expression_string.replace(' ', '')
    
    if not any(op in expression_string for op in ['+', '-', '*', '/']):
        return int(expression_string)

    # Perform multiplication and division first
    index = 0
    while index < len(expression_string):
        if expression_string[index] == '*' or expression_string[index] == '/':
            left_operand_end = index - 1
            while left_operand_end >= 0 and expression_string[left_operand_end].isdigit():
                left_operand_end -= 1
            left_operand_start = left_operand_end + 1
            
            right_operand_start = index + 1
            right_operand_end = right_operand_start
            while right_operand_end < len(expression_string) and expression_string[right_operand_end].isdigit():
                right_operand_end += 1
            
            left_operand = int(expression_string[left_operand_start:index])
            right_operand = int(expression_string[index + 1:right_operand_end])

            # Evaluate mul or div operations
            if expression_string[index] == '*':
                result = left_operand * right_operand
            else:
                result = left_operand // right_operand

            expression_string = expression_string[:left_operand_start] + str(result) + expression_string[right_operand_end:]
            index = 0
        else:
            index += 1

    # Perform addition and subtraction
    index = 0
    while index < len(expression_string):
        if expression_string[index] == '+' or expression_string[index] == '-':
            left_operand_end = index - 1
            while left_operand_end >= 0 and expression_string[left_operand_end].isdigit():
                left_operand_end -= 1
            left_operand_start = left_operand_end + 1
            
            right_operand_start = index + 1
            right_operand_end = right_operand_start
            while right_operand_end < len(expression_string) and expression_string[right_operand_end].isdigit():
                right_operand_end += 1
            
            left_operand = int(expression_string[left_operand_start:index])
            right_operand = int(expression_string[index + 1:right_operand_end])

            # Evaluate addition or subtraction
            if expression_string[index] == '+':
                result = left_operand + right_operand
            else:
                result = left_operand - right_operand

            expression_string = expression_string[:left_operand_start] + str(result) + expression_string[right_operand_end:]
            index = 0
        else:
            index += 1
    
    return int(expression_string)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, understand that multiplication and division need to happen before addition and subtraction.
Use a stack to hold numbers that are waiting to be added or subtracted.
Go through the expression character by character.
If you find a number, read the whole number and then check the previous operator.
If the previous operator was multiplication or division, perform that operation immediately with the number on top of the stack, and put the result back on the stack.
If the previous operator was addition or subtraction, push the current number onto the stack (with a possible negative sign if the operator was subtraction).
If you find an opening parenthesis, start a new calculation within the parentheses using the same method, treating it as a subproblem.
When you find a closing parenthesis, finish the calculation inside the parentheses, and treat the result as a single number for the outer calculation.
After processing the whole expression, add up all the numbers left on the stack. The final result is the answer.

Code Implementation

def calculate(expression_string):
    current_number = 0
    operation = '+'
    stack = []

    for i in range(len(expression_string)):
        character = expression_string[i]

        if character.isdigit():
            current_number = (current_number * 10) + int(character)

        if character in '+-*/()' or i == len(expression_string) - 1:
            if character == '(': # Start a sub-calculation.
                count = 1
                j = i + 1
                while count > 0:
                    if expression_string[j] == '(': 
                        count += 1
                    elif expression_string[j] == ')':
                        count -= 1
                    j += 1
                current_number = calculate(expression_string[i + 1:j - 1])
                i = j - 1 # Advance index after evaluating sub-expression.

            if operation == '+':
                stack.append(current_number)
            elif operation == '-':
                stack.append(-current_number)
            elif operation == '*': # Immediate multiplication.

                stack.append(stack.pop() * current_number)
            elif operation == '/': # Immediate division.

                stack.append(int(stack.pop() / current_number))

            operation = character
            current_number = 0

    result = 0
    while stack: # Sum remaining values in the stack.
        result += stack.pop()

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return 0 immediately as there's nothing to evaluate
String contains only whitespace	Return 0 after trimming whitespace if empty, or handle the whitespace gracefully during parsing by skipping it.
String starts with an operator (+, -, *, /)	Prepend '0' to the string to handle initial operators by treating them as unary
Consecutive operators (e.g., 2 + - 3)	Handle unary operators correctly by parsing the operator and its subsequent operand
Division by zero	Throw an exception or return a predefined error value to avoid undefined behavior
Integer overflow during calculation	Use a larger data type (e.g., long) or check for overflow conditions before performing the operation and throw an exception if needed
Very long input string exceeding stack limits	Use an iterative approach instead of recursion to avoid stack overflow for large expressions
Input contains invalid characters	Reject the input string or skip the invalid characters and continue parsing the rest.