文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 遞歸
    • 2.2 循環

1. 題目

給定一個以字符串表示的任意嵌套的三元表達式，計算表達式的值。

你可以假定給定的表達式始終都是有效的并且只包含數字 0-9, ?, :, T 和 F (T 和 F 分別表示真和假）。

注意：
給定的字符串長度 ≤ 10000。
所包含的數字都只有一位數。
條件表達式從右至左結合（和大多數程序設計語言類似）。
條件是 T 和 F其一，即條件永遠不會是數字。
表達式的結果是數字 0-9, T 或者 F。

示例 1： 輸入： "T?2:3" 輸出： "2" 解釋： 如果條件為真，結果為 2；否則，結果為 3。示例 2： 輸入： "F?1:T?4:5" 輸出： "4" 解釋： 條件表達式自右向左結合。使用括號的話，相當于："(F ? 1 : (T ? 4 : 5))" "(F ? 1 : (T ? 4 : 5))"-> "(F ? 1 : 4)" 或者 -> "(T ? 4 : 5)"-> "4" -> "4"示例 3： 輸入： "T?T?F:5:3" 輸出： "F" 解釋： 條件表達式自右向左結合。使用括號的話，相當于："(T ? (T ? F : 5) : 3)" "(T ? (T ? F : 5) : 3)"-> "(T ? F : 3)" 或者 -> "(T ? F : 5)"-> "F" -> "F"

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ternary-expression-parser
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 遞歸

兩種符號? :數量相等的時候，將字符串切開，遞歸考慮

class Solution { public:string parseTernary(string expression) {int c1 = 0, c2 = 0, n = expression.size();for(int i = 1; i < n; ++i){if(expression[i]=='?')c1++;else if(expression[i]==':')c2++;if(c1 == c2){return expression[0]=='T' ? parseTernary(expression.substr(2, i-2)) : parseTernary(expression.substr(i+1));}}return expression;} };

2.2 循環

• 參考評論區解答
• 逆序遍歷，每次 i - 2 找符號
• ： 把后面的數壓棧，？把前面的數更新為表達式的值，并彈棧

class Solution { public:string parseTernary(string expression) {stack<char> s1;for(int i = expression.length() - 1; i >= 2; i -= 2)//找?或者:{if(expression[i-1] == ':')//當前是 :s1.push(expression[i]);else//當前是?{expression[i-2] = expression[i-2] == 'T' ? expression[i] : s1.top();// ? 前面 更新為表達式的值s1.pop();}}return string(1,expression[0]);} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 439. 三元表达式解析器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。