439. Ternary Expression Parser

2ND TRY

Let's see an example
          1   
"T?T:F?T?1:2:F?3:4"

When we see T?T:F(1)  we don't want to evaluate it instantly
Instead, we evaluate F(1)?XXX and then return the result back
Which mean the right side has higher priority
So we have to check from end to start

Whenever we see a '?' we need to evaluate that instantly
So we stand at current char -> If we see that its previous char is '?' then we evaluate

29.43 %
class Solution {
    public String parseTernary(String expression) {
        if (expression == null || expression.length() == 0) {
return null;
}
char curr;
char left;
char right;
Deque<Character> deque = new ArrayDeque<>();
for (int i = expression.length() - 1; i >= 0; i--) {
curr = expression.charAt(i);
if (deque.size() > 2 && deque.peekFirst() == '?') {
deque.removeFirst();
left = deque.removeFirst();
right = deque.removeFirst();
curr = curr == 'T' ? left : right;
}
if (curr != ':') {
deque.addFirst(curr);
}
}
return deque.size() == 1 ? String.valueOf(deque.removeFirst()) : null;
    }
}



1ST TRY
char初始化成''会报错，所以初始化成' '

自己写的是用一个flag来记录'?'
看到答案里面有人是将'?' push into stack然后通过peek()检查，也是很好的办法

58.74 %
class Solution {
    public String parseTernary(String expression) {
        if (expression == null) return null;
        Stack<Character> stack = new Stack<>();
        char cTrue = ' ', cFalse = ' ';
        boolean flag = false;
        for (int i = expression.length() - 1; i >= 0; i--) {
            char c = expression.charAt(i);
            if (c == ':') {
                continue;
            } else if (c == '?') {
                cTrue = stack.pop();
                cFalse = stack.pop();
                flag = true;
            } else if (flag && (c == 'T' || c == 'F')) {
                stack.push(c == 'T' ? cTrue : cFalse);
                flag = false;
            } else {
                stack.push(c);
            }
        }
        return String.valueOf(stack.isEmpty() ? "" : stack.pop());
                     
    }
}