|
| 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 | +} |
0 commit comments