Jobs

Interviews

Discussions

Basic Calculator

Hard

Salesforce

0 views

Topics:

StacksStrings

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

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

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Constraints:

1 <= s.length <= 3 * 10⁵
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer.

Basic Calculator

Hard

Salesforce

0 views

Topics:

StacksStrings

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

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

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Constraints:

1 <= s.length <= 3 * 10⁵
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer.

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 I assume the input string `s` will always represent a valid expression, or should I handle cases with invalid syntax?
What is the range of values for the non-negative integers within the expression?
Besides '+', '-', '(', ')', spaces, and non-negative integers, are there any other characters I should expect in the input string?
If the expression evaluates to a value outside the representable range of integers, should I throw an error or return a specific value (e.g., Integer.MAX_VALUE or Integer.MIN_VALUE)?
How should I handle division or multiplication if they are not explicitly disallowed in the problem description?

Brute Force Solution

Approach

The basic calculator problem takes a math problem written as text and needs to figure out the final answer. The brute force method for solving this means directly following the written instructions step by step, one operation at a time, exactly as they appear in the text.

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

First, look at the entire math problem and find the very first operation that needs to be done.
Perform only that one operation and remember the result.
Replace the original part of the problem with the result you just found.
Now you have a slightly simpler math problem. Look at it again and find the new first operation.
Keep doing this, one operation at a time, replacing the operation with its result until there's only one number left. That number is the final answer.

Code Implementation

def basic_calculator_brute_force(expression):
    expression = expression.replace(' ', '')

    while True:
        # Find the first multiplication or division
        multiplication_index = expression.find('*')
        division_index = expression.find('/')

        if multiplication_index == -1 and division_index == -1:
            # If no multiplication or division, find addition or subtraction
            addition_index = expression.find('+')
            subtraction_index = expression.find('-')

            if addition_index == -1 and subtraction_index == -1:
                # No operations left, the expression is the result
                return float(expression)

            if addition_index == -1:
                operation_index = subtraction_index
            elif subtraction_index == -1:
                operation_index = addition_index
            else:
                operation_index = min(addition_index, subtraction_index)

        elif multiplication_index == -1:
            operation_index = division_index
        elif division_index == -1:
            operation_index = multiplication_index
        else:
            operation_index = min(multiplication_index, division_index)

        # Extract the left and right operands
        left_operand_end = operation_index
        left_operand_start = left_operand_end - 1

        while left_operand_start >= 0 and (expression[left_operand_start].isdigit() or expression[left_operand_start] == '.'):
            left_operand_start -= 1

        left_operand_start += 1

        right_operand_start = operation_index + 1
        right_operand_end = right_operand_start

        while right_operand_end < len(expression) and (expression[right_operand_end].isdigit() or expression[right_operand_end] == '.'):
            right_operand_end += 1

        left_operand = float(expression[left_operand_start:left_operand_end])
        right_operand = float(expression[right_operand_start:right_operand_end])
        operator = expression[operation_index]

        # Perform the operation
        if operator == '*':
            result = left_operand * right_operand
        elif operator == '/':
            result = left_operand / right_operand
        elif operator == '+':
            result = left_operand + right_operand
        else:
            result = left_operand - right_operand

        # Replace the expression with the result
        expression = expression[:left_operand_start] + str(result) + expression[right_operand_end:]

        # Clean up any leading minus signs that might exist after concatenation.
        if expression.startswith('-'):
          expression = expression[1:]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The described algorithm iterates through the expression to find the first operation. After performing the operation, the expression is modified by replacing the operands and operator with the result. This process is repeated until a single number remains. Finding the first operation in each iteration takes O(n) time, and replacing the operands and operator also takes O(n) time because string manipulation or array copying might be involved. Since this is repeated until the expression is reduced to a single number, and the expression shrinks by a small amount in each iteration, the number of iterations will be O(n). Therefore, the total time complexity will be O(n) * (O(n) + O(n)) which is O(n) * O(2n) which simplifies to O(n³).

Space Complexity

O(1) – The provided algorithm iteratively modifies the input string in place, replacing operations with their results. It doesn't explicitly create any auxiliary data structures like lists, arrays, or hash maps to store intermediate values. Although string modification might involve creating temporary copies in some implementations, for the purpose of this analysis focusing on auxiliary space dictated by the algorithm itself, we only consider a few variables used to track the first operation. Therefore, the auxiliary space remains constant, regardless of the input string length N.

