439

439. Ternary Expression Parser (Medium)

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

You can always assume that the given expression is valid and only contains digits, '?', ':', 'T', and 'F' where 'T' is true and 'F' is false. All the numbers in the expression are one-digit numbers (i.e., in the range [0, 9]).

The conditional expressions group right-to-left (as usual in most languages), and the result of the expression will always evaluate to either a digit, 'T' or 'F'.

 

Example 1:

Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

Input: expression = "F?1:T?4:5"
Output: "4"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
"(F ? 1 : (T ? 4 : 5))" --> "(F ? 1 : 4)" --> "4"
or "(F ? 1 : (T ? 4 : 5))" --> "(T ? 4 : 5)" --> "4"

Example 3:

Input: expression = "T?T?F:5:3"
Output: "F"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
"(T ? (T ? F : 5) : 3)" --> "(T ? F : 3)" --> "F"
"(T ? (T ? F : 5) : 3)" --> "(T ? F : 5)" --> "F"

 

Constraints:

• 5 <= expression.length <= 104
• expression consists of digits, 'T', 'F', '?', and ':'.
• It is guaranteed that expression is a valid ternary expression and that each number is a one-digit number.

Companies:
Snapchat

Related Topics:
String, Stack, Recursion

Similar Questions:

• Mini Parser (Medium)
• Remove Comments (Medium)
• Parse Lisp Expression (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/ternary-expression-parser/
// Author: github.com/lzl124631x
// Time: O(NL) where L is the level of nesting
// Space: O(NL)
class Solution {
public:
    string parseTernary(string s) {
        if (s.size() == 1) return s;
        bool left = s[0] == 'T';
        int cnt = 0, N = s.size(), i = 2;
        for (; i < N && cnt >= 0; ++i) {
            if (s[i] == '?') ++cnt;
            else if (s[i] == ':') --cnt;
        }
        return parseTernary(left ? s.substr(2, i - 3) : s.substr(i));
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/ternary-expression-parser
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(L) where L is the level of nesting
class Solution {
public:
    string parseTernary(string s) {
        int i = 0, N = s.size();
        function<string()> parse = [&]() {
            if (i == N - 1 || s[i + 1] == ':') {
                return s.substr(i++, 1);
            }
            bool b = s[i] == 'T';
            i += 2;
            auto left = parse();
            ++i;
            auto right = parse();
            return b ? left : right;
        };
        return parse();
    }
};