题解 | 吐泡泡

#include <iostream>
#include <stack>
using namespace std;
// 判断栈顶的两个元素是否均为两个大泡泡O
bool isDelBig(stack<char>& astk) {

    if (astk.size() <= 1) return false;  // 如果栈中元素少于2，则返回false

    char tem = astk.top();
    if (tem != 'O') return false;  // 如果栈顶不是大泡泡立刻返回fasle

    astk.pop();
    if (astk.top() == 'O') {  // 第二个栈顶元素也是大泡泡，返回true
        astk.push(tem);
        return true;
    }
    astk.push(tem);
    return false;
}
int main() {
    int T;
    cin >> T;
    stack<char> stk_char;
    while (T--) {
        string s;
        cin >> s;
        for (int i = 0; i < s.size(); i++) {  // 遍历字符串
            if (stk_char.empty()) stk_char.push(s[i]);  // 空栈没有可以合并或爆炸的，立即压入当前元素，看下一个
            else {
                char top = stk_char.top();
                if (s[i] == top) {  // 栈顶元素与当前字符相同才会涉及到合并或爆炸，不相同直接压入栈
                    if (top == 'O') stk_char.pop();  // 栈顶元素和当前元素都是大泡泡，直接爆炸，出栈栈顶元素
                    else { // 栈顶元素和当前元素都是小泡泡
                        // 小泡泡先合并成为大泡泡
                        stk_char.pop();
                        stk_char.push('O');
                        // 然后检查栈顶是否有两个大泡泡，如果有两个大泡泡直接爆炸，出栈栈顶两个元素
                        while (isDelBig(stk_char)) {  // 直到栈顶两个元素不是两个大泡泡为止
                            stk_char.pop();
                            stk_char.pop();
                        }
                    }

                } else {
                    stk_char.push(s[i]);
                }
            }
        }  // for

        // 逆序输出字符
        string res = "";
        while (!stk_char.empty()) {
            res = stk_char.top() + res;
            stk_char.pop();
        }
        cout << res << endl;
    }
}
// 64 位输出请用 printf("%lld")

当前字符需要与前一个字符比较，因此借助栈来辅助。解题思路为，当前字符与栈顶字符比较，如果不相同直接将当前字符入栈，如果相同需要判断合并(小泡泡)或爆炸(大泡泡)。爆炸仅需出栈栈顶大泡泡，而合并不仅需要出栈栈顶元素小泡泡再入栈大泡泡，还需要判断入栈大泡泡之后，是否会与栈顶第二个元素发生爆炸。最后输出字符串的时候不要忘记逆序输出