3032: 扩号匹配问题

解题思路:
先看一下题目，要求将不能匹配的括号在下面标出来，不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注。、

例如：((ABCD(x)，前面两个左括号不能匹配，所以打印出来是这样的：

((ABCD(x)
$$

一行为一组数据。

括号匹配问题使用栈来做，将左括号依次入栈，在入栈过程中如果出现右括号则最后入栈的左括号（在栈顶的左括号出栈）。

为了方便记录位置，所有栈定义的是int类型，用来标记下标位置。

参考代码:

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

int main () {
	string s;
	while(cin>>s){//多组数据
		stack<int>st;//左 
		stack<int>sk;//右 
		for(int i=0;i<s.size();i++){
			if(s[i]=='(')st.push(i);
			if(s[i]==')'){
				sk.push(i);
				if(!st.empty()){//如果左括号栈不为空
					st.pop();//左右括号消除一组
					sk.pop();
				} 
			}
		}

		cout<<s<<endl;//打印原字符串
		int p[s.size()+7];//标记第二行问题括号的位置
		memset(p,0,sizeof(p));//初始化为0
		
		while(!st.empty())p[st.top()]=-1,st.pop();//左括号位置记为-1
		while(!sk.empty())p[sk.top()]=-2,sk.pop();//右括号位置记为-2
		
		for(int i=0;i<s.size();i++){//打印
			if(p[i]==0)cout<<" ";
			if(p[i]==-1)cout<<"$";
			if(p[i]==-2)cout<<"?";
		}
		cout<<endl; 
	}


	return 0;
}