【基础练习】【栈】【映射】codevs3543 括号匹配题解

川长思鸟来 2022-08-07 02:45 93阅读 0赞

本来这是一道水题，结果因为我有些大意，弄了一个小时···引以为戒。

这道题比较特殊的一点是四种括号如果存在嵌套必须按照一定的顺序嵌套。

放代码

//codevs3543 括号匹配
    #include<stack>
    #include<cstring>
    #include<cstdio>
    #include<map>
    using namespace std;
    
    map<char,int> low;
    stack<char> s;
    int n;
    bool ok=true;
    char a[256];
    
    int main(){
    	freopen("1.txt","r",stdin);
    	freopen("2.txt","w",stdout);
    	low['<']=1;low['(']=2;low['[']=3;low['{']=4;low['>']=5;low[')']=6;low[']']=7;low['}']=8;//用map处理顺序问题，注意已有类型无法重载运算符；当然也可以函数+矩阵（from 里奥）
    	scanf("%d",&n);
    	for (int i=1;i<=n;i++){
    		ok=true;
    		scanf("%s",a);//注意没有&
    		while (!s.empty()) s.pop();//清空栈
    		int len=strlen(a);
    		int j=0;
    		while (j<len){
    			char ch=a[j];
    			if ((ch=='<')||(ch=='(')||(ch=='[')||(ch=='{')){
    				if ((s.empty())||(low[ch]<=low[s.top()])){//需检验栈是否为空
    					s.push(ch);
    				} 
    				else{
    					ok=false;
    					break;
    				}
    			}
    			else if ((!s.empty())&&(low[s.top()]==low[ch]-4)){
    				s.pop();
    			}
    			else{
    				ok=false;
    				break;
    			}
    			j++;
    		}
    		if (!s.empty()) printf("NO\n");//栈不为空，说明有左边一半括号没有匹配的情况
    		else if (ok) printf("YES\n");
    		else printf("NO\n");
    	}
    	return 0;
    }

——总角之宴，言笑晏晏。信誓旦旦，不知其反。