資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++三元表示式解析器
假設我們有一個字串，表示任意巢狀的三元表示式，我們需要計算表示式的結果。我們可以始終假設給定的表示式是有效的，並且僅包含數字 0-9、?、:、T 和 F 這幾個字元。（這裡 T 和 F 分別代表 True 和 False）。有一些屬性：
給定字串的長度必須小於或等於 10000。
每個數字只包含一位。
條件表示式從右到左分組。
條件總是 T 或 F。因此，條件永遠不會是數字。
表示式的結果將始終計算為數字 0-9、T 或 F 之一。
例如，如果輸入類似於“F?1:T?4:5”，則輸出將為 4，因為它將解析最右邊的表示式“T?4:5”，它將返回 4，然後主表示式將變為“F?1:4”，因此返回值為 4。
為了解決這個問題，我們將遵循以下步驟：
ret := 一個空字串，n := s 的大小，建立一個棧 st
for I in range n – 1 down to 0
x := s[i]
如果 st 不為空且棧頂為‘?’，則
從 st 中刪除
first := st 的棧頂，然後從棧中刪除兩個元素
second := 棧頂，並從 st 中刪除
如果 x 為 T，則將 first 插入 st，否則將 second 插入 st
否則，將 x 插入 st
當 st 不為空時
ret := ret + st 的棧頂，並從 st 中刪除
反轉 ret 並返回 ret
示例 (C++)
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string parseTernary(string s) {
string ret = "";
int n = s.size();
stack <char> st;
for(int i = n - 1; i >= 0; i--){
char x = s[i];
if(!st.empty() && st.top() == '?'){
st.pop();
char first = st.top();
st.pop();
st.pop();
char second = st.top();
st.pop();
if(x == 'T'){
st.push(first);
}
else st.push(second);
}
else{
st.push(x);
}
}
while(!st.empty()){
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
cout << (ob.parseTernary("F?1:T?4:5"));
}輸入
"F?1:T?4:5"
輸出
4
更新於：2020年4月29日
493 次瀏覽
廣告