## Monday, October 24, 2016

### LeetCode 439 - Ternary Expression Parser

Related: Pocket Gems - Ternary Expression to Binary Tree
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:
1. The length of the given string is ≤ 10000.
2. Each number will contain only one digit.
3. The conditional expressions group right-to-left (as usual in most languages).
4. The condition will always be either `T` or `F`. That is, the condition will never be a digit.
5. The result of the expression will always evaluate to either a digit `0-9``T` or `F`.
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"```
X.
https://segmentfault.com/a/1190000008939830

``````    public String parseTernary(String expression) {
if(expression == null || expression.length() == 0) return "";

for(int i=expression.length()-1; i >= 0; i--){
char c = expression.charAt(i);
if(!stk.isEmpty() && stk.peek() == '?'){
stk.pop();  // pop ?
char first = stk.pop();
stk.pop(); // pop :
char second = stk.pop();

if(c == 'T') stk.push(first);
else stk.push(second);
} else {
stk.push(c);
}
}

return String.valueOf(stk.peek());
}``````
https://discuss.leetcode.com/topic/64409/very-easy-1-pass-stack-solution-in-java-no-string-concat
Iterate the expression from tail, whenever encounter a character before '?', calculate the right value and push back to stack.
P.S. this code is guaranteed only if "the given expression is valid" base on the requirement.
``````public String parseTernary(String expression) {
if (expression == null || expression.length() == 0) return "";

for (int i = expression.length() - 1; i >= 0; i--) {
char c = expression.charAt(i);
if (!stack.isEmpty() && stack.peek() == '?') {

stack.pop(); //pop '?'
char first = stack.pop();
stack.pop(); //pop ':'
char second = stack.pop();

if (c == 'T') stack.push(first);
else stack.push(second);
} else {
stack.push(c);
}
}

return String.valueOf(stack.peek());
}``````
https://discuss.leetcode.com/topic/64512/java-short-clean-code-no-stack

https://discuss.leetcode.com/topic/64524/short-python-solutions-one-o-n

Collect chars from back to front on a stack, evaluate ternary sub-expressions as soon as possible:
``````def parseTernary(self, expression):
stack = []
for c in reversed(expression):
stack.append(c)
if stack[-2:-1] == ['?']:
stack[-5:] = stack[-3 if stack[-1] == 'T' else -5]
return stack[0]
``````
Originally my check was `stack[-4::2] == [':', '?']`, but @YJL1228's is right, looking for `?` is enough.
https://discuss.leetcode.com/topic/64389/easy-and-concise-5-lines-python-java-solution
The time complexity seems very high(may be O(n^2)). Using lastIndexOf means that u need to scan the whole String each loop, which costs a lot of time.
``````    public String parseTernary(String expression) {
while (expression.length() != 1) {
int i = expression.lastIndexOf("?");    // get the last shown '?'
char tmp;
if (expression.charAt(i-1) == 'T') { tmp = expression.charAt(i+1); }
else { tmp = expression.charAt(i+3); }
expression = expression.substring(0, i-1) + tmp + expression.substring(i+4);
}
return expression;
}``````

X. Recursion

? : 所组成的最小单位，可以看作一对括号。 ？类似（， ：类似 ）。

