Giả sử chúng ta có một biểu thức chứa biểu thức bậc ba, chúng ta phải đánh giá kết quả của biểu thức. Nó hỗ trợ một số giá trị như T và F cho Đúng và Sai và “?” và các ký tự “:”. Có một số thuộc tính:
- Độ dài của chuỗi đã cho phải nhỏ hơn hoặc bằng 10000.
- Nhóm biểu thức điều kiện từ phải sang trái.
- Điều kiện sẽ luôn là T hoặc F. Vì vậy, điều kiện sẽ không bao giờ là một chữ số.
- Kết quả của biểu thức sẽ luôn đánh giá thành T hoặc F.
Vì vậy, ví dụ, nếu đầu vào là “T? T? F:T:T ”, vì vậy đầu ra sẽ là F.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- ret:=một chuỗi trống, n:=kích thước của s,
- tạo một ngăn xếp
- đối với tôi trong phạm vi n - 1 giảm xuống 0
- x:=s [i]
- nếu st không trống và trên cùng của ngăn xếp là ‘?’, thì
- xóa khỏi st
- first:=top of st, sau đó xóa hai phần tử khỏi ngăn xếp
- second:=top of stack và xóa khỏi st
- nếu x là T, thì chèn đầu tiên vào st, nếu không thì chèn thứ hai vào st
- nếu không thì chèn x vào st
- while st không trống, thì
- ret:=ret + top of st và xóa khỏi st
- đảo ngược ret và trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
#include
using namespace std;
class Solution {
public:
string parseTernary(string s) {
string ret = "";
int n = s.size();
stack 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("T?T?F:T:T"));
} Đầu vào
" T?T?F:T:T"
Đầu ra
F