TernaryExpressionParser [source code]
public class TernaryExpressionParser {
static
/******************************************************************************/
public class Solution {
public String parseTernary(String expression) {
char[] chs = expression.toCharArray();
if (chs.length < 5)
return "";
Expr expr = parse(chs);
return eval(expr) + "";
}
public char eval(Expr e) {
if (e.left == null && e.right == null)
return e.question;
if (e.question == 'T')
return eval(e.left);
else
return eval(e.right);
}
public Expr parse(char[] chs) {
Stack<Expr> stack = new Stack<>();
Expr cur = null, prev;
for (int i = 0; i < chs.length / 2; i++) {
int index = 2 * i + 1;
if (chs[index] == '?') {
if (cur != null)
stack.push(cur);
cur = new Expr();
cur.question = chs[index - 1];
} else {
if (chs[index - 2] == '?') {
cur.left = new Expr();
cur.left.question = chs[index - 1];
} else {
Expr newRight = new Expr();
newRight.question = chs[index - 1];
if (cur.adopt(newRight)) {
if (!stack.isEmpty()) {
prev = stack.pop();
prev.adopt(cur);
cur = prev;
}
} else {
prev = stack.pop();
prev.adopt(cur);
prev.adopt(newRight);
cur = prev;
}
}
}
}
Expr newRight = new Expr();
newRight.question = chs[chs.length - 1];
if (!cur.adopt(newRight)) {
while (!stack.isEmpty()) {
prev = stack.pop();
prev.adopt(cur);
prev.adopt(newRight);
cur = prev;
}
} else {
while (!stack.isEmpty()) {
prev = stack.pop();
prev.adopt(cur);
cur = prev;
}
}
return cur;
}
public static class Expr {
char question;
Expr left;
Expr right;
public String toString() {
String children;
if (left == null && right == null)
return question + "";
else children = "?" + (left == null ? "_" : left.toString()) + ":" + (right == null ? "_" : right.toString());
return "(" + question + children + ")";
}
public boolean adopt(Expr e) {
if (left != null & right != null)
return false;
if (left == null)
left = e;
else if (right == null)
right = e;
return true;
}
}
}
/******************************************************************************/
public static void main(String[] args) {
TernaryExpressionParser.Solution tester = new TernaryExpressionParser.Solution();
String[] inputs = {
"T?2:3",
"F?1:T?4:5",
"T?T?F:5:3",
"F?T?F?7:F?F?F?3:F?F?0:1:0:6:1:0:5",
"T?T:F?T?1:2:F?3:4", //T?T:(F?(T?1:2):(F?3:4))
"F?4:F?T?7:T?9:6:T?T?T?F?4:4:0:T?T?F?3:F?F?T:T?F?T?0:F?T:0:T?0:7:5:T?T?7:T?2:F?5:7:4:F?T?6:T?F?9:T?F:T?T?F?9:4:T?1:T?T?T?T?F?T?T?T?T:F?F:4:T?T?T?1:T?0:T?T?T:F?2:8:4:T?3:F?6:5:T?T?T?T?F?F:F:T?T?1:F?9:F?4:1:F:9:8:8:F:F:8:6:F:3:8:3:6:9:8",
};
String[] answers = {
"2",
"4",
"F",
"5",
"T",
"4",
};
for (int i = 0; i < inputs.length; i++) {
if (i != 5) continue;
System.out.println(Printer.separator ());
String output = tester.parseTernary(inputs[i]);
System.out.println(Printer.wrapColor(tester.parse(inputs[i].toCharArray()).toString(), "magenta") + " -> " + output + Printer.wrapColor(", expected: " + answers[i], output.equals(answers[i]) ? "green" : "red"));
}
}
}
这个题目比较好的地方是给了不少的例子, 这些例子的trace其实就是一个人逻辑的作用;
感觉这个题目应该是做的出来的, 不太想放弃;
这个题目我第一感觉就是, 因为是一个nested parens的结构, 很自然的想要做一个类似tree的结构, 然后后面想了一下怎么处理这个tree呢? 好像是DFS可以, 再一看, 这里的tag给的就是DFS, 所以感觉这个题目的思路应该是对的了;
当然刚开始想到要建立object的时候还是有点不甘心的, 不过不要怕麻烦, 做出来最要紧, 大不了, 这个就当做是笨办法就是了;
描述一下我这个笨办法:
- parse, 按照类似括号配对的算法, parse出来一个tree;
- 按照DFS的顺序evaluate, 要用PostOrder?
不过所谓DFS最后实现的时候无非也就是一个recursion, 或许可以直接就用一个recursion做完? 而省略掉这个种树的过程?
这个想不出来, 我们暂时就用笨办法;
有一个问题需要先拎清楚, 我们的node保存的应该是什么? 每一个node最后实际上就只有一个value, 那么我们需要在建立这个node的时候就保存这个value吗? 按照之前426的时候的感觉, 我认为应该是不要的, 作为一个interpreter的思路, 你的node和tree保存的应该是expression. 至于evaluate到value的过程, 最后eval的时候再做. 事实上, 套用426那个时候写interpreter的经验, 这个value其实就是eval函数的直接的返回值;
interpreter的逻辑其实我还是会写的, 不过这个问题还要写一个parser, 这个426上课的时候当时是没有写过的, 有点慌;
至于group from right to left这个条件, 好像是如果出现这种的: T?T:F?1:2, 这个其实可以理解为(T?T:F)?1:2, 也可以理解为T?T:(F?1:2). 按照下面第三个例子的展示, 应该用第二种方式来parse;
写的时间太长了, 大概瞄了一眼discussion, 感觉大部分人用的方法都没有我这么复杂, 感觉我还是给这个问题想的太复杂了, 非要写一个完整的interpreter. 虽然说Snapchat的题目难, 但是也不至于45分钟让你写一个interpreter这么难;
这个题目应该还是有其内在的简化的逻辑的, 比如说"T?T:F?T?1:2:F?3:4"这个case, 就很明显的, 可以用short circuit来做, 最后实际上根本不需要parse整个expression; 这个题目更好的思路应该是直接一边parse一边eval, 而不是426上课的时候Scott那种做法: 他当时之所以要那样做, 估计就是考虑parser的难度太高, 只让我们写一下eval, 能够理解课程的核心内容就行了;
最后考虑还是放弃了, 这个题目浪费的时间已经太多了; 这个parser暂时感觉是写不出来了; 看到后面hard好像有一题就是deserialize BST, 估计那个题目可以得到一点启发; 这个题目暂时就先把这个版本摆在这里了;
感觉这个题目我还是止损没有做好, 按理说当写interpreter这个思路花了这么长的时间还是没有结果的时候, 就应该考虑换一个思路了, 比如是不是把问题想的太复杂了, 是不是有什么关键的intuition没有想到;
Problem 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 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"
Difficulty:Medium
Total Accepted:6.8K
Total Submissions:13.5K
Contributor: LeetCode
Companies
snapchat
Related Topics
depth-first search stack
Similar Questions
Mini Parser