Easy 1-pass O(N) Clean - Java - Stack - Explaination


  • 0
    A
    /*
        - Split values by ":" start from end, keep pushing values until we encounter a string with "?"
        - Once we encounter a string with "?", split string with "?", we know at this point that,
          in a given String : "bla ? a ? b" b is the value when condition is true.
        - push b in the Stack (we need to push b to make the code clean as there can be multiple "?" in a string)
        - now, if a is True, pop the second element from Stack, else pop the first.
        - return the top element.
        */
        public String parseTernary(String exp) {
            if(exp == null || exp.length() == 0) return "";
            
            Stack<String> evalStack = new Stack<>();
            String[] split = exp.split(":");
            
            for(int i = split.length - 1; i >= 0; i--){
                if(split[i].indexOf("?") == -1) evalStack.add(split[i]);
                else {
                    String eval[] = split[i].split("\\?");
                    evalStack.add(eval[eval.length - 1]);
                    
                    for(int j = eval.length - 2; j >= 0; j--){
                        if("T".equals(eval[j])){
                            String top = evalStack.pop();
                            //pop the second value in stack
                            evalStack.pop();
                            evalStack.add(top);
                        }
                        //pop the top value from stack.
                        else evalStack.pop();
                    }
                }
            }
            
            return evalStack.pop();
        }
    

Log in to reply
 

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