Chương trình đánh giá biểu thức ba ngôi (ternary) bằng C++

Cho chuỗi biểu thức ba ngôi chứa 'T', 'F', '?', ':'. Điều kiện nhóm từ phải sang trái. Điều kiện luôn là T hoặc F. Kết quả luôn T hoặc F. Đánh giá biểu thức.

Ví dụ: "T?T?F:T:T" → F.

Giải thuật

• Duyệt chuỗi từ phải sang trái, dùng stack.
• Nếu đỉnh stack là '?': pop '?', lấy first (pop), pop ':', lấy second (pop). Nếu ký tự hiện tại 'T' push first, ngược lại push second.
• Ngược lại push ký tự hiện tại.
• Cuối cùng pop stack xây dựng kết quả, đảo ngược chuỗi.

Ví dụ minh họa

#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;
    }
};
int main(){
    Solution ob;
    cout << ob.parseTernary("T?T?F:T:T");
}

Đầu vào

"T?T?F:T:T"

Đầu ra

F