Bộ Phân Tích Biểu Thức Ba Ngôi Trong C++

Giả sử chúng ta có chuỗi biểu diễn biểu thức ba ngôi lồng nhau tùy ý, chúng ta phải tính kết quả của biểu thức. Biểu thức chỉ chứa chữ số 0-9, ?, :, T, F (T và F đại diện cho True và False). Các tính chất:

• Độ dài chuỗi ≤ 10000.

• Mỗi số chỉ chứa một chữ số.

• Biểu thức điều kiện nhóm từ phải sang trái.

• Điều kiện luôn là T hoặc F, không phải chữ số.

• Kết quả luôn là chữ số 0-9, T hoặc F.

Ví dụ: "F?1:T?4:5" → 4. Phân tích biểu thức phải "T?4:5" → 4, biểu thức chính thành "F?1:4" → 4.

Để giải quyết, chúng ta làm theo các bước:

• ret := chuỗi rỗng, n := độ dài s, tạo stack st.

• Với i từ n-1 xuống 0: x = s[i].

  • Nếu st không rỗng và st.top() == '?': st.pop(); first = st.top(); st.pop(); st.pop(); second = st.top(); st.pop(); nếu x == 'T' đẩy first, ngược lại đẩy second.

  • Ngược lại đẩy x vào st.

• Khi st không rỗng: ret += st.top(); st.pop().

• Đảo ngược ret và trả về.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#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;
    }
};

int main(){
    Solution ob;
    cout << (ob.parseTernary("F?1:T?4:5"));
}

Đầu vào

"F?1:T?4:5"

Đầu ra

4