NC15029 吐泡泡(解析与代码)

Bertha 。 2022-11-27 08:54 139阅读 0赞

**题目描述**

链接：https://ac.nowcoder.com/acm/problem/15029
    来源：牛客网
    
    小鱼儿吐泡泡，嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡：大泡泡"O"，小泡泡"o"。
    两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。
    （是的你没看错，小气泡和大气泡不会产生任何变化的，原因我也不知道。）
    例如:ooOOoooO经过一段时间以后会变成oO。

**输入描述**

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

**输出描述**

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

通过题意,可将输入字符串分成单个字符,每个字符逐个输入,且每次输入对字符串产生的变化只与该字符相邻的元素有关,根据这个特点，我们很容易看出这是一个简单的栈模拟问题。

解题思路：  
1、栈中无元素或栈顶元素与输入元素不相同时，将输入元素压入栈。  
2、当栈非空时，判断栈顶元素是否为小泡泡‘o’且输入元素也为小泡泡,这时将栈顶元素出栈,此时并不能将合成的大泡泡’O’直接压入栈中,因为可能栈顶的小泡泡出栈后,栈顶变成了大泡泡,这时需要将大泡泡消去,若栈顶不为大泡泡时,将大泡泡压入栈中。  
3、若输入元素和栈顶元素同为大泡泡时，将栈顶元素出栈。  
4、将栈顶剩余元素逐个出栈，逆序输出结果。

**AC代码：**

#include<bits/stdc++.h>
    using namespace std;
    
    int main(){ 
        string s;
        while(cin >> s){ 
            stack<char> st;
            string str;
            st.push(s[0]);
            for(int i = 1; i < s.length(); i++){ 
                if(st.empty() || st.top() != s[i]){ 
                    st.push(s[i]);
                    continue;
                }
                if(!st.empty()&&st.top()==s[i]&&s[i]=='o'){ 
                    st.pop();
                    if(!st.empty()&&st.top()=='O') st.pop();
                    else st.push('O');
                }
                else if(!st.empty()&&st.top()==s[i]&&s[i]=='O'){ 
                    st.pop();
                }
            }
            while(!st.empty())//将栈里剩余的弹出至str中
            { 
                str+=st.top();
                st.pop();
            }
            for(int i=(int)str.length()-1;i>=0;i--)//逆序输出str
                cout<<str[i];
            cout<<endl;
        }   
    }