Optimal Solution

Approach

This problem requires us to evaluate a mathematical expression given as a string. The most efficient approach involves using a stack to keep track of numbers and signs, processing the expression one character at a time, and updating the stack accordingly.

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

Start by setting up a place to store numbers and operations temporarily, like a stack of plates.
Go through the expression from left to right, looking at each piece (number, symbol) individually.
If you see a number, put it on the stack.
If you see a plus or minus, handle it based on what's on the stack. It's like checking if you need to add or subtract the next number you encounter.
If you see an opening parenthesis, think of it as starting a new calculation. Store the current total and the sign so you can resume later.
If you see a closing parenthesis, finish the current calculation inside the parentheses and combine it with the previous total and sign.
Once you've gone through the entire expression, the final value is the only thing left. That's your answer.

Code Implementation

def calculate_expression(expression):
    current_number = 0
    operation_stack = []
    result = 0
    sign = 1

    for character in expression:
        if character.isdigit():
            current_number = current_number * 10 + int(character)
        elif character == '+':
            result += sign * current_number
            current_number = 0
            sign = 1
        elif character == '-':
            result += sign * current_number
            current_number = 0
            sign = -1
        elif character == '(': # Store result and sign for later
            operation_stack.append(result)
            operation_stack.append(sign)
            result = 0
            sign = 1
        elif character == ')': # Finish current calculation
            result += sign * current_number
            current_number = 0
            result *= operation_stack.pop()
            result += operation_stack.pop()
        else:
            pass

    if current_number != 0: # Add the last number
        result += sign * current_number

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n exactly once. Each character in the string is processed in constant time, involving operations such as number parsing, stack pushes and pops, and basic arithmetic. The number of stack operations is bounded by the number of characters in the input string. Therefore, the overall time complexity is directly proportional to the length of the input string, resulting in O(n).

Space Complexity

O(N) – The algorithm uses a stack to store intermediate numbers, signs, and results when encountering parentheses. In the worst-case scenario, the expression could consist of nested parentheses and numbers, requiring the stack to store a number of elements proportional to the length of the input string. Therefore, the auxiliary space used by the stack can grow linearly with the input size N, where N is the length of the input string representing the mathematical expression. Consequently, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input string	Return 0 as the result of an empty expression.
String containing only whitespace	Return 0 after trimming whitespace from the string.
Input string starts with a negative sign	Initialize the sign to -1 and parse the following number appropriately.
Consecutive operators (e.g., '1 + - 2')	Handle the sign changes appropriately, effectively treating '--' as '+' and '+-' as '-'.
Nested parentheses (e.g., '(1+(4+5+2)-3)+(6+8)')	Use a stack to keep track of the sign and intermediate results for each parenthesis level.
Integer overflow during calculation	Use a long integer to store intermediate results and check if the final result exceeds the Integer.MAX_VALUE or Integer.MIN_VALUE range, returning the boundary if it does.
Missing closing parenthesis	The stack-based approach will naturally handle this by preserving intermediate result, but consider explicit error handling for production code.
Very long input string exceeding stack space or causing performance issues	The iterative stack-based approach generally avoids stack overflow, but consider alternative expression parsing methods if extremely large inputs become a concern, perhaps limiting string size.

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 I assume the input string `s` will always represent a valid expression, or should I handle cases with invalid syntax?
What is the range of values for the non-negative integers within the expression?
Besides '+', '-', '(', ')', spaces, and non-negative integers, are there any other characters I should expect in the input string?
If the expression evaluates to a value outside the representable range of integers, should I throw an error or return a specific value (e.g., Integer.MAX_VALUE or Integer.MIN_VALUE)?
How should I handle division or multiplication if they are not explicitly disallowed in the problem description?

Brute Force Solution

Approach

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

First, look at the entire math problem and find the very first operation that needs to be done.
Perform only that one operation and remember the result.
Replace the original part of the problem with the result you just found.
Now you have a slightly simpler math problem. Look at it again and find the new first operation.
Keep doing this, one operation at a time, replacing the operation with its result until there's only one number left. That number is the final answer.

Code Implementation

