439. Ternary Expression Parser

MediumStackRecursionString
Leetcode Link

Problem Description

The problem requires us to evaluate a ternary expression given as a string. A ternary expression is of the form "X ? Y : Z" which means "if X is true, then Y, otherwise Z". The expression provided will be a nested ternary expression where the result of one ternary can be a condition for other ternaries. The challenge is to process the expression which may be heavily nested and produce a single output.

An expression can only contain one-digit numbers, 'T' for true, 'F' for false, '?' as a delimiter between condition and true case, and ':' as a delimiter between true case and false case. Expressions are evaluated from right to left, and we are ensured the expression is always valid.

For example, given an expression "T?T?F:5:3", the result of evaluating this expression should be "F", as we evaluate "T?F:5" first which yields "F", then "T?F:3" which yields "F".

Intuition

The intuition behind the solution comes from understanding how a stack can help in evaluating nested expressions. A stack is a simple data structure that allows us to add elements to the top and remove elements from the top; Last-In, First-Out (LIFO). We reverse the expression and iterate over it, using a stack to keep track of operands and operators. When we encounter a number or 'T'/'F', we push it onto the stack. When we encounter a '?', we know the top two elements on the stack are operands for the ternary operation, and we evaluate them based on the condition just before the '?'. We throw away the false case and keep only the true case result on the stack right away as the problem simplifies to evaluating the rightmost expression first due to the right-to-left grouping.

By continuously evaluating the ternary operations as we encounter them and keeping track of results on the stack, by the time we reach the beginning of the expression (since we iterate from the end), we should have the final result on top of the stack.

The provided solution algorithm correctly implements this intuition. When a ':' is encountered, it is simply ignored because our stack already contains the operands it needs. The '?' indicates that an evaluation must be performed. If the condition is 'T', we pop once from the stack to discard the false case and the top of the stack now becomes the true case (which is our result). If the condition is 'F', we pop twice to discard the true case and then the false case becomes our result. Either way, we reset the cond flag to False until the next '?' is encountered.

Learn more about Stack and Recursion patterns.

Solution Approach

The solution uses a stack data structure to evaluate the expression in a right-to-left manner, which is suitable for the right-to-left grouping nature of ternary expressions. The algorithm proceeds as follows:

  1. Initialize an empty stack called stk.
  2. Initialize a boolean variable cond as False. This variable will be used as a flag to know when we're ready to evaluate a ternary expression.
  3. Reverse the input expression and iterate over it character by character using a for-loop. Reversing is crucial because the conditions and their corresponding true-false values are pushed onto the stack in such a way that they can be popped off in the correct order when evaluating.
  4. Ignore the case when the current character is a ':'. This character simply separates the true and false case, which we don't need to keep track of since the stack already contains the necessary cases for evaluation.
  5. When the current character is a '?', set the cond flag to True. This indicates that the next non-':' character will be a condition whose result determines which of the two values on top of the stack to keep.
  6. For any other character (which could be a digit, 'T', or 'F'):
    • If cond is True, this means the current character is a condition (either 'T' or 'F'). Based on its value:
      • If the condition is 'T', pop once from the stack to remove the false case (as it is not needed) and the remaining top is the true case, which becomes our result for the current ternary.
      • If the condition is 'F', pop twice from the stack; once to remove the true case and once to remove the false case and then append this false case back onto the stack, as it is the result of the ternary.
    • If cond is False, append the current character onto the stack because it's a value, not a condition.
    • Reset the cond flag to False after the conditional check, since the ternary expression has been evaluated and the result is on the stack.
  7. Continue the above process until the entire string has been iterated over. Since the evaluation is always complete right after a '?' or when a value is encountered (and the stack is not ready for evaluation), the top of the stack at the end of the iteration will hold the final result.
  8. Return the top of the stack, which is the evaluated result of the entire expression.

Through this implementation, we effectively mimic the parsing and evaluating of a nested ternary expression while using the stack to keep track of pending operations. Each character in the reversed string contributes to the formation of the expression as the ternary operations are resolved.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the ternary expression "F?1:T?4:5".

