【练习】吐泡泡

吐泡泡

https://ac.nowcoder.com/acm/problem/15029

这道题明明很简单的，我却被牛牛难得一见的多组输入卡到自闭，一度怀疑自己是不是sb

题目

题目描述：
小鱼儿吐泡泡，嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡：大泡泡"O"，小泡泡"o"。

两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。

（是的你没看错，小气泡和大气泡不会产生任何变化的，原因我也不知道。）

例如:ooOOoooO经过一段时间以后会变成oO。

输入描述：

数据有多组，处理到文件结束。
每组输入包含一行仅有'O'与'o'组成的字符串。

输出描述：

每组输出仅包含一行，输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。

解析

知识点

这道题就是一道简单的栈操作。

算法解析

这道题，我们可以看到，是相邻的两个都是小泡泡就要变成大泡泡，都是大泡泡就要删除。
有过题目经验的我，一看就知道的关于栈的题目：因为题目如果从前往后操作，可以逐个进行判断。
栗子：先入栈o，然后入栈o，发现都是小泡泡，然后合成为大泡泡，并且这个大泡泡前面没有大泡泡，所以将O入栈。然后入栈O，就爆炸了，无入栈。

操作分析

从前往后遍历栈，我们就是碰到相同即操作，不同即进栈就行了（同上面例子）。
操作咋的操作？首先我们就判断一波是不是空栈，是空的就没啥可以比较的了呀，就入栈跳过呗：
```
if (st.empty()) {
    st.push(ch);
    continue;
}  
```
如果不是，我们就把当前的值取出来做个比较，如果都是小泡泡就合成大泡泡，如果都是大泡泡就炸掉：
```
while (ch == top) {
    if ('o' == ch) {
        st.pop();
        ch = 'O';
    }
    else {
        st.pop();
        flag = 1;
        break;
      }
    if (st.empty()) break;
        top = st.top();
    }
    if (!flag) st.push(ch);
}
```
这里合并ch为'O'用于判断前面还有没有大泡泡可以炸掉。最后判断时除了如果不是炸掉的话就入栈呗（包括变成了大泡泡时前面为空和前面是小泡泡）。
最后栈倒过来一下再输出就好了。

打代码

首先输入，多组输入搞死我，我没看到，我说怎么只过了40%。
然后就对数组每一位进行个遍历了。从前往后。
接下来按照我讲的栈操作进行操作。
看完代码咯~

AC代码

#include <iostream>
#include <stack>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

stack<char> st, tmp;
//全局变量区

int main() {
    IOS;
    string s; 
    while (cin >> s) {
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch = s[i];
            if (st.empty()) {
                st.push(ch);
                continue;
            }             char top = st.top();
            bool flag = 0;//表示不是炸裂开的
            while (ch == top) {
                if ('o' == ch) {
                    st.pop();
                    ch = 'O';
                }
                else {
                    st.pop();
                    flag = 1;
                    break;
                }
                if (st.empty()) break;
                top = st.top();
            }
            if (!flag) st.push(ch);
        }
        while (!st.empty()) {
            tmp.push(st.top());
            st.pop();
        }
        while (!tmp.empty()) {
            cout << tmp.top();
            tmp.pop();
        }
        cout << endl;
    }
    return 0;
}
//函数区

牛客算法竞赛入门课题解文章被收录于专栏

憨憨的专栏