https://discuss.leetcode.com/topic/68336/5ms-java-dfs-solution
https://yijiajin.github.io/leetcode/2017/01/11/LC439.-Ternary-Expression-Parser/
The key idea is to find the legitimate `:` separating two "values".
This `:` has the property that the number of `?` ahead of this `:` should equals the number of `:`, similar to the case of `(` and `)`.
Only problem is the time complexity is up to O(n^2) in the worse case.
For example, T?T?T?T?T?1:2:3:4:5:6.
``````    public String parseTernary(String expression) {
if(expression == null || expression.length() == 0){
return expression;
}
char[] exp = expression.toCharArray();

return DFS(exp, 0, exp.length - 1) + "";

}
public char DFS(char[] c, int start, int end){
if(start == end){
return c[start];
}
int count = 0, i =start;
for(; i <= end; i++){
if(c[i] == '?'){
count ++;
}else if (c[i] == ':'){
count --;
if(count == 0){
break;
}
}
}
return c[start] == 'T'? DFS(c, start + 2, i - 1) : DFS(c, i+1,end);
}``````
https://discuss.leetcode.com/topic/64389/easy-and-concise-5-lines-python-java-solution
To avoid use lastIndexOf, we can easily scan through whole string at first. I've added modified version below, however it costs extra 3 lines.
``````    def parseTernary(self, expression):
# begin with the last question.
idx = []
for i in xrange(len(expression)):
if expression[i] == "?": idx += i,
while len(expression) != 1:
j = idx.pop()
tmp = expression[j+1] if expression[j-1] == 'T' else expression[j+3]
expression = expression[:j-1] + tmp + expression[j+4:]

return expression``````
http://hongzheng.me/leetcode/leetcode-439-ternary-expression-parser/

http://www.voidcn.com/blog/zqh_1991/article/p-6244665.html
```    string parseTernary(string expression) {
int len=expression.size();
if(len==1) return expression;
int count1=0,count2=0;
for(int i=0;i<len;i++) {
if(expression[i]=='?') {
count1++;
}
else if(expression[i]==':') {
count2++;
if(count1==count2) {
if(expression[0]=='T') {
return parseTernary(expression.substr(2,i-2));  //表达式的左边
}
else return parseTernary(expression.substr(i+1));   //表达式的右边
}
}
}
return "";
}```

X. Build express tree
https://scottduan.gitbooks.io/leetcode-review/ternary_expression_parser.html
Let's assume the input ternary expression is valid, we can build the tree in preorder manner.
Each time we scan two characters, the first character is either ? or :, the second character holds the value of the tree node. When we see ?, we add the new node to left. When we see :, we need to find out the ancestor node that doesn't have a right node, and make the new node as its right child.
``````public TreeNode convert(char[] expr) {
if (expr.length == 0) {
return null;
}

TreeNode root = new TreeNode(expr[0]);

Stack<TreeNode> stack = new Stack<>();

for (int i = 1; i < expr.length; i += 2) {
TreeNode node = new TreeNode(expr[i + 1]);

if (expr[i] == '?') {
stack.peek().left = node;
}

if (expr[i] == ':') {
stack.pop();
while (stack.peek().right != null) {
stack.pop();
}
stack.peek().right = node;
}

stack.push(node);
}

return root;
}``````
https://discuss.leetcode.com/topic/64397/java-o-n-using-binary-tree
``````    public String parseTernary(String expression) {
if(expression == null || expression.length() == 0) return "";
Node root = buildTree(expression.toCharArray());
return evaluate(root) + "";
}
static class Node {
char val;
Node left;
Node right;
Node parent;

public Node(char c) {
val = c;
left = null;
right = null;
parent = null;
}
}
private static Node buildTree(char[] ch) {
Node root = new Node(ch[0]);
Node node = root;
for(int i = 1; i < ch.length; i++) {
if(ch[i] == '?') {
Node left = new Node(ch[i + 1]);
node.left = left;
left.parent = node;
node = node.left;
}
else if(ch[i] == ':') {
node = node.parent;
while(node.right != null && node.parent != null) {
node = node.parent;
}
Node right = new Node(ch[i + 1]);
node.right = right;
right.parent = node;
node = node.right;
}
}
return root;
}
private static char evaluate(Node root) {
while(root.val == 'T' || root.val == 'F') {
if(root.left == null && root.right == null) break;
if(root.val == 'T') root = root.left;
else root = root.right;
}
return root.val;
}``````

TODO http://www.cnblogs.com/grandyang/p/6022498.html
Only problem is the time complexity is up to O(n^2) in the worse case.
For example, T?T?T?T?T?1:2:3:4:5:6.