Massive Algorithms: LeetCode 439

Related: Pocket Gems - Ternary Expression to Binary Tree
http://bookshadow.com/weblog/2016/10/23/leetcode-ternary-expression-parser/

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 or F. That is, the condition will never be a digit.
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://www.cnblogs.com/grandyang/p/6022498.html

这道题让我们解析一个三元表达式，我们通过分析题目中的例子可以知道，如果有多个三元表达式嵌套的情况出现，那么我们的做法是从右边开始找到第一个问号，然后先处理这个三元表达式，然后再一步一步向左推，这也符合程序是从右向左执行的特点。那么我最先想到的方法是用用一个stack来记录所有问号的位置，然后根据此问号的位置，取出当前的三元表达式，调用一个eval函数来分析得到结果，能这样做的原因是题目中限定了三元表达式每一部分只有一个字符，而且需要分析的三元表达式是合法的，然后我们把分析后的结果和前后两段拼接成一个新的字符串，继续处理之前一个问号，这样当所有问号处理完成后，所剩的一个字符就是答案

    string parseTernary(string expression) {
        string res = expression;
        stack<int> s;
        for (int i = 0; i < expression.size(); ++i) {
            if (expression[i] == '?') s.push(i);
        }
        while (!s.empty()) {
            int t = s.top(); s.pop();
            res = res.substr(0, t - 1) + eval(res.substr(t - 1, 5)) + res.substr(t + 4);
        }
        return res;
    }
    string eval(string str) {
        if (str.size() != 5) return "";
        return str[0] == 'T' ? str.substr(2, 1) : str.substr(4);
    }

下面这种方法也是利用栈stack的思想，但是不同之处在于不是存问号的位置，而是存所有的字符，将原数组从后往前遍历，将遍历到的字符都压入栈中，我们检测如果栈首元素是问号，说明我们当前遍历到的字符是T或F，然后我们移除问号，再取出第一部分，再移除冒号，再取出第二部分，我们根据当前字符来判断是放哪一部分进栈，这样遍历完成后，所有问号都处理完了，剩下的栈顶元素即为所求:

http://www.chongchonggou.com/g_609521024.html

用stack来做，对string从右往左遍历：遇到？，则根据？前的T/F从stack顶上两个数选一个保留；遇到数字或者F/T,直接push；遇到：不用操作！
为什么从右往左遍历string？因为对每个“？”,选取“？”右边的两个数中的一个，而每个数又可以包含”?”。考虑string是嵌套的，因此需要先得到？右边的两个数的值，再根据？从两个数中选一个，所以需要对string从右往左遍历！更简单的说法：同样是?,位于左边的?优先级低，需要后处理；位于右边的?优先级高，需要先处理。即:表面看都是问号，但位置不同，优先级不同，这是所有嵌套类问题的通解！

https://segmentfault.com/a/1190000008939830

从右往左看，? 作为决定最小单位的符号，每次遇到一个？，就拆解离？最近的两个小单位。宏观上看是，从小到大。

    public String parseTernary(String expression) {
        if(expression == null || expression.length() == 0) return "";
        Deque<Character> stk = new LinkedList<>();
        
        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 "";
    Deque<Character> stack = new LinkedList<>();

    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

栈（Stack）数据结构

循环直到栈中元素为1并且表达式非空：

取栈顶的5个元素，判断是否为一个可以解析的表达式。若是，则解析后压栈

否则从右向左将expression中的字符压入栈stack

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://github.com/maiquynhtruong/Leetcode/blob/master/ternary-expression-parser.java

 public static String parseTernary(String expression) {
  if (expression.length() < 2) {
   return expression;
  } else {
   String[] strs = expression.substring(2).split(":");
   if (expression.charAt(0) == 'T') {
    return parseTernary(strs[0]);
   } else {
    return parseTernary(strs[1]);
   }
  }
 }
 
 public static String parseTernary(String expression) {
  if (expression == null || expression.length() == 0) {
   return expression;
  }
  Stack<Character> s = new Stack<Character>();
  for (int i = expression.length() - 1; i >= 0; i--) {
   char c = expression.charAt(i);
   if (!s.empty() && s.peek() == '?') {
    s.pop(); // remove '?'
    char first = s.pop();
    s.pop(); // remove ':'
    char second = s.pop();
    if (c == 'T') {
     s.push(first);
    } else {
     s.push(second);
    }
   } else {
    s.push(c);
   }
  }
  return String.valueOf(s.peek());
 }

https://medium.com/@honda.wei/leetcode-破關之路-439-ternary-expression-parser-上鎖題-a34fae94156

用遞迴。方式和上面相反，從字串前端開始遍歷字串。此時可把問號(?)和分號(:)看作一個組合，若問號和分號的數量一樣，就處理這個組合。此時可從該字串的第一個字來確認是T還是F，如果是T，則抓取第2個字元到分號之間的子字串，也就是分號左邊，來往下遞迴。如果是F，則抓取分號右邊的子字串，來往下遞迴。在遍歷的過程中，在處理此段邏輯時，因為時機點是問號和分號的數量一樣，所以此時索引的值會停留在分號這個位置。

細部處理

在用遞迴時，要注意的是判斷問號和分號的數量一樣時，接下來的處理要在確認當前是分號的情況下才能作，也就是

for (int i = 0; i < expression.length(); i++) {
            if (exp.charAt(i) == '?')
                questionMarkCnt++;
            else if (exp.charAt(i) == ':') {
                colonCnt++;
            
                if (questionMarkCnt == colonCnt) {
                    if ('T' == exp.charAt(0)) {
                    // left side
                        return parseTernary(exp.substring(2,i));
                    }
                    else {
                        return parseTernary(exp.substring(i+1));
                    }
                }
                
            } 
  
        }

若寫成下面，則表示有可能是在索引值為為問號時進行處理(下面的程式碼會出錯)

for (int i = 0; i < expression.length(); i++) {
            if (exp.charAt(i) == '?')
                questionMarkCnt++;
            else if (exp.charAt(i) == ':') {
                colonCnt++;

             }            
             
             if (questionMarkCnt == colonCnt) {
               if ('T' == exp.charAt(0)) {
                    // left side
                    return parseTernary(exp.substring(2,i));
               }
               else {
                    return parseTernary(exp.substring(i+1));
               }
             }

https://blog.csdn.net/zqh_1991/article/details/52901605
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 "";
}

? : 所组成的最小单位，可以看作一对括号。？类似（，：类似）。
从左往右看，：作为决定一组完整最小单位的符号。每次找到一对就可以按：分为左右两个子问题递归解决。
宏观上看是从大到小拆开，从小到大递归回去。
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/

一个公式由3部分组成 <bool>?<left>:<right>, bool值只能为T或F, left或right可以为子公式或是单一的值. 所以只要能够正确的划分这三个部分, 就能用递归来处理.

这里我们发现?和:是成对出现的, 用一个flag来计数, 遇到?加1, 遇到:减一, 当flag == 0的时候, 说明正好为left和right的分界.

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;
    }

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.

LeetCode 439 - Ternary Expression Parser

Labels

Popular Posts