Jobs

Interviews

Discussions

Basic Calculator

Hard

TikTok

1 view

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

TikTok

1 view

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 the input string `s` contain characters other than digits, '+', '-', '(', ')', and space?
What is the expected range of integer values within the expression, and should I handle potential overflow?
Can the input string `s` be empty or null, and if so, what should I return?
Are nested parentheses allowed, and what is the maximum level of nesting?
Should I assume that the input expression is always valid, or do I need to handle invalid input cases such as mismatched parentheses or consecutive operators?

Brute Force Solution

Approach

The goal is to directly calculate the result of the given expression. We achieve this by processing the string character by character, keeping track of the current number and operation. It's a straightforward, step-by-step evaluation without any clever shortcuts.

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

Start at the beginning of the expression.
Read the expression character by character.
If you see a number, remember it; you are building the current number.
If you see an operation (like +, -, *, or /), store that operation to perform later.
Once you have both a number and an operation, perform that operation with the previous result (or 0 if it's the first number).
Store the new result.
Continue reading the expression, building numbers and performing operations as you go.
When you reach the end of the expression, the final result is what you've stored.

Code Implementation

def calculate_basic(expression):
    current_number = 0
    last_operation = '+'
    result = 0
    string_index = 0

    while string_index < len(expression):
        char = expression[string_index]

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

        if char in '+-*/' or string_index == len(expression) - 1:
            # Perform operation when an operator or end is encountered.
            if last_operation == '+':
                result += current_number
            elif last_operation == '-':
                result -= current_number
            elif last_operation == '*':
                result *= current_number
            elif last_operation == '/':
                # Integer division as per problem description
                result = int(result / current_number)

            last_operation = char
            current_number = 0

        string_index += 1

    # The final result is accumulated in the 'result' variable.
    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once, character by character. The operations performed in each iteration (reading a character, updating the current number, performing an operation) take constant time, O(1). Therefore, the overall time complexity is directly proportional to the length of the input string, n, which represents the number of characters in the expression. This makes the time complexity O(n).

Space Complexity

O(1) – The algorithm, as described, only uses a few variables to store the current number, the operation, and the result. These variables take up a constant amount of space, irrespective of the length of the input expression string, which we can denote as N. No dynamic data structures, such as lists or hash maps, are employed. Therefore, the auxiliary space used is constant.

Optimal Solution

Approach

To evaluate the arithmetic expression string, we avoid directly calculating from left to right due to operator precedence. Instead, we use a stack-based approach to handle parentheses and different operator priorities. The core idea is to keep track of the running result and the sign for the next number.

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

Read the expression character by character.
If we encounter a number, keep building the full number by combining digits.
Once we have a complete number, add it to the running result, considering the current sign (positive or negative).
If we see a '+' sign, set the sign to positive (+1).
If we see a '-' sign, set the sign to negative (-1).
If we encounter an opening parenthesis '(', push the current result and the current sign onto the stack. Reset the result and sign as if starting a new calculation within the parentheses.
If we encounter a closing parenthesis ')', it means we've finished calculating the expression within the parentheses. Pop the sign and the previous result from the stack, then update the current result by multiplying with the sign and adding the previous result. This effectively incorporates the parentheses' result into the overall calculation.
Repeat the above steps until the entire expression is processed. The final result will be the evaluated value of the expression.

Code Implementation

def calculate_expression(expression):
    current_result = 0
    current_sign = 1
    stack = []
    number = 0

    for char in expression:
        if char.isdigit():
            number = number * 10 + int(char)
        elif char == '+':
            current_result += current_sign * number
            number = 0
            current_sign = 1

        elif char == '-':
            current_result += current_sign * number
            number = 0
            current_sign = -1

        elif char == '(': 
            # Save the current state before entering parenthesis
            stack.append(current_result)
            stack.append(current_sign)
            current_result = 0
            current_sign = 1

        elif char == ')':
            # Evaluate the expression within the parenthesis
            current_result += current_sign * number
            number = 0
            current_result *= stack.pop()
            current_result += stack.pop()

        else:
            continue

    return current_result + current_sign * number

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once, processing each character. Within the loop, operations such as number construction, sign updates, stack pushes, and stack pops take constant time. 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 results and signs when encountering opening parentheses. In the worst-case scenario, the expression could consist of nested parentheses and numbers, requiring the stack to grow proportionally to the number of nested parentheses. Therefore, the maximum size of the stack can be proportional to N, where N is the length of the input string representing the arithmetic expression. This stack is the primary driver of auxiliary space, leading to O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input string	Return 0 as the evaluated value for an empty expression.
String containing only whitespace	Remove whitespace before evaluating or return 0 if the string becomes empty after whitespace removal.
String with leading or trailing whitespace	Trim the string before processing to avoid incorrect parsing.
Nested parentheses	Use a stack-based approach to correctly handle the order of operations within parentheses.
Consecutive operators (+ or -)	Combine the operators, e.g., '--' becomes '+', '+-' becomes '-'.
Integer overflow	Use a data type that can handle larger numbers (e.g., long) and check for potential overflow during calculations, returning an error if necessary.
Missing operand before or after operator	Return an error or invalid result, or treat it as a zero operand where appropriate.
String contains invalid characters	Reject the string or ignore invalid characters and continue evaluating the rest, based on requirements.

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 characters other than digits, '+', '-', '(', ')', and space?
What is the expected range of integer values within the expression, and should I handle potential overflow?
Can the input string `s` be empty or null, and if so, what should I return?
Are nested parentheses allowed, and what is the maximum level of nesting?
Should I assume that the input expression is always valid, or do I need to handle invalid input cases such as mismatched parentheses or consecutive operators?

Brute Force Solution

Approach

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

Start at the beginning of the expression.
Read the expression character by character.
If you see a number, remember it; you are building the current number.
If you see an operation (like +, -, *, or /), store that operation to perform later.
Once you have both a number and an operation, perform that operation with the previous result (or 0 if it's the first number).
Store the new result.
Continue reading the expression, building numbers and performing operations as you go.
When you reach the end of the expression, the final result is what you've stored.

Code Implementation

def calculate_basic(expression):
    current_number = 0
    last_operation = '+'
    result = 0
    string_index = 0

    while string_index < len(expression):
        char = expression[string_index]

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

        if char in '+-*/' or string_index == len(expression) - 1:
            # Perform operation when an operator or end is encountered.
            if last_operation == '+':
                result += current_number
            elif last_operation == '-':
                result -= current_number
            elif last_operation == '*':
                result *= current_number
            elif last_operation == '/':
                # Integer division as per problem description
                result = int(result / current_number)

            last_operation = char
            current_number = 0

        string_index += 1

    # The final result is accumulated in the 'result' variable.
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Read the expression character by character.
If we encounter a number, keep building the full number by combining digits.
Once we have a complete number, add it to the running result, considering the current sign (positive or negative).
If we see a '+' sign, set the sign to positive (+1).
If we see a '-' sign, set the sign to negative (-1).
If we encounter an opening parenthesis '(', push the current result and the current sign onto the stack. Reset the result and sign as if starting a new calculation within the parentheses.
If we encounter a closing parenthesis ')', it means we've finished calculating the expression within the parentheses. Pop the sign and the previous result from the stack, then update the current result by multiplying with the sign and adding the previous result. This effectively incorporates the parentheses' result into the overall calculation.
Repeat the above steps until the entire expression is processed. The final result will be the evaluated value of the expression.

Code Implementation

def calculate_expression(expression):
    current_result = 0
    current_sign = 1
    stack = []
    number = 0

    for char in expression:
        if char.isdigit():
            number = number * 10 + int(char)
        elif char == '+':
            current_result += current_sign * number
            number = 0
            current_sign = 1

        elif char == '-':
            current_result += current_sign * number
            number = 0
            current_sign = -1

        elif char == '(': 
            # Save the current state before entering parenthesis
            stack.append(current_result)
            stack.append(current_sign)
            current_result = 0
            current_sign = 1

        elif char == ')':
            # Evaluate the expression within the parenthesis
            current_result += current_sign * number
            number = 0
            current_result *= stack.pop()
            current_result += stack.pop()

        else:
            continue

    return current_result + current_sign * number

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return 0 as the evaluated value for an empty expression.
String containing only whitespace	Remove whitespace before evaluating or return 0 if the string becomes empty after whitespace removal.
String with leading or trailing whitespace	Trim the string before processing to avoid incorrect parsing.
Nested parentheses	Use a stack-based approach to correctly handle the order of operations within parentheses.
Consecutive operators (+ or -)	Combine the operators, e.g., '--' becomes '+', '+-' becomes '-'.
Integer overflow	Use a data type that can handle larger numbers (e.g., long) and check for potential overflow during calculations, returning an error if necessary.
Missing operand before or after operator	Return an error or invalid result, or treat it as a zero operand where appropriate.
String contains invalid characters	Reject the string or ignore invalid characters and continue evaluating the rest, based on requirements.