Question

439. 三元表达式解析器

English Version

题目描述

给定一个表示任意嵌套三元表达式的字符串 expression ，求值并返回其结果。

你可以总是假设给定的表达式是有效的，并且只包含数字， '?' ，  ':' ，  'T' 和 'F' ，其中 'T' 为真， 'F' 为假。表达式中的所有数字都是 一位 数(即在 [0,9] 范围内)。

条件表达式从右到左分组(大多数语言中都是这样)，表达式的结果总是为数字 'T' 或 'F' 。

 

示例 1：

输入： expression = "T?2:3"
输出： "2"
解释： 如果条件为真，结果为 2；否则，结果为 3。

示例 2：

输入： expression = "F?1:T?4:5"
输出： "4"
解释： 条件表达式自右向左结合。使用括号的话，相当于：
 "(F ? 1 : (T ? 4 : 5))" --> "(F ? 1 : 4)" --> "4"
or "(F ? 1 : (T ? 4 : 5))" --> "(T ? 4 : 5)" --> "4"

示例 3：

输入： expression = "T?T?F:5:3"
输出： "F"
解释： 条件表达式自右向左结合。使用括号的话，相当于：
"(T ? (T ? F : 5) : 3)" --> "(T ? F : 3)" --> "F"
"(T ? (T ? F : 5) : 3)" --> "(T ? F : 5)" --> "F"

 

提示:

• 5 <= expression.length <= 104
• expression 由数字, 'T', 'F', '?' 和 ':' 组成
• 保证 了表达式是一个有效的三元表达式，并且每个数字都是 一位数 

解法

方法一：栈

我们从右到左遍历字符串 expression，对于当前遍历到的字符 $c$：

• 如果 $c$ 是字符 ':'，则跳过；
• 如果 $c$ 是字符 '?'，那么意味着下一个即将遍历到的字符是条件表达式的条件，我们用一个布尔变量 cond 标记；
• 如果 $c$ 的上一个遍历到的字符是 '?'，也即布尔变量 cond 为 true，那么我们判断当前字符 $c$ 是否为字符 'T'，如果是，那么我们要保留栈顶第一个元素，弹出栈顶第二个元素；否则，我们要保留栈顶第二个元素，弹出栈顶第一个元素。最后，将 cond 置为 false；
• 否则，我们将当前字符 $c$ 入栈。

最后，栈中只剩下一个元素，即为表达式的结果。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 expression 的长度。

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])
}