Ternary Expression Parser ใน C++ : แปลงนิพจน์ Ternary Nested ให้เป็นค่า

ให้ String แทน **Ternary Expression แบบ Nested** ประกอบด้วย 0-9, ?, :, T, F (T=True, F=False) คำนวณค่าของ Expression

กฎ:

• Group Right-to-Left (Right Associative)
• Condition จะเป็น T หรือ F เท่านั้น (ไม่ใช่ Digit)
• Result จะเป็น Digit, T, หรือ F

ตัวอย่าง

"F?1:T?4:5"

1. Parse ขวาสุด: "T?4:5" -> Condition T -> Result 4
2. Expression กลายเป็น "F?1:4" -> Condition F -> Result 4

Output: 4

อัลกอริทึม: Stack + Right-to-Left Scan

สแกน String **จากขวาไปซ้าย** ใช้ Stack:

1. Push Char ทุกตัวเข้า Stack
2. เจอ '?' บน Stack Top -> พบ Ternary Operator:
   • Pop '?'
   • Pop first (True Branch)
   • Pop ':' (Separator)
   • Pop second (False Branch)
   • ดู Condition (Char ปัจจุบัน x):
     • x == 'T' -> Push first
     • x == 'F' -> Push second
3. จบลูป -> Stack เหลือ 1 Char -> Reverse -> Result

ตัวอย่างโค้ด 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();           // Remove '?'
                char first = st.top(); st.pop(); // True value
                st.pop();           // Remove ':'
                char second = st.top(); st.pop(); // False value

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

Input / Output

Input:  "F?1:T?4:5"
Output: 4

ความซับซ้อน (Complexity)

• Time: O(N) — Scan 1 รอบ, Stack Ops O(1)
• Space: O(N) — Stack

จุดสำคัญ

Right-to-Left Scan + Stack จัดการ Right-Associativity ได้โดยธรรมชาติ เพราะเรา Resolve Inner Expression ก่อน (อยู่ขวา) แล้วค่อยนำไปใช้กับ Outer Expression (อยู่ซ้าย) ครับ