Jobs

Interviews

Discussions

Ternary Expression Parser

Medium

Asked by:

2 views

Topics:

ArraysRecursionStrings

Given a string representing arbitrarily nested ternary expressions, evaluate the expression and return the result.

You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).

Note:

The length of the given string is ≤ 10000.
Each number will contain only one digit.
The conditional expressions group right-to-left (as usual in most languages).

Example 1:

Input: "T?2:3"

Output: "2"

Explanation: If true, result is 2; otherwise result is 3.

Example 2:

Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, the input is parsed as: "F?1:(T?4:5)" --> "F?1:4" --> "4".

Example 3:

Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, the input is parsed as: "T?(T?F:5):3" --> "T?F:3" --> "F".

Try coding it in LeetCode

Ternary Expression Parser

Medium

Asked by:

2 views

Topics:

ArraysRecursionStrings

Given a string representing arbitrarily nested ternary expressions, evaluate the expression and return the result.

You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).

Note:

The length of the given string is ≤ 10000.
Each number will contain only one digit.
The conditional expressions group right-to-left (as usual in most languages).

Example 1:

Input: "T?2:3"

Output: "2"

Explanation: If true, result is 2; otherwise result is 3.

Example 2:

Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, the input is parsed as: "F?1:(T?4:5)" --> "F?1:4" --> "4".

Example 3:

Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, the input is parsed as: "T?(T?F:5):3" --> "T?F:3" --> "F".

Try coding it in LeetCode

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 you provide examples of valid ternary expressions, especially those with nested '?' and ':' operators?
What should I return if the input string is empty or null?
Is the input expression guaranteed to be valid, meaning it will always have a '?' and ':' pair for every 'T' or 'F' condition, and will the result of each evaluation be a single character?
Besides digits, 'T', 'F', '?', and ':', are there any other characters that might appear in the input string?
By 'digit', do you mean single-digit numbers (0-9) represented as characters, or could 'digits' potentially refer to multi-digit numbers represented as substrings within the expression?

Brute Force Solution

Approach

The brute force way to evaluate a ternary expression is to explore every possible interpretation. Think of it as trying every combination of true and false answers to the conditions until we find one that fits. We keep simplifying the expression step by step until we arrive at a single value.

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

Start by looking at the beginning of the ternary expression.
Check the first part of the expression, which should be the condition.
Consider both possibilities: what if the condition is true, and what if the condition is false?
If the condition is true, ignore the 'false' part of the expression and focus on the 'true' part.
If the condition is false, ignore the 'true' part and focus on the 'false' part.
Now, within the part you're focusing on, check if there are more ternary expressions.
If there are, repeat the process of checking the condition and choosing the 'true' or 'false' part.
Keep doing this until you get to a simple value, like a number or letter, which is the result of the expression.
Go back and check if we missed any other possibilities in any of the conditions we encountered.
If there were other possibilities, explore them too and see what final result they lead to.
Once you have explored ALL possibilities, pick the very first result you found as the outcome.

Code Implementation

def solve_ternary_brute_force(expression):

    results = []

    def evaluate(current_expression):
        if len(current_expression) == 1:
            results.append(current_expression)
            return

        # Find the first '?' to identify a ternary operation.
        question_mark_index = current_expression.find('?')

        if question_mark_index == -1:
            results.append(current_expression)
            return

        condition = current_expression[:question_mark_index]

        # Determine the indices of the true and false parts
        colon_index = current_expression.find(':')
        true_expression = current_expression[question_mark_index + 1:colon_index]
        false_expression = current_expression[colon_index + 1:]

        # Explore the 'true' branch.
        evaluate(true_expression)

        # Explore the 'false' branch.
        evaluate(false_expression)

    evaluate(expression)

    #Return the first result found from all possible paths
    return results[0]

Big(O) Analysis

Time Complexity

O(3^n) – The brute force approach explores all possible interpretations of the ternary expression, essentially creating a decision tree. Each ternary operator introduces a branch with three possibilities: evaluate the condition, evaluate the 'true' branch, or evaluate the 'false' branch. In the worst case, where the expression is a chain of nested ternary operators of length n, the algorithm explores approximately 3^n possibilities. Thus, the time complexity grows exponentially with the length of the expression.

Space Complexity

O(N) – The algorithm explores every possible interpretation of the ternary expression, potentially leading to recursive calls. In the worst-case scenario, the ternary expression might be deeply nested, resulting in a call stack depth proportional to the length of the expression, N. Therefore, the space complexity due to the recursion stack is O(N), where N is the length of the ternary expression. No other significant auxiliary space is used beyond the call stack.

Optimal Solution

Approach

The most efficient way to parse a ternary expression is to work from right to left using a special data structure. This approach allows us to solve smaller parts of the expression first and combine them to solve the bigger expression without redundant calculations.

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