def basic_calculator_brute_force(expression):
    expression = expression.replace(' ', '')

    while True:
        # Find the first multiplication or division
        multiplication_index = expression.find('*')
        division_index = expression.find('/')

        if multiplication_index == -1 and division_index == -1:
            # If no multiplication or division, find addition or subtraction
            addition_index = expression.find('+')
            subtraction_index = expression.find('-')

            if addition_index == -1 and subtraction_index == -1:
                # No operations left, the expression is the result
                return float(expression)

            if addition_index == -1:
                operation_index = subtraction_index
            elif subtraction_index == -1:
                operation_index = addition_index
            else:
                operation_index = min(addition_index, subtraction_index)

        elif multiplication_index == -1:
            operation_index = division_index
        elif division_index == -1:
            operation_index = multiplication_index
        else:
            operation_index = min(multiplication_index, division_index)

        # Extract the left and right operands
        left_operand_end = operation_index
        left_operand_start = left_operand_end - 1

        while left_operand_start >= 0 and (expression[left_operand_start].isdigit() or expression[left_operand_start] == '.'):
            left_operand_start -= 1

        left_operand_start += 1

        right_operand_start = operation_index + 1
        right_operand_end = right_operand_start

        while right_operand_end < len(expression) and (expression[right_operand_end].isdigit() or expression[right_operand_end] == '.'):
            right_operand_end += 1

        left_operand = float(expression[left_operand_start:left_operand_end])
        right_operand = float(expression[right_operand_start:right_operand_end])
        operator = expression[operation_index]

        # Perform the operation
        if operator == '*':
            result = left_operand * right_operand
        elif operator == '/':
            result = left_operand / right_operand
        elif operator == '+':
            result = left_operand + right_operand
        else:
            result = left_operand - right_operand

        # Replace the expression with the result
        expression = expression[:left_operand_start] + str(result) + expression[right_operand_end:]

        # Clean up any leading minus signs that might exist after concatenation.
        if expression.startswith('-'):
          expression = expression[1:]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by setting up a place to store numbers and operations temporarily, like a stack of plates.
Go through the expression from left to right, looking at each piece (number, symbol) individually.
If you see a number, put it on the stack.
If you see a plus or minus, handle it based on what's on the stack. It's like checking if you need to add or subtract the next number you encounter.
If you see an opening parenthesis, think of it as starting a new calculation. Store the current total and the sign so you can resume later.
If you see a closing parenthesis, finish the current calculation inside the parentheses and combine it with the previous total and sign.
Once you've gone through the entire expression, the final value is the only thing left. That's your answer.

Code Implementation

def calculate_expression(expression):
    current_number = 0
    operation_stack = []
    result = 0
    sign = 1

    for character in expression:
        if character.isdigit():
            current_number = current_number * 10 + int(character)
        elif character == '+':
            result += sign * current_number
            current_number = 0
            sign = 1
        elif character == '-':
            result += sign * current_number
            current_number = 0
            sign = -1
        elif character == '(': # Store result and sign for later
            operation_stack.append(result)
            operation_stack.append(sign)
            result = 0
            sign = 1
        elif character == ')': # Finish current calculation
            result += sign * current_number
            current_number = 0
            result *= operation_stack.pop()
            result += operation_stack.pop()
        else:
            pass

    if current_number != 0: # Add the last number
        result += sign * current_number

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return 0 as the result of an empty expression.
String containing only whitespace	Return 0 after trimming whitespace from the string.
Input string starts with a negative sign	Initialize the sign to -1 and parse the following number appropriately.
Consecutive operators (e.g., '1 + - 2')	Handle the sign changes appropriately, effectively treating '--' as '+' and '+-' as '-'.
Nested parentheses (e.g., '(1+(4+5+2)-3)+(6+8)')	Use a stack to keep track of the sign and intermediate results for each parenthesis level.
Integer overflow during calculation	Use a long integer to store intermediate results and check if the final result exceeds the Integer.MAX_VALUE or Integer.MIN_VALUE range, returning the boundary if it does.
Missing closing parenthesis	The stack-based approach will naturally handle this by preserving intermediate result, but consider explicit error handling for production code.
Very long input string exceeding stack space or causing performance issues	The iterative stack-based approach generally avoids stack overflow, but consider alternative expression parsing methods if extremely large inputs become a concern, perhaps limiting string size.