Following the solution approach:

  1. A stack stk is initialized as empty.

  2. A boolean variable cond is initialized as False.

  3. Reverse the expression to "5:4?T:1?F".

  4. Iterating over the reversed expression:

    • '5' is encountered: cond is False, so '5' is pushed onto stk.
    • ':' is a separator, so we do nothing.
    • '4' is encountered next: cond is False, push '4' onto stk.
    • '?' is encountered: cond is set to True, indicating that the next non-':' character will be a condition.
    • 'T' is a condition: Since cond is True and the condition is 'T', pop once from stk (remove '5'), so '4' is the result for this ternary operation. Reset cond to False.
    • ':' is another separator, do nothing.
    • '1' is encountered: cond is False, push '1' onto stk.
    • '?' is encountered: Set cond to True.
    • 'F' is a condition: Now, cond is True and the condition is 'F'. Pop twice from stk to remove '4' (true case) and '1' (false case), then push '1' back onto stk, as it is the result of this ternary. Reset cond to False.

  5. At the end of the iteration, the stack stk has one element, which is '1', the evaluated result of the entire expression.

Therefore, the given ternary expression "F?1:T?4:5" evaluates to '1'.

Solution Implementation

1class Solution:
2    def parseTernary(self, expression: str) -> str:
3        # Initialize a stack to keep track of characters and results.
4        stack = []
5        # This variable is used as a flag to know when a condition (T or F) is encountered
6        is_condition = False
7
8        # Loop through the expression in reverse order.
9        for char in expression[::-1]:
10            # Skip over the ':' character as it's just a separator.
11            if char == ':':
12                continue
13            # If we encounter a '?', we know the next character is a condition (T or F).
14            if char == '?':
15                is_condition = True
16            else:
17                # If we're dealing with a condition, resolve the ternary operation.
18                if is_condition:
19                    # If the condition is 'T' (true), pop and use the first result (left-hand operand).
20                    if char == 'T':
21                        true_result = stack.pop()
22                        # Pop and discard the second result (right-hand operand) as it's not needed.
23                        stack.pop()
24                        stack.append(true_result)
25                    # If condition is 'F' (false), skip the first result and pop the second (right-hand operand).
26                    else:
27                        stack.pop()
28                        false_result = stack.pop()
29                        stack.append(false_result)
30                    # Reset the condition flag as we've resolved this ternary operation.
31                    is_condition = False
32                else:
33                    # If we're not handling a condition, push the character onto the stack.
34                    stack.append(char)
35        # The final result will be at the top of the stack, so return it.
36        return stack[0]
37
1import java.util.Deque;
2import java.util.ArrayDeque;
3
4class Solution {
5
6    // Method to parse the given ternary expression and return the result as a string
7    public String parseTernary(String expression) {
8        // Initialize a stack to help evaluate the ternary expressions from right to left
9        Deque<Character> stack = new ArrayDeque<>();
10        // Variable to keep track of when the '?' symbol is encountered, indicating a condition
11        boolean isCondition = false;
12
13        // Iterate over the expression from end to start
14        for (int i = expression.length() - 1; i >= 0; i--) {
15            char currentChar = expression.charAt(i);
16            if (currentChar == ':') {
17                continue; // Skip ':' as it does not affect stack operations
18            }
19            if (currentChar == '?') {
20                isCondition = true; // Set the condition flag upon finding '?'
21            } else {
22                if (isCondition) {
23                    // Evaluate the ternary condition based on the current character 'T' or 'F'
24                    if (currentChar == 'T') {
25                        // If condition is true, pop and keep the first value
26                        char trueValue = stack.pop();
27                        stack.pop(); // Discard the false value
28                        stack.push(trueValue); // Push the true value back onto the stack
29                    } else {
30                        // If condition is false, simply discard the true value
31                        stack.pop(); // Discard the true value
32                        // The top now contains the false value, which is the desired result
33                    }
34                    isCondition = false; // Reset condition flag for the next evaluation
35                } else {
36                    // Push the current character onto the stack if not part of a condition
37                    stack.push(currentChar);
38                }
39            }
40        }
41        // The top of the stack now contains the result of the ternary expression
42        return String.valueOf(stack.peek());
43    }
44}
45
1#include <algorithm>
2#include <string>
3
4class Solution {
5public:
6    // Function to parse a ternary expression and return the resulting string.
7    string parseTernary(string expression) {
8        // Use a string as a stack to keep track of the characters.
9        string stack;
10      
11        // A flag to know when we're evaluating a condition.
12        bool isCondition = false;
13      
14        // Reverse the expression to evaluate it from right to left.
15        std::reverse(expression.begin(), expression.end());
16      
17        // Iterate through each character of the reversed expression.
18        for (char& currentChar : expression) {
19            if (currentChar == ':') {
20                // Ignore colons as they only separate expressions, not required in evaluation.
21                continue;
22            }
23            if (currentChar == '?') {
24                // If we find a '?', the next character is a condition.
25                isCondition = true;
26            } else {
27                if (isCondition) {
28                    // If we're at a condition, check if it is 'T' (True).
29                    if (currentChar == 'T') {
30                        // If True, pop the false result and keep the true result.
31                        char trueResult = stack.back();
32                        stack.pop_back();
33                        stack.pop_back(); // Remove the false result.
34                        stack.push_back(trueResult); // Keep the true result.
35                    } else {
36                        // If False ('F'), remove the true result, keeping the false one.
37                        stack.pop_back(); // The true result is removed.
38                    }
39                    isCondition = false; // Reset the flag as we've resolved the condition.
40                } else {
41                    // If it's a regular character, add it to the stack.
42                    stack.push_back(currentChar);
43                }
44            }
45        }
46      
47        // The final result will be at the top of the stack.
48        return {stack.back()};
49    }
50};
51
1function parseTernary(expression: string): string {
2    // A stack to hold the characters for processing the expression
3    let stack: string[] = [];
4
5    // Variable to mark whether we are evaluating a condition
6    let evaluatingCondition: boolean = false;
7
8    // Reverse the expression to evaluate from right to left
9    let reversedExpression: string = expression.split('').reverse().join('');
10
11    // Iterate through each character of the reversed expression
12    for (let i = 0; i < reversedExpression.length; i++) {
13        let currentChar: string = reversedExpression[i];
14
15        if (currentChar === ':') {
16            // Colons are separators and do not affect the evaluation
17            continue;
18        } else if (currentChar === '?') {
19            // The next character is a condition
20            evaluatingCondition = true;
21        } else {
22            if (evaluatingCondition) {
23                // If evaluating a condition, check if it's 'T' for True
24                if (currentChar === 'T') {
25                    // If True, the top of the stack is the true result, pop and discard the next (false) result
26                    let trueResult: string = stack.pop()!;
27                    stack.pop(); // Remove the false result
28                    stack.push(trueResult); // Push the true result back onto the stack
29                } else {
30                    // If False ('F'), simply pop the true result leaving the false one at the top of the stack
31                    stack.pop(); // The true result is discarded
32                }
33                // Reset evaluating condition flag after processing
34                evaluatingCondition = false;
35            } else {
36                // If it's not a condition, push the character onto the stack for later evaluation
37                stack.push(currentChar);
38            }
39        }
40    }
41
42    // The final result will be at the top of the stack
43    return stack.pop()!;
44}
45
46// Example usage
47// const result = parseTernary("T?2:3"); // Should return "2"
48

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the input string expression. This complexity arises because the code traverses the entire input in reverse once, performing a constant amount of work for each character. Each character is processed only once and the operations inside the loop (like pop and append on the stack) are O(1).

The space complexity of the code is also O(n). In the worst case, all characters besides ":" and "?" might end up on the stack, which means the stack can grow up to the size of the input string when the conditional expressions are nested but always evaluating to the false branch (e.g., "F?F?F?...:a:a:a"). However, in most cases, the stack will contain fewer elements than n.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Want a Structured Path to Master System Design Too? Don’t Miss This!