Start at the far right end of the expression.
Use a stack (like a pile where you add and remove from the top) to keep track of the parts of the expression we've already seen.
Read the expression from right to left, one character at a time.
When you find a value (a number or a letter), put it on top of the stack.
When you find a '?', it means you've found a ternary operation. You now need to evaluate it.
Take the two values from the top of the stack. These are the 'then' and 'else' values of the ternary operation.
Also take the condition value from the top of the stack.
Evaluate the condition: if it's true, pick the 'then' value; otherwise, pick the 'else' value.
Put the result of this operation back on top of the stack.
Keep going from right to left, repeating these steps until you reach the beginning of the expression.
At the end, the final result will be the only value left on the stack.

Code Implementation

def ternary_expression_parser(expression):
    stack = []
    index = len(expression) - 1

    while index >= 0:
        character = expression[index]

        if character.isalnum():
            stack.append(character)
        elif character == '?':
            # Found a ternary operation, evaluate it.
            false_value = stack.pop()
            true_value = stack.pop()
            index -= 1  # Skip the ':' character

            condition = stack.pop()

            # Evaluate the condition and push result.
            if condition != '0':
                stack.append(true_value)
            else:
                stack.append(false_value)
        index -= 1

    # The final result is left on the stack.
    return stack[0]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the ternary expression of length n exactly once, from right to left. Within the loop, it performs constant-time operations such as stack pushes, stack pops, and conditional evaluations. The number of these operations is directly proportional to the length of the input string, therefore the time complexity is O(n).

Space Complexity

O(N) – The algorithm utilizes a stack to store intermediate values encountered while parsing the ternary expression from right to left. In the worst-case scenario, where the expression consists of nested ternary operations, the stack could potentially hold all the operands present in the expression before any evaluation takes place. Therefore, the auxiliary space used by the stack scales linearly with the input size N, where N is the length of the ternary expression. Hence, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or throw an IllegalArgumentException, depending on requirements, to indicate invalid input.
Single character input (e.g., 'T', '1')	Return the single character as it is already evaluated.
Invalid characters in the input (e.g., 'A', '$')	Throw an IllegalArgumentException to indicate invalid ternary expression format.
Unbalanced '?' and ':' operators (e.g., 'T?1')	Throw an IllegalArgumentException because the ternary expression is incomplete and cannot be evaluated.
Input string with only 'T' and '?' (e.g., 'T?T?1:0')	The algorithm should correctly evaluate based on the 'T' values, selecting the correct branches recursively.
Deeply nested expressions causing stack overflow with a recursive solution	Consider using an iterative approach with a stack data structure to prevent stack overflow errors for very large expressions.
Leading or trailing whitespace in input	Trim the input string before processing to avoid unexpected behavior.
Large numerical values in the ternary expression	The solution should handle large digits (as string) without causing integer overflow during processing, as we return a string.

Null or empty input string

How to Handle:

Return an empty string or throw an IllegalArgumentException, depending on requirements, to indicate invalid input.

Single character input (e.g., 'T', '1')

How to Handle:

Return the single character as it is already evaluated.

Invalid characters in the input (e.g., 'A', '$')

How to Handle:

Throw an IllegalArgumentException to indicate invalid ternary expression format.

Unbalanced '?' and ':' operators (e.g., 'T?1')

How to Handle:

Throw an IllegalArgumentException because the ternary expression is incomplete and cannot be evaluated.

Input string with only 'T' and '?' (e.g., 'T?T?1:0')

How to Handle:

The algorithm should correctly evaluate based on the 'T' values, selecting the correct branches recursively.

Deeply nested expressions causing stack overflow with a recursive solution

How to Handle:

Consider using an iterative approach with a stack data structure to prevent stack overflow errors for very large expressions.

Leading or trailing whitespace in input

How to Handle:

Trim the input string before processing to avoid unexpected behavior.

Large numerical values in the ternary expression

How to Handle:

The solution should handle large digits (as string) without causing integer overflow during processing, as we return a string.

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 you provide examples of valid ternary expressions, especially those with nested '?' and ':' operators?
What should I return if the input string is empty or null?
Is the input expression guaranteed to be valid, meaning it will always have a '?' and ':' pair for every 'T' or 'F' condition, and will the result of each evaluation be a single character?
Besides digits, 'T', 'F', '?', and ':', are there any other characters that might appear in the input string?
By 'digit', do you mean single-digit numbers (0-9) represented as characters, or could 'digits' potentially refer to multi-digit numbers represented as substrings within the expression?

Brute Force Solution

Approach

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

