Bubble spitting problem solution

Link: https://ac.nowcoder.com/acm/problem/15029?&headNav=acm
Source: niuke.com
Time limit: 1 second for C / C + + and 2 seconds for other languages
Space limitation: C/C++ 32768K, other languages 65536K
64bit IO Format: %lld

Title Description

The little fish spit bubbles and come out. Small fish will spit out two kinds of bubbles: big bubble "O" and small bubble "O".
Two adjacent small bubbles will melt into a big bubble, and two adjacent big bubbles will burst.
(yes, you're right. Small bubbles and large bubbles won't change. I don't know why.)
For example, ooooo will become oO after a period of time.

Enter Description:

There are multiple groups of data, which are processed until the end of the file.
Each set of inputs contains a single line of string consisting only of 'o' and 'o'.

Output Description:

Each group of output contains only one line, and one line of string represents the remaining bubbles after fusion.

Example 1

input

ooOOoooO

output

oO

explain

Merge from left to right

remarks:

For 100% data,
The length of the string does not exceed 100.

Algorithm analysis:
Stack thought
Simulation:

ooOOoooO
t=o # o # empty stack, stack
t=o ^ OO - > O ^ non empty, fusion, eject o, press in o
t=O ﹐ OO - > non empty, fusion, pop up o
t=O ^ o ^ empty stack, stack
t=o , Oo , non empty, fusion, press in o
t=o ^ OOo - > OO - > non empty, fusion, pop up o, press in O, the first bit of stack and the last bit of stack can be fused, take the first bit of stack as a new temporary element, and play again (write a judgment function to judge whether the first bit of stack and the last bit of stack can be fused, if not, pass, otherwise cycle)
t=o # o # empty stack, stack
t=O ^ oO ^ non empty, fusion, press in o
At this time, the stack is arranged as follows from top to bottom
Oo
The algorithm should be output in reverse order
The reverse order output method is as follows: first output one by one to the string container, and then reverse the string
The algorithm is abstracted as follows:
i if the stack is empty, press in
ii if it is not empty, fuse and operate to judge whether the first and last bits of the stack can be fused. If yes, continue to fuse, otherwise it will be too late
If the fusion can be continued, the function parameter a becomes the first element of the stack, pop up the first element of the stack, and continue the operation
Considering that only Ooo can continue, the algorithm can be simplified
Ooo->OO
ooo->oO
Note: oo will empty the stack
Acquire knowledge points:

For stack,pop is pop-up and top is get!
The STL passed in parameters are referenced with &

#include<cstdio>
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int fuse(char a,char b) { //Fusion function, invalid operation returns 0, two small ones return 1, and two large ones return 2
	if(a=='o' && b=='O')	return 0;
	if(a=='O' && b=='o')	return 0;
	if(a=='o' && b=='o')	return 1;
	if(a=='O' && b=='O')	return 2;
}
bool judge(stack<char> a) { //Judge whether the first and last bits of the stack can be fused
	char temp;
	temp=a.top();
	a.pop();
	if(fuse(a.top(),temp))	return true;
	else return false;
}
void play(stack<char> &old,char a) { //Get the elements from the string one by one, and do the following
	if (old.empty()) { //i: If the stack is empty, press it into the stack
		old.push(a);
		return;
	} else { //ii: if it is not empty, fuse and operate to judge whether the first and last bits of the stack can be fused. If yes, continue to fuse, otherwise it will be too late
		int ans;//Store the result of fuse
		char temp=old.top();
		ans=fuse(a,temp);
		if(ans==0) {
			old.push(a);
			return;
		} else if(ans==1) {	//oo merges into O
			old.pop();
			old.push('O');
			char temp=old.top();
			old.pop();
			if(!old.empty()	&& old.top()=='O')	old.pop();
			else	old.push(temp);
		} else if(ans==2) {	//OO crushing
			old.pop();
		}
	}
	
}
string copy(stack<char> &sta) {
	string a;
	while(!sta.empty()) {
		a+=sta.top();
		sta.pop();
	}
	return a;
}
void reverseStr(string& str) //String inversion 
{ 
	int n = str.length(); 
	for (int i = 0; i < n / 2; i++) 
		swap(str[i], str[n - i - 1]); 
} 
int main() {
	string str1;
	while(cin>>str1) {
		stack<char> old;
		for(int i=0; i<str1.length(); i++) {
			char now=str1[i];
			play(old,now);
		}
		string ans;
		ans=copy(old);
		reverseStr(ans);
		cout<<ans<<endl;
	}
	return 0;
}

Keywords: C++ ICPC

Added by linfidel on Mon, 03 Jan 2022 20:27:31 +0200