Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/439.html
439. Ternary Expression Parser
Level
Medium
Description
Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. 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).
- The condition will always be either
T
orF
. That is, the condition will never be a digit. - The result of the expression will always evaluate to either a digit
0-9
,T
orF
.
Example 1:
Input: "T?2:3"
Output: "2"
Explanation: If true, then 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, it is read/evaluated as:
"(F ? 1 : (T ? 4 : 5))" "(F ? 1 : (T ? 4 : 5))"
-> "(F ? 1 : 4)" or -> "(T ? 4 : 5)"
-> "4" -> "4"
Example 3:
Input: "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 ? (T ? F : 5) : 3)"
-> "(T ? F : 3)" or -> "(T ? F : 5)"
-> "F" -> "F"
Solution
Use two stacks stack1
and stack2
to store the characters in expression
. Loop over expression
from left to right and add each character into stack1
.
While stack1
contains more than one element, do operation on stack1
. Each time pop two elements c1
and c2
from stack1
, where c1
must be a digit or a boolean letter, and c2
must be a ?
or :
. If c2
is :
, then there will be more elements before meeting a ?
, so push c1
into stack2
. If c2
is ?
, then pop one more element from stack1
, which must be a boolean letter. If the boolean letter is T
, then c1
is the result of the current ternary expression. Otherwise, the top element of stack2
is the result of the current ternary expression. Pop one element from stack2
and push the result of the current ternary expression into stack1
. Repeat the process until there is only one element in stack1
.
Finally, pop the one element from stack1
, convert it into a string and return.
-
class Solution { public String parseTernary(String expression) { Stack<Character> stack1 = new Stack<Character>(); Stack<Character> stack2 = new Stack<Character>(); int length = expression.length(); for (int i = 0; i < length; i++) stack1.push(expression.charAt(i)); while (stack1.size() > 1) { char c1 = stack1.pop(); char c2 = stack1.pop(); if (c2 == ':') stack2.push(c1); else { char conditionChar = stack1.pop(); boolean condition = conditionChar == 'T'; char nextChar = condition ? c1 : stack2.peek(); stack2.pop(); stack1.push(nextChar); } } String value = String.valueOf(stack1.pop()); return value; } }
-
// OJ: https://leetcode.com/problems/ternary-expression-parser/ // 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)); } };
-
class Solution(object): def parseTernary(self, expression): """ :type expression: str :rtype: str """ stack = [] i = len(expression) - 1 while i >= 0: if expression[i] not in ["?", ":"]: stack.append(expression[i]) elif expression[i] == "?": i -= 1 if expression[i] == "T": top = stack.pop() stack.pop() stack.append(top) elif expression[i] == "F": stack.pop() i -= 1 return stack[0]
-
func parseTernary(expression string) string { stk := []byte{} cond := false for i := len(expression) - 1; i >= 0; i-- { c := expression[i] if c == ':' { continue } if c == '?' { cond = true } else { if cond { if c == 'T' { x := stk[len(stk)-1] stk = stk[:len(stk)-2] stk = append(stk, x) } else { stk = stk[:len(stk)-1] } cond = false } else { stk = append(stk, c) } } } return string(stk[0]) }