方法一：O(N^2)

思路非常的直觀：如何將問題減而治之(Decrease and Conquer)

1. 找到outter most的表達(dá)式
2. 找到兩個(gè)sub express，子問題用遞歸求解

關(guān)鍵問題：

1. 既然是遞歸，那么base是？
   1. 當(dāng)沒有question mark，直接返回
   2. 當(dāng)只有1個(gè)question mark，可以直接判斷
2. 如何找到outter most的表達(dá)式?
   利用題目的信息“The conditional expressions group right-to-left”，因此最左邊的question mark即為outter most
3. 如何找到對(duì)應(yīng)question mark的colon？
   pair matching問題，可以用: 1) counting 2) Stack

復(fù)雜度：
由于在找配對(duì)question mark的時(shí)候需要遍歷字符串，因此O(N^2)

方法二：優(yōu)化

思路：類似于表達(dá)式評(píng)估，利用兩個(gè)stack，一個(gè)conditionStack，另一個(gè)operantStack

1. 如果是condition: 
  conditionStack入棧
2. 如果是colon：
  conditionStack出棧
  1) 如果condition為T：將指針skip to corresponding colon(即跳過表達(dá)式的第二部分)
  2) 如果condition為F：operantStack出棧，因?yàn)槔锩娴臄?shù)不再是結(jié)果考慮的對(duì)象
3. 其他
  operant入棧

返回operantStack.peek()

關(guān)鍵問題：

如何跳過表達(dá)式的第二部分？利用pair matching的counting

// skip i to corresponding colon position
int cnt = 1;
while (i + 1 < expression.length()) {
  if (expression.charAt(i + 1) == ':' && --cnt == 0) break;
  else if (expression.charAt(i + 1) == '?') cnt++;
  i++;
}

需要注意的是對(duì)i + 1進(jìn)行判斷而不是i，因?yàn)橥鈱友h(huán)會(huì)i++

時(shí)間復(fù)雜度：
由于只需要一次對(duì)字符串的一次遍歷，因此O(N)