Question

439. Ternary Expression Parser

中文文档

Description

Given a string expression representing arbitrarily nested ternary expressions, evaluate the expression, and return _the result of it_.

You can always assume that the given expression is valid and only contains digits, '?', ':', 'T', and 'F' where 'T' is true and 'F' is false. All the numbers in the expression are one-digit numbers (i.e., in the range [0, 9]).

The conditional expressions group right-to-left (as usual in most languages), and the result of the expression will always evaluate to either a digit, 'T' or 'F'.

 

Example 1:

Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

Input: expression = "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 : 4)" --> "4"
or "(F ? 1 : (T ? 4 : 5))" --> "(T ? 4 : 5)" --> "4"

Example 3:

Input: expression = "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 ? F : 3)" --> "F"
"(T ? (T ? F : 5) : 3)" --> "(T ? F : 5)" --> "F"

 

Constraints:

• 5 <= expression.length <= 104
• expression consists of digits, 'T', 'F', '?', and ':'.
• It is guaranteed that expression is a valid ternary expression and that each number is a one-digit number.

Solutions

Solution 1

class Solution:
  def parseTernary(self, expression: str) -> str:
    stk = []
    cond = False
    for c in expression[::-1]:
      if c == ':':
        continue
      if c == '?':
        cond = True
      else:
        if cond:
          if c == 'T':
            x = stk.pop()
            stk.pop()
            stk.append(x)
          else:
            stk.pop()
          cond = False
        else:
          stk.append(c)
    return stk[0]

class Solution {
  public String parseTernary(String expression) {
    Deque<Character> stk = new ArrayDeque<>();
    boolean cond = false;
    for (int i = expression.length() - 1; i >= 0; --i) {
      char c = expression.charAt(i);
      if (c == ':') {
        continue;
      }
      if (c == '?') {
        cond = true;
      } else {
        if (cond) {
          if (c == 'T') {
            char x = stk.pop();
            stk.pop();
            stk.push(x);
          } else {
            stk.pop();
          }
          cond = false;
        } else {
          stk.push(c);
        }
      }
    }
    return String.valueOf(stk.peek());
  }
}

class Solution {
public:
  string parseTernary(string expression) {
    string stk;
    bool cond = false;
    reverse(expression.begin(), expression.end());
    for (char& c : expression) {
      if (c == ':') {
        continue;
      }
      if (c == '?') {
        cond = true;
      } else {
        if (cond) {
          if (c == 'T') {
            char x = stk.back();
            stk.pop_back();
            stk.pop_back();
            stk.push_back(x);
          } else {
            stk.pop_back();
          }
          cond = false;
        } else {
          stk.push_back(c);
        }
      }
    }
    return {stk[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])
}