STL-堆与栈（初稿）

例题1：火车进站问题

Problem Description
假设杭州东火车站只有一条铁路，并且所有火车都从一侧进来，从另一侧出去。那么，如果火车A先进站，然后火车B在火车A离开之前就进站，那么火车A直到火车B离开后才能离开，可参见下图。

现在，假设车站中有n（n<=9）列火车，所有火车都有一个ID（从1到n的编号），火车以O1的顺序进站，您的任务是确定火车是否可以按O2顺序出站。

Input
输入包含几个测试用例。

每个测试用例均包含三部分：一个表示火车数量的整数和两个字符串O1和O2，其中，火车的进站顺序用O1串表示，火车的出站顺序用O2串表示。

输入在文件末尾终止，更多信息参见样例。

Output
如果不能从O1的入站顺序得到O2的出站顺序，请输出字符串“ No.”。

如果能够得到，则请输出”Yes.”
然后输出进站和出站的具体方式（“in”表示火车进站，“out”表示火车出站）。
在每个测试用例之后输出一行“ FINISH”。

更多信息参见样例。


输入样例
3 123 321
3 123 312
输出样例
Yes.
in
in
in
out
out
out
FINISH
No.
FINISH

解题思路：用进栈出栈模拟进站出站。

源码：

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	while(cin>>n){
	string s1,s2;
	queue<char> q1,q2;
	queue<string>opt;
	stack<char> st;
		cin>>s1>>s2;
		for(int i=0;i<n;i++){
			q1.push(s1[i]);
			q2.push(s2[i]);
		}
		while(!q1.empty()){//确保车辆都进站了 
			while(!st.empty()&&st.top()==q2.front()){
				opt.push("out");
				st.pop();
				q2.pop();
			}//同时出栈出堆 
			char ch=q1.front();
			if(ch!=q2.front()){
				st.push(ch);
				opt.push("in");
				q1.pop();//q1出堆入栈， 
			}
			else{
				opt.push("in");
				opt.push("out");
				q1.pop();
				q2.pop();
			}
		}
		while(!q2.empty()){
			if(q2.front()!=st.top()){
					printf("No.\n");
					break;
			}
			else{
				opt.push("out");
				st.pop();
				q2.pop();
			}
		}
		if(st.size()==0){
			printf("Yes.\n");
			while(!opt.empty()){
				cout<<opt.front()<<endl;
				opt.pop();
			}
		}
	
			printf("FINISH\n");
	}
}

例题2：括号匹配问题

Problem Description
I’m out of stories. For years I’ve been writing stories, some rather silly, just to make simple problems look difficult and complex problems look easy. But, alas, not for this one.
You’re given a non empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition for being stable is as follows:

An empty string is stable.
If S is stable, then {S} is also stable.
If S and T are both stable, then ST (the concatenation of the two) is also stable.
All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{.
The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa.
Input
Your program will be tested on one or more data sets. Each data set is described on a single line. The line is a non-empty string of opening and closing braces and nothing else. No string has more than 2000 braces. All sequences are of even length.
The last line of the input is made of one or more ’-’ (minus signs.)

Output
For each test case, print the following line:
k. N
Where k is the test case number (starting at one,) and N is the minimum number of operations needed to convert the given string into a balanced one.
Note: There is a blank space before N.


输入样例
}{
{}{}{}
{{{}
---
输出样例
1. 2
2. 0
3. 1

源码：

#include<bits/stdc++.h>
using namespace std;
string s;//贪心+模拟堆
int id=1;
int main()
{
  while(cin>>s){
  	if(s[0]=='-')break;
  	int num=0,l=0;//l指堆内左括号的个数，num指操作数 
  	for(int i=0;i<s.size();i++){
  		if(s[i]=='{')l++;
  		else{
  			if(l)l--;//能出就出队 
  			else{
  				num++;//操作一次 
  				l++;
			  }
		  }
	  }
	  printf("%d. %d\n",id++,num+l/2);//num是贪心操作下的次数，l是操作后的等效情况。 
  }
  return 0; 
}