TernaryExpressionParserOPT [source code]
public class TernaryExpressionParserOPT {
static
/******************************************************************************/
public class Solution {
public String parseTernary(String expression) {
char[] chs = expression.toCharArray();
Stack<Character> stack = new Stack<>();
for (int i = chs.length - 1; i >= 0; i--) {
if (chs[i] != '?' && chs[i] != ':') {
stack.push(chs[i]);
} else if (chs[i] == '?') {
char l = stack.pop();
char r = stack.pop();
stack.push(chs[--i] == 'T' ? l : r);
}
}
return stack.pop() + "";
}
}
/******************************************************************************/
public static void main(String[] args) {
TernaryExpressionParserOPT.Solution tester = new TernaryExpressionParserOPT.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++) {
String e = inputs[i];
System.out.println(Printer.seperator());
String output = tester.parseTernary(e);
String ans = answers[i];
System.out.println(Printer.wrapColor(e, "magenta") + " -> " + output + Printer.wrapColor(", expected: " + ans, output.equals(ans) ? "green" : "red"));
}
}
}
答案看完之后自己大概写了一个, 速度是21ms (68%), 倒不是很快; submission里面看了一下, 那个recursive然后count到:的N^2的办法居然在90%的第一梯队, 很不理解; 感觉LeetCode的OJ对于这些数据结构的penalty还是太严重了;
第一梯队的基本都是recursion的解;
但是神乎其技版本的recursion解居然也没有这个count的方法快? 真的是不太理解了;
另外这个Stack的解法, 我感觉我这种写法实际上是比下面discussion最优解这种写法要好的, ?作为一个cue, 当出现?的时候就pop出来计算, 而不是所有的entry全部都push进去;
这个题目基本是放弃了, 这个是discussion的最优解:
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());
}
以及一个稍微简化的版本:
public String parseTernary(String expression) {
Stack<Character> stack = new Stack<>();
stack.push(expression.charAt(expression.length() - 1));
for (int i = expression.length() - 3; i >= 0; i -= 2) {
if (expression.charAt(i + 1) == '?') {
char cTrue = stack.pop();
char cFalse = stack.pop();
stack.push(expression.charAt(i) == 'T' ? cTrue : cFalse);
} else {
stack.push(expression.charAt(i));
}
}
return String.valueOf(stack.peek());
}
这个问题就非常的直接了, 首先这个是一个on the fly的做法, 严格来说这里都没有一个parse的过程, 因为所谓的parse就是一个要把一个直接的concrete expression转换成AST的过程, 也就是我做的这个过程; 但是这里是不需要的, 直接就eval就行了;
这个算法, 仔细看, 其实是非常像math expression的那个2stack的算法的; 碰到一个cue就pop出来计算, 计算完了再放回去;
那么Stack在这类问题中针对的到底是什么feature呢? 我认为好像是nested, 也就是一个tree structure.
想了一下, 好像利用他这个从右到左的思路, 就算是写一个parser也是写的出来的?
所以我自己的parser失败的原因到底是什么? 是因为没有看懂题目就开始写?
这个是另外一个版本, 逻辑更加直白一些:
public String parseTernary(String expression) {
Stack<Character> stack = new Stack<>();
for (int i = expression.length() - 1; i >= 0; --i) {
char c = expression.charAt(i);
if (c == ':')
continue;
else if (c == '?') {
char left = stack.pop();
char right = stack.pop();
char condition = expression.charAt(i - 1);
stack.push(condition == 'T' ? left : right);
--i;
} else {
stack.push(c);
}
}
return stack.pop().toString();
}
另外注意他这个做法, 他这个做法是可以很简单的就改写成一个recursion的; 不对, recursion, 其实是没有这么简单的:
public class Solution {
int idx;
public String parseTernary(String expression) {
idx = 0; //clean instance var: good practice
return Character.toString(helper(expression));
}
char helper(String s) {
char ch = s.charAt(idx);
if (idx + 1 == s.length() || s.charAt(idx + 1) == ':') {
idx += 2; // pass ':'
return ch;
}
idx += 2; // pass '?'
char first = helper(s), second = helper(s);
return ch == 'T' ? first : second;
}
}
这个recursion, 你subproblem怎么定义, 是一个问题; 你可以看到, 他虽然说是一个recursion, 但是实际上, 他的参数在每个level的recursive call里面都没有变化! 那么变化的是什么? 其实就是idx, 这个global的变量; 所以其实他这里我感觉就是用recursion完成了一个类似iteration的功能;
为什么要有idx这一个指针, 因为这个问题, 你不知道你后面的两个operand到底有多长.
这个recursion算法其实是有点难以理解的, 画了一个trace, 还是能够看出来对的, 不过不太理解作者设计的时候背后动机到底是怎样的, 怎么想出来的; 另外注意他这里这个DFS的order是PostOrder; 因为他这个做法是从左到右的, 所以PostOrder其实是合理的;
仔细想了一下, 其实人家这里这个是有subproblem的概念的, 比如你走到一个'?'的位置(注意看代码怎么写的, 这个才是main case, recursion的代码base case写在上面, 但是':'的case并不是primary case): 严格来说, 是前方是(面对)'?'的位置: 我们先跳过这个'?', 然后我们后方有两个subproblem, 作为这个三目的两个operand; 但是我们不知道这两个subproblem各自有多长(但是我们知道他们是紧密连接在一起的);
我们发现一个recursion不好理解的时候, 一个常见的技巧就是考虑第一个level(以了解这个divide的过程), 以及最后一个level(最后一个触底反弹的过程, 来了解DP value的体现: 怎样用subsolution完成组合);
想recursion算法的时候, 很多时候好像单纯的从imperative的, 也就是trace的角度来想, 是想不出来的; recursion算法设计的时候的核心, 还是能够找到一个逻辑statement: subsolution跟big solution之间到底有什么关系;
放到这个问题上面来说, 这个方法并不难做到, 因为你是知道最后的答案的! 也就是最终这个subproblem怎么划分, 我们是完全知道的; 光是这一点, 这一题做的时候其实比很多其他题目都有优势很多了; 你思考的时候, 就假设subsolution你已经知道了(事实上你就是已经知道了). 一个需要注意的问题, 光是知道subsolution还是不够的, 你还要知道subproblem的划分, 也就是这个括号的划分; 因为这个才是你的recursion在进行的过程中要完成的内容;
其实就算搞了这么多的方法, 这个idx的理解还是有点难; 其实这个idx真正的作用, 是一个timestamp的作用: timestamp左右两个是可以给一个subproblem进行分解的; 当我们在一个level, 进行recursive call的时候, 左边的timestamp, 或者说左边括号, 我们是知道的, 那么右边括号呢?
这个recursion算法不仅不是一个trivial的改写, 而且还可以算是LeetCode上面不常见到的一个神乎其技的算法;
另外一个我比较不理解的地方是, 到底怎么想到这个问题用Stack? 如果说是写一个parser, 那么你用Stack我都理解了, 关键严格来说这里做的也不是一个parse的过程啊?
另外下面的评论里面有人写了一个每个数字可以多个digit的版本; 我没有仔细看, 不过这个Follow-Up实际上并不难写, 直接先把整个array给parse成一个string array, 每个entry储存T/F, 或者数字, 或者符号就行了;
这个是他写的代码:
public String parseTernary(String expression) {
if (expression == null || expression.length() < 5) {
return "";
}
Stack<String> stack = new Stack<>();
// two pointers for getting the substring
int i = expression.length();
int j = i-1;
while (j >= 0) {
char c = expression.charAt(j);
if (!stack.isEmpty() && stack.peek().equals("?")) {
if (stack.size() < 4) {
return ""; //invalid expression
}
stack.pop(); //pop '?'
String first = stack.pop();
stack.pop(); //pop ':'
String second = stack.pop();
if (c == 'T') {
stack.push(first);
} else if (c == 'F') {
stack.push(second);
} else {
return ""; //invalid expression
}
i = j;
} else {
if (c == '?' || c == ':') {
// i == j+1 indicates that the value is already pushed in stack
if (i != j+1) {
String value = expression.substring(j+1, i);
stack.push(value);
}
stack.push(String.valueOf(c));
i = j;
}
}
j--;
}
return stack.peek();
}
这个是另外一个recursion的版本:
public class Solution {
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);
}
}
这个版本的速度就不怎么好, 因为每一个level里面还要重新再过一个pass, 不像上面那个神乎其技版本, 直接一个1pass就搞定了; 这个版本理论上WorstCase是N^2;
这个算法的核心逻辑是抓住了?和:之间的对应性: 一个没有nesting的三目expression, 肯定是一个?和一个:. 现在我们有nesting, 带来的是什么问题呢? 首先, 一个nested expression, 最上面一层, 也就是root level, 肯定还是一个?和一个:, 问题就在于你不知道这个:在哪里;
nesting到底是什么意思? 比如T?(expr1):(expr2)这样就是一个nesting, 事实上就是在两个expr之间插入一个:, 然后在开头加一个?; 看到关键没有? 要找到这个:, 我们注意到expr1里面?和:的个数是相等的; 所以我们从最开始的?开始数, 数到:的数量第一次抵消?的数量的时候(当?的数量大于:的数量的时候, 就是nesting还在继续下行(加深)的过程), 就是我们这个root level的:的位置; 而从这个:的位置到root level的最末尾, 就是expr2的范围;
题外话一下:
另外这个count思路也可以帮助理解上面那个神乎其技的版本: 在这个神乎其技的版本里面, 你注意, 除开base case, 当我们面前是?的时候, 我们做出两个recursive call: 这里暗示: 每一个recursive level代表的是什么? 也就是每一个subproblem代表的是什么? 其实代表的就是the two expressions that are the two operands of this level(and this level's ?);
知道这个recursive structure之后(也就是subproblem的definition和划分), 我们怎么来理解, 这个idx呢? 仅仅理解上面对于subproblem的定义, 其实还是不好理解这个idx到底是什么作用的; 比如我们站在T?(expr1):(expr2)的最外层, 向下recurse, 结果碰到的第一个:我们就是我们碰到的第一个base case? 为什么是这样? 如果expr1里面还nest了其他的:, 那么我们这个base case的时候明明其实还没有结束expr1啊?
这个idx真正的作用, 其实是一个PostOrder的时候的指针, 类似于给你一个AST, 然后你PostOrder走的时候, 这个idx就是一个在不同的node当中移动的指针; 只不过现在你手上拿到的不是一个AST, 而是一个serialization, 所以这个pointer看起来有点不好理解, 实际上如果你真正理解了tree traversal, 那么你就知道这样一个对应的指针在serialization上面正好就是一个从左到右的一遍头就走完了; 这样一个fact如果以前没有接触过第一次理解是有点困难;
刚开始想问题的时候, 按照recursion的思路来理解是很好, 比如利用
- root level and its chidren
- DP property
- subproblem delimination
不过很多时候光是从这个角度来思考并不能完整的指导最后的实现; recursion问题最后实现的时候, 为了代码写的更好, 最好的办法还是可以尝试从traversal的角度来思考一下; 比如这里这个下面这个N^2的版本, 其实就是一个对于subproblem理解的直接翻译,最后的速度就比如理解了traversal之后写出来的版本;
另外, 这个题目我这么束手无策, 肯定是因为我对这个题型很陌生. 那么, 这个算是一个什么题型呢? 严格来说, 这个算是一个deserialize nested stucture的题型.
首先考虑, nesting是什么意思? 其实就是每一个node都有相同的inductive structure的意思; 就比如这里, 或者说是括号结构; 这种定义其实是比deserialize BST那个题目要简单的, 那个题目, 是没有任何分界的标志的;
至于deserialize, 这个就很好理解了; 做法无非就是iterative with Stack, 或者就是recursion, 后者难写一些, 不过如果足够锻炼, 两个算法应该是都能够掌握的;
count这个版本虽然WorstCase不太好, 但是BestCase好像还可以? 比如"T?T:F?T?1:2:F?3:4"这个case, 这个算法是能够完成short circuiting的!
总体来说我感觉这个算法不是一个特别优秀的算法, 因为这个还是观察问题本身的peculiarity做出来的, 背后的fundamental idea并没有往其他的同类问题拓展的潜能;
这个是一个简化的版本:
public String parseTernary(String expression) {
if (expression.length() == 1) return expression;
int i = 1, count = 1;
while (count != 0) {
char c = expression.charAt(++i);
count += c == '?' ? 1 : c == ':' ? -1 : 0;
}
return expression.charAt(0) == 'T'? parseTernary(expression.substring(2, i)): parseTernary(expression.substring(i + 1));
}
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 ).
这个人的解释就很好, 另外, 按照他这里的解释, 他认为这个数symbol的方法其实不属于纠结题目本身的peculiarity, 而是一个普遍在expression类问题里面常见的技巧: 你总是可以找到这样两个数量相等的symbol;
这个是另外一个很聪明的iterative的解:
public class Solution {
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;
}
}
作者的解释:
In order to pick out useful "?" and ":", we can always begin with the last "?" and the first ":" after the chosen "?".
Therefore, directly seek for the last "?" (or you can simply put all "?" into a stack) and update the string depending on T or F until no more "?"s.
e.g.
"(F ? 1 : (T ? 4 : 5))" => "(F ? 1 : 4)" => "4"
"(T ? (T ? F : 5) : 3)" => "(T ? F : 3)" => "F"
虽然说这个题目是一个tree的结构, 但是这个人没有被这个tree结构局限住, 而是直接考虑用Bottom-Up的思路来做: 最后一个?就是最底层的一个leaf, 严格来说是最左下角的一个leaf; 不对, 好像是右下角?
?
/ \
? : ?
/ \ / \
_ :_ _:_
如果要让你画一个AST, 那么这样的一个tree结构是要能够画出来的(?在哪里, :在哪里). 以及给我们的这个string跟这个AST是什么关系(PreOrder serialization);
理解了这个AST, 那么这个人的思路还是不难理解的, 他就是一个Bottom-Up, 同时从右向左的的collapse这个serialization的过程; 每一个?对应一个internal node, 所以直接一个一个的把每一个internal node变成一个leaf就行了, 最后只剩一个leaf(root), 就是我们要的结果;
注意我们每次找到的这个rightmost ?, 他下面两个一定是leaf, 这个对应到serialization上面, 就是每一个rightmost ?的右边紧邻的:直接对应的就是两个没有nesting的值, 所以他这里直接就用charAt来取结果了;
大概考虑一下这种方法整个tree collapse的顺序: 最深的?优先消失, 如果相同深度, 那么右边的优先消失? 不对, 这样不对, 你就想真正在PreOrder serialization的时候, ?是什么顺序摆起来的? 倒着来就行了; 最后实际上是root的right child先消失, 然后再到左边; 这个才是DFS; 你一开始说的"深度优先, 左右用来break tie", 这个其实是BFS, 不是DFS;
不过这个算法如果按照当前的这个代码, 复杂度其实是不怎么友好的, 因为lastIndexOf这个东西的速度其实不快, 是需要遍历的;
这个是一个类似的版本:
public static String parse(String expression){
if(expression == null || expression.isEmpty()) return "";
String input = expression;
int i = input.length()-1;
//final result will always be a single character
while(input.length() > 1){
while(input.charAt(i) != '?'){
i--;
}
//the first ? is found
char trueOrFalse = input.charAt(i-1);
//compose new input string by adding the middle to original string
char middle = trueOrFalse == 'T' ? input.charAt(i+1) : input.charAt(i+3);
input = input.substring(0,i-1) + middle + input.substring(i+4);
i -= 2;
}
return input;
}
思路其实是差不多的, 就是按照PreOrder serialization的反向来进行eval; 他这个每一个iteration都要做一个string construction, 我感觉这个复杂度估计是挺蠢的;
总结到这里的这些个方法, 其实都很容易改写成一个parser(产生一个AST). 感觉我自己的算法失败的原因还是太拘泥于历史信息流的窠臼(历史信息流的一个死脑筋就是, 绝对不向前看, 当前位置做出的所有决定, 都只依赖于information so far). 但是你看看这里见过的几个算法, recursion的几个就不谈了. iterative的这几个, 除了Stack那个是依赖于倒序, 其他的这几个全都依赖于探路, 虽然探路的目的不尽相同(一个是找到subproblem的末尾, 一个是找到AST的bottom).
所以这题最后失败, 跟死脑筋还是有一定关系的;
discussion里面还真有一个又臭又长先parse成AST的做法:
public class Solution {
public String parseTernary(String expression) {
String res = null;
if (expression != null && expression.length() > 0) {
boolean isLeft = false;
TNode root = null;
Stack<TNode> s = new Stack<TNode>();
TNode n = null;
for (char c : expression.toCharArray()) {
if (c == ':') {
isLeft = false;
} else if (c == '?') {
isLeft = true;
s.push(n);
} else {
n = new TNode(c + "");
if (!s.empty()) {
if (isLeft) {
s.peek().left = n;
} else {
s.peek().right = n;
}
} else {
root = n;
}
if (!isLeft) {
while (!s.empty() && s.peek().right != null) {
s.pop();
}
}
}
}
while (root.s.equals("T") || root.s.equals("F")) {
if (root.left == null && root.right == null) {
break;
}
root = root.s.equals("T") ? root.left : root.right;
}
res = root.s;
}
return res;
}
class TNode {
public String s;
TNode left, right;
public TNode(String s) {
this.s = s;
}
}
}
这个算法刚开始也是看不懂, 还是用一个例子来理解, 用的例子是T?T?F?0:1:1:1, 这个例子的好处在于首先level够深, 可以帮助理解一个完整的recursion的过程, 另外一个好处在于这个说起来是一个tree, 但是比一般的tree简单, 整体的结构更像是一个line一样的list; 这样的一个结构recursion的时候更好理解. 通过这个例子, 可以理解到这个算法几个值得注意的地方;
题外话, 不要说什么历史信息流做不起来, 人家这里就是一个历史信息流的算法, 不过这种historical stream with stack的算法我确实也是不熟悉;
stack the incomplete
我对Stack还是不熟悉. 很多时候, 我不知道Stack的作用是什么, 为什么好好的就想到要用Stack呢? 当然你可以说是因为我们这里对付的是一个tree结构, 在tree结构当中, 相当用Stack不是不能理解: recursion就是用Stack的, DFS也可以理解为是一个Stack based的算法;
当然更完整的, 你还是要想好你为什么需要一个stack? Stack, 和其他的queue之类的结构一样, 都有一个共同作用, 就是write历史信息, 提供给未来的位置来read; 只不过是一个顺序的区别(FIFO还是FILO). 这里的Stack的作用, 就是为了store the incomplete nodes, 至于为什么我们这里需要Stack的这个倒序, 感觉语言上还是不太好描述; 可能还是在自己实际设计的时候用一个example based的思路, 更有利于想出这个思路
top down rather than bottom up: when build tree with stack
这个是跟我的做法一个很大的区别; 我做的时候, 想法的框架就是我们的current指针指向的其实一直是当前正在处理的这个node. 不对, 他这里也是有一个指向当前正在处理的node的指针的;
peek rather than pop
我当时处理的时候有一个很不好的习惯, 就是如果cur已经满了, 那么直接就再pop出来一个, 用来adopt; 这个我当时就没有意识到peek的存在, 因为实际上我这个pop出来第一个, 然后操作, 其实操作的就是peek的这一个; 仔细想想, 跟他这里的做法好像也差不多?
cleanup when isRight
这里他还有一个区别就是用了一个左右的flag, 这个想法我当时其实差不多就加上了, 但是实际上他这里对于这个flag的使用的思路跟我其实不一样, 我的想法是用这个flag来保存每一个在Stack里面的incomplete node的待填充的位置; 其实这个是不必要的, 你仔细看他这里的逻辑, 他这里当一个child完成之后, 填充给peek的位置其实还是采用我的adopt的原则(左边优先, 不行才右边);
他这个flag更大的作用是判断当前这个node是否complete; 如果complete, 他完成一个cleanup的过程: until the peek is empty on its right child;
仔细想想, 我自己的历史信息流失败, 其实还是信息保存的不够, 这个flag其实我是完全没有想到的(那个插入位置的flag虽然也是左右, 但是不是我真正缺少的那个flag). 你回过头仔细看看我那个算法: 纯粹就是一个针对string的分析, 没有任何针对tree结构或者recursion结构设置的逻辑; 如果这样的一个算法都能够正确, 这就太不合理了;
另外他这里没有纠结, 最后的root必须用Stack最后一个被pop的来做, 而是直接在一开始就专门建立一个指针来保存这个大root;
这个算法还有一个和我的算法很大的区别在于他实际上对所有的entry都判断, 而不是我那样只判断符号;
这个是一个没有用Stack的思路: 这样就避免了麻烦. 他的解决办法是用一个parent link来保证能够反向移动:
public class Solution {
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;
}
}
这个就很直白了, 都是一些最基本的tree操作;
discussion基本就没有其他的方法了, 只能说这个题目填了一个大坑;
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