WLACM 1079: 括弧匹配检验栈入门

àì夳堔傛蜴生んèń 2022-05-20 09:43 112阅读 0赞

> ## 1079: 括弧匹配检验 ##
> 
> 时间限制: 1 Sec 内存限制: 128 MB  
> \[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]\[命题人: 外部导入\]
> 
> ## 题目描述 ##
> 
> 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如(\[\]())或\[(\[\]\[\])\]等为正确的匹配，\[(\])或(\[\]()或(()))均为错误的匹配。
> 
> 现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？
> 
> 输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “OK”，不匹配就输出“Wrong”。
> 
> 输入一个字符串：\[(\[\]\[\])\]，输出：OK
> 
> ## 输入 ##
> 
> 输入仅一行字符（字符个数小于255）
> 
> ## 输出 ##
> 
> 匹配就输出 “OK” ，不匹配就输出“Wrong”。
> 
> ## 样例输入 ##
> 
>     [(])
> 
> ## 样例输出 ##
> 
>     Wrong
> 
> ## 来源 ##
> 
> [栈和队列][Link 4]

## 此题常规循环一看就很难做，但是括号匹配容易让人想到栈，考虑用栈来写。 ##

#include <iostream>
    #include<cstring>
    #include<stack>
    using namespace std;
    //<>,(),[],{}
    char fan(char a){
    	if(a=='<')
    		return '>';
    	else if (a=='(')
    		return ')';
    	else if(a=='[')
    		return ']';
    	else if(a=='{')
    		return '}';
    	else if(a=='>')
    		return '<';
    	else if (a==')')
    		return '(';
    	else if(a==']')
    		return '[';
    	else if(a=='}')
    		return '{';
    	 
    }
    int main(int argc, char *argv[])
    {
    	char s[256];
    	int n,j,i;
    	scanf("%d",&n);
    	for(i=0;i<n;i++){
    		stack <char> a;
    		scanf("%s",s);
    		int l=strlen(s);
    		for(j=0;j<l;j++){
    			if(a.empty()){
    				if(s[j]=='<'||s[j]=='('||s[j]=='['||s[j]=='{')
    					a.push(s[j]);
    				else{
    					printf("NO\n");
    					break;
    				}
    			}
    			else{
    				if(s[j]=='<'||s[j]=='('||s[j]=='['||s[j]=='{'){
    					if(s[j]=='{'&&(a.top()=='{'))
    						a.push(s[j]);
    					else if(s[j]=='['&&(a.top()=='['||a.top()=='{'))
    						a.push(s[j]);
    					else if(s[j]=='('&&(a.top()=='('||a.top()=='['||a.top()=='{'))
    						a.push(s[j]);
    					else if(s[j]=='<'&&(a.top()=='<'||a.top()=='('||a.top()=='['||a.top()=='{'))
    						a.push(s[j]);
    				}
    				else{
    					if(a.top()!=fan(s[j])){
    						printf("NO\n");
    						break;
    					}
    					else
    						a.pop();
    					
    				}
    			}
    				
    			
    			
    			
    		}
    		if(j==l&&a.empty())
    			printf("YES\n");
    		else if(j==l)
    			printf("NO\n");
    	}	
    	return 0;
    }

## 此题为栈入门题，对于常规的栈增加了括号数量与括号顺序。 ##

## 这题还没想到很快的方法。。。这么长的代码写的头都痛了。。。。 ##

[Link 1]: http://wlacm.com/submitpage.php?id=1079
[Link 2]: http://wlacm.com/problemstatus.php?id=1079
[Link 3]: http://wlacm.com/bbs.php?pid=1079
[Link 4]: http://wlacm.com/problemset.php?search=%E6%A0%88%E5%92%8C%E9%98%9F%E5%88%97