Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/439.html

439. Ternary Expression Parser

Level

Medium

Description

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. 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).

Note:

1. The length of the given string is ≤ 10000.
2. Each number will contain only one digit.
3. The conditional expressions group right-to-left (as usual in most languages).
4. The condition will always be either T or F. That is, the condition will never be a digit.
5. The result of the expression will always evaluate to either a digit 0-9, T or F.

Example 1:

Input: "T?2:3"

Output: "2"

Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
          -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
          -> "4"                                    -> "4"

Example 3:

Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
          -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
          -> "F"                                    -> "F"

Solution

Use two stacks stack1 and stack2 to store the characters in expression. Loop over expression from left to right and add each character into stack1.

While stack1 contains more than one element, do operation on stack1. Each time pop two elements c1 and c2 from stack1, where c1 must be a digit or a boolean letter, and c2 must be a ? or :. If c2 is :, then there will be more elements before meeting a ?, so push c1 into stack2. If c2 is ?, then pop one more element from stack1, which must be a boolean letter. If the boolean letter is T, then c1 is the result of the current ternary expression. Otherwise, the top element of stack2 is the result of the current ternary expression. Pop one element from stack2 and push the result of the current ternary expression into stack1. Repeat the process until there is only one element in stack1.

Finally, pop the one element from stack1, convert it into a string and return.

• Java
• C++
• Python
• Go

• class Solution {
      public String parseTernary(String expression) {
          Stack<Character> stack1 = new Stack<Character>();
          Stack<Character> stack2 = new Stack<Character>();
          int length = expression.length();
          for (int i = 0; i < length; i++)
              stack1.push(expression.charAt(i));
          while (stack1.size() > 1) {
              char c1 = stack1.pop();
              char c2 = stack1.pop();
              if (c2 == ':')
                  stack2.push(c1);
              else {
                  char conditionChar = stack1.pop();
                  boolean condition = conditionChar == 'T';
                  char nextChar = condition ? c1 : stack2.peek();
                  stack2.pop();
                  stack1.push(nextChar);
              }
          }
          String value = String.valueOf(stack1.pop());
          return value;
      }
  }
  

• // OJ: https://leetcode.com/problems/ternary-expression-parser/
  // Time: O(NL) where L is the level of nesting
  // Space: O(NL)
  class Solution {
  public:
      string parseTernary(string s) {
          if (s.size() == 1) return s;
          bool left = s[0] == 'T';
          int cnt = 0, N = s.size(), i = 2;
          for (; i < N && cnt >= 0; ++i) {
              if (s[i] == '?') ++cnt;
              else if (s[i] == ':') --cnt;
          }
          return parseTernary(left ? s.substr(2, i - 3) : s.substr(i));
      }
  };
  

• class Solution(object):
    def parseTernary(self, expression):
      """
      :type expression: str
      :rtype: str
      """
      stack = []
      i = len(expression) - 1
      while i >= 0:
        if expression[i] not in ["?", ":"]:
          stack.append(expression[i])
        elif expression[i] == "?":
          i -= 1
          if expression[i] == "T":
            top = stack.pop()
            stack.pop()
            stack.append(top)
          elif expression[i] == "F":
            stack.pop()
        i -= 1
      return stack[0]
  
  

• func parseTernary(expression string) string {
  	stk := []byte{}
  	cond := false
  	for i := len(expression) - 1; i >= 0; i-- {
  		c := expression[i]
  		if c == ':' {
  			continue
  		}
  		if c == '?' {
  			cond = true
  		} else {
  			if cond {
  				if c == 'T' {
  					x := stk[len(stk)-1]
  					stk = stk[:len(stk)-2]
  					stk = append(stk, x)
  				} else {
  					stk = stk[:len(stk)-1]
  				}
  				cond = false
  			} else {
  				stk = append(stk, c)
  			}
  		}
  	}
  	return string(stk[0])
  }
  

All Problems

All Solutions