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


题目

题目描述:
小鱼儿吐泡泡,嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡:大泡泡"O",小泡泡"o"。
两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。
(是的你没看错,小气泡和大气泡不会产生任何变化的,原因我也不知道。)
例如:ooOOoooO经过一段时间以后会变成oO。

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

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


解析

知识点

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

算法解析

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

操作分析

  1. 从前往后遍历栈,我们就是碰到相同即操作,不同即进栈就行了(同上面例子)。
  2. 操作咋的操作?首先我们就判断一波是不是空栈,是空的就没啥可以比较的了呀,就入栈跳过呗:
    if (st.empty()) {
        st.push(ch);
        continue;
    }  
  3. 如果不是,我们就把当前的值取出来做个比较,如果都是小泡泡就合成大泡泡,如果都是大泡泡就炸掉
    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'用于判断前面还有没有大泡泡可以炸掉。最后判断时除了如果不是炸掉的话就入栈呗(包括变成了大泡泡时前面为空和前面是小泡泡)。
  4. 最后栈倒过来一下再输出就好了。

打代码

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


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;
}
//函数区