Skip to content

Commit 2c99c70

Browse files
fishercoder1534fishercoder1534
committed
add 439
1 parent 8956b5d commit 2c99c70

File tree

3 files changed

+134
-0
lines changed

3 files changed

+134
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,6 +104,7 @@ Your ideas/fixes/algorithms are more than welcome!
104104
|445|[Add Two Numbers II](https://leetcode.com/problems/add-two-numbers-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/_445.java)| O(max(m,n)|O(max(m,n)) | Medium| Stack, LinkedList
105105
|442|[Find All Duplicates in an Array](https://leetcode.com/problems/find-all-duplicates-in-an-array/)|[Solution](../master/src/main/java/com/stevesun/solutions/FindAllDuplicatesinanArray.java)| O(n)|O(1) | Medium| Array
106106
|441|[Arranging Coins](https://leetcode.com/problems/arrange-coins/)|[Solution](../master/src/main/java/com/stevesun/solutions/ArrangingCoins.java)| O(n)|O(1) | Easy|
107+
|439|[Ternary Expression Parser](https://leetcode.com/problems/ternary-expression-parser/)|[Solution](../master/src/main/java/com/stevesun/solutions/_439.java)| O(n)|O(n) | Medium| Stack
107108
|438|[Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/)|[Solution](../master/src/main/java/com/stevesun/solutions/FindAllAnagramsinaString.java)| O(n)|O(1) | Easy|
108109
|437|[Path Sum III](https://leetcode.com/problems/path-sum-iii/)|[Solution](../master/src/main/java/com/stevesun/solutions/PathSumIII.java) | O(n^2) |O(n) | Easy| DFS, recursion
109110
|436|[Find Right Interval](https://leetcode.com/problems/find-right-interval/)|[Solution](../master/src/main/java/com/stevesun/solutions/FindRightInterval.java) | O(nlogn) |O(n) | Medium| Binary Search

‎src/main/java/com/stevesun/solutions/_439.java

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package com.stevesun.solutions;
2+
3+
import java.util.ArrayDeque;
4+
import java.util.Deque;
5+
6+
/**
7+
* 439. Ternary Expression Parser
8+
*
9+
* Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression.
10+
* 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).
11+
12+
Note:
13+
14+
The length of the given string is ≤ 10000.
15+
Each number will contain only one digit.
16+
The conditional expressions group right-to-left (as usual in most languages).
17+
The condition will always be either T or F. That is, the condition will never be a digit.
18+
The result of the expression will always evaluate to either a digit 0-9, T or F.
19+
20+
Example 1:
21+
22+
Input: "T?2:3"
23+
24+
Output: "2"
25+
26+
Explanation: If true, then result is 2; otherwise result is 3.
27+
28+
29+
Example 2:
30+
31+
Input: "F?1:T?4:5"
32+
33+
Output: "4"
34+
35+
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
36+
37+
"(F ? 1 : (T ? 4 : 5))" "(F ? 1 : (T ? 4 : 5))"
38+
-> "(F ? 1 : 4)" or -> "(T ? 4 : 5)"
39+
-> "4" -> "4"
40+
Example 3:
41+
42+
Input: "T?T?F:5:3"
43+
44+
Output: "F"
45+
46+
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
47+
48+
"(T ? (T ? F : 5) : 3)" "(T ? (T ? F : 5) : 3)"
49+
-> "(T ? F : 3)" or -> "(T ? F : 5)"
50+
-> "F" -> "F"
51+
*/
52+
public class _439 {
53+
54+
/**Below is my original solution, but looking at Discuss, a more concise way is to use just one stack, process it from right to left,
55+
* example: https://discuss.leetcode.com/topic/64409/very-easy-1-pass-stack-solution-in-java-no-string-concat*/
56+
57+
public String parseTernary(String expression) {
58+
Deque<Character> stack = new ArrayDeque<>();
59+
Deque<Character> tmpStack = new ArrayDeque<>();
60+
for (char c : expression.toCharArray()) {
61+
stack.addFirst(c);
62+
}
63+
while (!stack.isEmpty()) {
64+
if (stack.peek() != '?') {
65+
tmpStack.addFirst(stack.pollFirst());
66+
} else {
67+
char char1 = tmpStack.removeFirst();
68+
tmpStack.removeFirst();//remove ':'
69+
char char2 = tmpStack.removeFirst();
70+
stack.removeFirst();//remove '?'
71+
char judge = stack.removeFirst();
72+
tmpStack.addFirst(judge == 'T' ? char1 : char2);
73+
while (!tmpStack.isEmpty()) {
74+
stack.addFirst(tmpStack.pollFirst());
75+
}
76+
}
77+
if (stack.size() == 1) break;
78+
}
79+
return Character.toString(stack.removeFirst());
80+
}
81+
82+
}

‎src/test/java/com/stevesun/_439Test.java

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.solutions._439;
4+
import com.stevesun.solutions._48;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static org.junit.Assert.assertEquals;
9+
10+
/**
11+
* Created by stevesun on 5/18/17.
12+
*/
13+
public class _439Test {
14+
private static _439 test;
15+
private static String expression;
16+
private static String expected;
17+
private static String actual;
18+
19+
@BeforeClass
20+
public static void setup(){
21+
test = new _439();
22+
}
23+
24+
@Test
25+
public void test1(){
26+
expression = "T?2:3";
27+
expected = "2";
28+
assertEquals(expected, test.parseTernary(expression));
29+
}
30+
31+
@Test
32+
public void test2(){
33+
expression = "F?1:T?4:5";
34+
expected = "4";
35+
assertEquals(expected, test.parseTernary(expression));
36+
}
37+
38+
@Test
39+
public void test3(){
40+
expression = "T?T?F:5:3";
41+
expected = "F";
42+
assertEquals(expected, test.parseTernary(expression));
43+
}
44+
45+
@Test
46+
public void test4(){
47+
expression = "T?T:F?T?1:2:F?3:4";
48+
expected = "T";
49+
assertEquals(expected, test.parseTernary(expression));
50+
}
51+
}

0 commit comments

Comments
 (0)