括号匹配
HRBUST - 1549
给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。
Input
输入数据有多组，每组数据不超过100个字符并含有( ,) ,[, ],{, }一个或多个。处理到文件结束。
Output
如果匹配就输出“yes”，不匹配输出“no”
Input
sin(20+10)
{[}]
Output
yes
no
?
思路：输入字符串后，用栈，如果字符串里有(,[,{,就压进栈，否则就弹出栈顶元素看是否匹配，如果匹配就弹出栈顶元素，直到检查完毕
特殊情况
1? ?））如果是以右半边括号开头的话就直接判断成不匹配
2 （））如果在匹配过程中有栈为空，然后下一个括号也是右半边的就直接判为不匹配
#include<stdio.h>
#include<iostream>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
?? ?char str1[101010];
?? ?stack<char>S;
?? ?
?? ?while(~scanf("%s",str1))
?? ?{
?? ??? ?while(!S.empty())
?? ??? ?{
?? ??? ??? ?S.pop();
?? ??? ?}
?? ??? ?if(str1[0] == '}' || str1[0] == ']' || str1[0] == ')')
?? ??? ?{
?? ??? ??? ?printf("NO\n");
?? ??? ??? ?continue;
?? ??? ?}
?? ??? ?int flag=0;
?? ??? ?for(int i=0; i<strlen(str1); i++)
?? ??? ?{?? ?
?? ??? ??? ?char str2;
?? ??? ??? ?if(str1[i] == ')')
?? ??? ??? ?{
?? ??? ??? ??? ?if(!S.empty())
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?str2 = S.top();
?? ??? ??? ??? ??? ?if(str2 == '(')
?? ??? ??? ??? ??? ??? ?S.pop();?? ?
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?printf("NO\n");
?? ??? ??? ??? ??? ?flag=1;
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?else if(str1[i] == ']')
?? ??? ??? ?{
?? ??? ??? ??? ?if(!S.empty())
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?str2 = S.top();
?? ??? ??? ??? ??? ?if(str2 == '[')
?? ??? ??? ??? ??? ??? ?S.pop();?? ?
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?printf("NO\n");
?? ??? ??? ??? ??? ?flag=1;
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?
?? ??? ??? ?}
?? ??? ??? ?else if(str1[i] == '}')
?? ??? ??? ?{
?? ??? ??? ??? ?if(!S.empty())
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?str2 = S.top();
?? ??? ??? ??? ??? ?if(str2 == '{')
?? ??? ??? ??? ??? ?S.pop();?? ??? ?
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?printf("NO\n");
?? ??? ??? ??? ??? ?flag=1;
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?else if( (str1[i] == '(') || (str1[i] == '[') || (str1[i] == '{'))
?? ??? ??? ?{
?? ??? ??? ??? ?S.push(str1[i]);
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ??? ?continue;
?? ??? ?}
?? ??? ?if(!flag)
?? ??? ?{
?? ??? ??? ?if(S.size() == 0)
?? ??? ??? ??? ?printf("YES\n");
?? ??? ??? ?else
?? ??? ??? ??? ?printf("NO\n");?? ?
?? ??? ?}
?? ?}
}
|