Very easy 1 pass Stack Solution in JAVA (NO STRING CONCAT)


  • 61

    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());
    }

  • 2
    F

    Great idea. One small question is that it can be a little more robust. For example, the test case "T?123:1" should return 123.


  • 0

    @forestschao
    Yeah, thank you, you bring out a good point.
    Only for this case, we have the constraint in requirement so I didn't implement this.
    "2. Each number will contain only one digit. "


  • 0
    F

    Oh, my bad, bro. You are totally right.


  • 0
    D

    @NathanNi Do you need to push the ? and : characters on to the stack or can you solve just by pushing the true and false expressions alone and when you encounter a ? just check the character before it? Is there any case where the conditional expression can itself be a ternary expression instead of a constant?


  • 0

    Great solution! Here is my re-written version based on yours. I did not push '?' and ':' into the stack. Instead I used a variable conditionIdx to keep track of the position before '?'.

    public String parseTernary(String expression) {
        char[] arr = expression.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        int conditionIdx = arr.length;
        for(int i=arr.length-1; i>=0; --i){
            char c = arr[i];
            // char before '?': Either 'T' or 'F'
            if(i==conditionIdx){
                char first = stack.pop(), second = stack.pop();
                stack.push(c=='T' ? first : second);
            }
            // '?', update conditionIdx
            else if(c=='?'){
                 conditionIdx = i-1;
            }
            else if(c!=':'){
                stack.push(c);
            }
        }
        return String.valueOf(stack.peek());
     }
    

  • 2
    I

    Recursive way, one pass.

        int idx;
        public String parseTernary(String expression) {
            idx = 0;
            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;
        }
    

  • 4

    Great Solution! Modified slightly:

    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());
    }
    

  • 0
    M

    Nice solution! I rewrite a follow up solution that :

    1. a number can contains multiple digits
    2. return "" if it's an invalid ternary expression
    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();
        }

  • 0
    Z

    Great solution! One little thing, could this handle the case: "(T) ? 4: 5"? I think the code assumes that '?' is right next to 'T' or 'F'?

    -- nvm, the question says "only consists of digits 0-9, ?, :, T and F", so no empty spaces, no parenthesis...


  • 0

    Can you explain the time complexity of this method?
    I'm not familiar with that? Thank You.


  • 0

    Initially, I thought approach this problem from start to end. But I found that if condition is "T", I need to look ahead and skip the second arguments of ":", which is kind of stuck. Your solution is great, if from end to start, by end of the loop, the rest values within the stack are those "second arguments" whose evaluated condition is true, am I right?


  • 0
    J

    rewrite with same idea.

        public String parseTernary(String expression) {
            Stack<Character> stack = new Stack<>();
            int i = expression.length() - 1;
            while (i >= 0) {
                while(i >= 0 && expression.charAt(i) != '?') {
                    stack.push(expression.charAt(i));
                    i--;
                }
                char left = stack.pop();
                stack.pop();
                char right = stack.pop();
                i--;
                if (expression.charAt(i) == 'T') stack.push(left);
                else stack.push(right);
                i--;
            }
            return String.valueOf(stack.peek());
        }
    

  • 0
    Z

    Great solution! I rewrote in C++.

    class Solution {
    public:
        string parseTernary(string expression) {
            int n = expression.size();
            stack<char> sk;
            for (int i = n-1; i >= 0; i--) {
                if (expression[i] == '?') {
                    if (expression[i-1] == 'F') 
                        sk.pop();
                    else {
                        char first = sk.top();
                        sk.pop();
                        sk.pop();
                        sk.push(first);
                    }
                    i--;
                }
                else if (expression[i] != ':') {
                    sk.push(expression[i]);
                }
            }
            string ans(1, sk.top());
            return ans;
        }
    };
    

  • 0

    @iaming After spending some time on it, I have to say this is a truly remarkable solution. Thanks for sharing.


  • 0
    C

    genius idea,but runtime is not as expected.


  • 0

    I think parsing the string from right to left is a bad idea. Consider the below case where the first expression is true and we could simply return the left value without processing the right expression. Any thoughts?

    "T?1:T?T?T?T?T?T?T?T?T?T?T?T?T?T?T?T?4:5:5:5:5:5:5:5:5:5:5:5:5:5:5:5:5"

    My C++ implementation. Could be done using recursion. I've used stack in this case. Beats 80%.

    class Solution {
    public:
        string parseTernary(string expression) {
            if (expression.empty()) return "";
            stack<string> stk;
            stk.push(expression);
            while (!stk.empty()){
                if (stk.top().size()==1) return stk.top();
                string temp = stk.top();
                stk.pop();
                int i=0;
                char ch = temp[i++];
                i++; //skip the first question mark
                int start=i, count=1;
                
                while (count != 0){
                    i++;
                    if (temp[i]=='?')
                        count++;
                    else if (temp[i]==':')
                        count--;
                }
                
                if (ch=='T'){
                    stk.push(temp.substr(start, i-start));    
                }else{
                    stk.push(temp.substr(i+1));
                }
            }
            return "";
        }
    };
    

  • 0
    V

    @forestschao exactly


  • 0
    V

    @sky-xu nice code!


  • 0
    F

    My DFS version

    class Solution {
        public String parseTernary(String expression) {
            if (expression == null || expression.length() == 0) {
                return "";
            }
            return dfs(expression, 0, expression.length() - 1);
        }
        public String dfs(String expression, int start, int end) {
            if (start == end) {
                return String.valueOf(expression.charAt(start));
            }
            int count = 1;
            int i = start + 2;
            for (; i <= end; i++) {
                if (expression.charAt(i) == '?') {
                    count++;
                } else if (expression.charAt(i) == ':'){
                    count--;
                }
                if (count == 0) {
                    break;
                }
            }
            if (expression.charAt(start) == 'T') {
                return dfs(expression, start + 2, i - 1);
            }
            return dfs(expression, i + 1, end);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.