Start by looking at the beginning of the ternary expression.
Check the first part of the expression, which should be the condition.
Consider both possibilities: what if the condition is true, and what if the condition is false?
If the condition is true, ignore the 'false' part of the expression and focus on the 'true' part.
If the condition is false, ignore the 'true' part and focus on the 'false' part.
Now, within the part you're focusing on, check if there are more ternary expressions.
If there are, repeat the process of checking the condition and choosing the 'true' or 'false' part.
Keep doing this until you get to a simple value, like a number or letter, which is the result of the expression.
Go back and check if we missed any other possibilities in any of the conditions we encountered.
If there were other possibilities, explore them too and see what final result they lead to.
Once you have explored ALL possibilities, pick the very first result you found as the outcome.

Code Implementation

def solve_ternary_brute_force(expression):

    results = []

    def evaluate(current_expression):
        if len(current_expression) == 1:
            results.append(current_expression)
            return

        # Find the first '?' to identify a ternary operation.
        question_mark_index = current_expression.find('?')

        if question_mark_index == -1:
            results.append(current_expression)
            return

        condition = current_expression[:question_mark_index]

        # Determine the indices of the true and false parts
        colon_index = current_expression.find(':')
        true_expression = current_expression[question_mark_index + 1:colon_index]
        false_expression = current_expression[colon_index + 1:]

        # Explore the 'true' branch.
        evaluate(true_expression)

        # Explore the 'false' branch.
        evaluate(false_expression)

    evaluate(expression)

    #Return the first result found from all possible paths
    return results[0]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the far right end of the expression.
Use a stack (like a pile where you add and remove from the top) to keep track of the parts of the expression we've already seen.
Read the expression from right to left, one character at a time.
When you find a value (a number or a letter), put it on top of the stack.
When you find a '?', it means you've found a ternary operation. You now need to evaluate it.
Take the two values from the top of the stack. These are the 'then' and 'else' values of the ternary operation.
Also take the condition value from the top of the stack.
Evaluate the condition: if it's true, pick the 'then' value; otherwise, pick the 'else' value.
Put the result of this operation back on top of the stack.
Keep going from right to left, repeating these steps until you reach the beginning of the expression.
At the end, the final result will be the only value left on the stack.

Code Implementation

def ternary_expression_parser(expression):
    stack = []
    index = len(expression) - 1

    while index >= 0:
        character = expression[index]

        if character.isalnum():
            stack.append(character)
        elif character == '?':
            # Found a ternary operation, evaluate it.
            false_value = stack.pop()
            true_value = stack.pop()
            index -= 1  # Skip the ':' character

            condition = stack.pop()

            # Evaluate the condition and push result.
            if condition != '0':
                stack.append(true_value)
            else:
                stack.append(false_value)
        index -= 1

    # The final result is left on the stack.
    return stack[0]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or throw an IllegalArgumentException, depending on requirements, to indicate invalid input.
Single character input (e.g., 'T', '1')	Return the single character as it is already evaluated.
Invalid characters in the input (e.g., 'A', '$')	Throw an IllegalArgumentException to indicate invalid ternary expression format.
Unbalanced '?' and ':' operators (e.g., 'T?1')	Throw an IllegalArgumentException because the ternary expression is incomplete and cannot be evaluated.
Input string with only 'T' and '?' (e.g., 'T?T?1:0')	The algorithm should correctly evaluate based on the 'T' values, selecting the correct branches recursively.
Deeply nested expressions causing stack overflow with a recursive solution	Consider using an iterative approach with a stack data structure to prevent stack overflow errors for very large expressions.
Leading or trailing whitespace in input	Trim the input string before processing to avoid unexpected behavior.
Large numerical values in the ternary expression	The solution should handle large digits (as string) without causing integer overflow during processing, as we return a string.

Null or empty input string

How to Handle:

Return an empty string or throw an IllegalArgumentException, depending on requirements, to indicate invalid input.

Single character input (e.g., 'T', '1')

How to Handle:

Return the single character as it is already evaluated.

Invalid characters in the input (e.g., 'A', '$')

How to Handle:

Throw an IllegalArgumentException to indicate invalid ternary expression format.

Unbalanced '?' and ':' operators (e.g., 'T?1')

How to Handle:

Throw an IllegalArgumentException because the ternary expression is incomplete and cannot be evaluated.

Input string with only 'T' and '?' (e.g., 'T?T?1:0')

How to Handle:

The algorithm should correctly evaluate based on the 'T' values, selecting the correct branches recursively.

Deeply nested expressions causing stack overflow with a recursive solution

How to Handle:

Consider using an iterative approach with a stack data structure to prevent stack overflow errors for very large expressions.

Leading or trailing whitespace in input

How to Handle:

Trim the input string before processing to avoid unexpected behavior.

Large numerical values in the ternary expression

How to Handle:

The solution should handle large digits (as string) without causing integer overflow during processing, as we return a string.