โปรแกรมประเมินนิพจน์ Ternary ใน C++

มีนิพจน์ Ternary ประกอบ T, F, ?, : ประเมินผลลัพธ์ (T/F) กลุ่มขวาไปซ้าย

เช่น "T?T?F:T:T" ให้ F

ขั้นตอนการแก้ปัญหา

• อ่านสตริงจากขวาไปซ้าย ใช้ Stack
• เจอ ? : pop ?, first=pop, pop :, second=pop
• ถ้าตัวอักษรปัจจุบัน T push first มิฉะนั้น push second
• มิฉะนั้น push ตัวอักษรปัจจุบัน
• ท้ายสุด pop ทั้ง stack รวมเป็นสตริง reverse คืนค่า

ตัวอย่างโค้ด

#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("T?T?F:T:T");
}

อินพุต

"T?T?F:T:T"

เอาต์พุต

F