括号匹配

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述: 现在，有一行括号序列，请你检查这行括号是否配对。

输入

第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

样例输入

3
[(])
(])
([[]()])

样例输出

No
No
Yes

 1 #include <stdlib.h>
 2 #include <stdio.h>
 3 #include <string>
 4 #include <string.h>
 5 #include <iostream>
 6 #include <stack>
 7 using namespace std;
 8 #define debug(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
 9 
10 int main(void) {
11     int N;
12     scanf("%d", &N);
13     getchar();
14     while (N--) {
15         char S[10001];
16         memset(S, 0x00, sizeof(S));
17         scanf("%s", S);
18         getchar();
19         int len = strlen(S);
20         //cout << len << endl;
21         stack<char> sch;
22         //cout << sch.size() << endl;
23         //length(size)
24         for (int i = 0; i < len; ++i) {
25             if(S[i] == '[' || S[i] == '('){
26                 sch.push(S[i]);
27             }else if(S[i] == ']'){
28                 if(!sch.empty()){
29                     if(sch.top() == '['){
30                         sch.pop();
31                     }else {
32                         sch.push(S[i]);
33                         break;
34                     }
35                 }else {
36                     sch.push(S[i]);
37                     break;
38                 }
39             }else if (S[i] == ')') {
40                 if(!sch.empty()){
41                     if(sch.top() == '('){
42                         sch.pop();
43                     }else {
44                         sch.push(S[i]);
45                         break;
46                     }
47                 }else {
48                     sch.push(S[i]);
49                     break;
50                 }
51             }
52         }
53 
54         if(sch.size() == 0){
55             printf("Yes
");
56         }else {
57             printf("No
");
58             //cout << sch.size() << endl;
59         }
60     }
61     return 0;
62 }

View Code

上面代码优化:

 1 #include <stdlib.h>
 2 #include <stdio.h>
 3 #include <string>
 4 #include <string.h>
 5 #include <iostream>
 6 #include <stack>
 7 using namespace std;
 8 #define debug(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
 9 
10 int main(void) {
11     int N;
12     scanf("%d", &N);
13     getchar();
14     while (N--) {
15         char S[10001];
16         memset(S, 0x00, sizeof(S));
17         scanf("%s", S);
18         getchar();
19         int len = strlen(S);
20         //cout << len << endl;
21         stack<char> sch;
22         //cout << sch.size() << endl;
23         //length(size)
24         for (int i = 0; i < len; ++i) {
25             if(S[i] == '[' || S[i] == '('){
26                 sch.push(S[i]);
27             }else if(S[i] == ']'){
28                 if(!sch.empty() && sch.top() == '['){ 
29                     sch.pop();
30                 }else {
31                     sch.push(S[i]);
32                     break;
33                 }
34             }else if (S[i] == ')') {
35                 if(!sch.empty() && sch.top() == '('){
36                     sch.pop();
37                 }else {
38                     sch.push(S[i]);
39                     break;
40                 }
41             }
42         }
43         
44         if(sch.size() == 0){
45             printf("Yes
");
46         }else {
47             printf("No
");
48             //cout << sch.size() << endl;
49         }
50     }
51     return 0;
52 }

View Code



//优秀代码 C++

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
	int n;
	cin>>n;
	while(n--)
	{	
		vector<char> vec;
		string ch;
		vec.push_back(' ');
		cin>>ch;
		for(int i=0;i<ch.length();i++)
		{
			vec.push_back(ch[i]);
　　　　　　　　　　　　//　()[]  $3 = std::vector of length 3, capacity 4 = {32 ' ', 40 '(', 41 ')'}
　　　　　　　　　　　　//$5 = std::vector of length 3, capacity 4 = {32 ' ', 91 '[', 93 ']'}
		    if( vec.back()-1 == *(vec.end()-2) || vec.back()-2 == *(vec.end()-2))
			{
				vec.pop_back();
				vec.pop_back();
			}
		}
		if(vec.size()==1)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}      

//v1.1  C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define STACK_SIZE 10000
typedef struct STACK{
  char stack[STACK_SIZE];
  int pointer;
}STSTACK;
STSTACK stack;
void push(char ch);
char pop();

int main(int argc, char *argv[])
{
  int num;
  int i;
  char buf[STACK_SIZE]={0};
  scanf("%d",&num);
  getchar();
  
  for(i = 0;i < num;i++){
      memset(stack.stack, 0x00, STACK_SIZE);
      stack.pointer = -1;
      scanf("%s", buf);
      getchar();
      int len = strlen(buf);
      int j;
      int flag=1;
      for(j = 0;j < len;j++){
          char tmp;
          if(buf[j] == '[' || buf[j] == '('){
              push(buf[j]);
              
            }else if (buf[j] == ']') {
              if(stack.pointer == -1){
                  flag = 0;
                  break;
                }
              tmp = pop();
              if(tmp != '['){
                  flag = 0;
                  break;
                }/*else if(tmp == '['){
                        continue;
                      }*/
              
            }else if (buf[j] == ')') {
              if(stack.pointer == -1){
                  flag = 0;
                  break;
                }
              tmp = pop();
              if(tmp != '('){
                  flag = 0;
                  break;
                }/*else if(tmp == '('){
                        continue;
                      }*/
            }
        }
      
      
      if(stack.pointer == -1 && flag){
          printf("Yes
");
        }else{
          printf("No
");
        }
      
    }
  return 0;
}

void push(char ch){
  stack.stack[++stack.pointer] = ch;
}

char pop(){
  return stack.stack[stack.pointer--];
}

//V1.0调试通过版 C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define STACK_SIZE 10000
typedef struct STACK{
  char stack[STACK_SIZE];
  int pointer;
}STSTACK;
STSTACK stack;
void push(char ch);
char pop();

int main(int argc, char *argv[])
{
  int num;
  int i;
  char buf[STACK_SIZE]={0};
  scanf("%d",&num);
  getchar();

  for(i = 0;i < num;i++){
      memset(stack.stack, 0x00, STACK_SIZE);
      stack.pointer = -1;
      scanf("%s", buf);
      getchar();
      int len = strlen(buf);
      //printf("%d
",len);
      int j;
      int flag=1;
      for(j = 0;j < len;j++){
          char tmp;
          if(buf[j] == '[' || buf[j] == '('){
              push(buf[j]);

            }else if (buf[j] == ']') {
              if(stack.pointer == -1){
                  //--stack.pointer;
                  flag = 0;
                  //printf("No
");
                  break;
                }
              tmp = pop();
              if(tmp != '['){
                  //push(tmp);
                  //printf("No
");
                  flag = 0;
                  break;
                }/*else if(tmp == '['){
                        continue;
                      }*/

            }else if (buf[j] == ')') {
              if(stack.pointer == -1){
                 // --stack.pointer;
                  flag = 0;
                  //printf("No
");
                  break;
                }
              tmp = pop();
              if(tmp != '('){
                  //push(tmp);
                  //printf("No
");
                  flag = 0;
                  break;
                }/*else if(tmp == '('){
                        continue;
                      }*/
            }
        }


      if(stack.pointer == -1 && flag){
          printf("Yes
");
        }else{
                printf("No
");
            }

    }
  return 0;
}

void push(char ch){
  stack.stack[++stack.pointer] = ch;
}

char pop(){
  return stack.stack[stack.pointer--];
}




//v0.01 调试版
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define STACK_SIZE 10000

typedef struct STACK{

    char stack[STACK_SIZE];

    int pointer;

}STSTACK;

STSTACK stack;

void push(char ch);

char pop();

int main(int argc, char *argv[])

{

    int num;

    int i;

    char buf[STACK_SIZE]={0};

    scanf("%d",&num);

    getchar();

    for(i = 0;i < num;i++){

        memset(stack.stack, 0x00, STACK_SIZE);

        stack.pointer = -1;

        scanf("%s", buf);

        getchar();

        int len = strlen(buf);

        int j;

        if(buf[0] == ']' || buf[0] == ')'){
            printf("No
");
        }else{
            push(buf[0]);

            for(j = 1;j < len;j++){
                char tmp;
                if(buf[j] == '[' || buf[j] == '('){
                    push(buf[j]);
                }else if (buf[j] == ']') {

                    if(stack.pointer < 0){

                        printf("No
");

                        break;

                    }

                    tmp = pop();

                    if(tmp != '['){
                        push(tmp);
                        break;
                    }

                }else if (buf[j] == ')') {

                    if(stack.pointer < 0){
                        printf("No
");
                        break;
                    }

                    tmp = pop();

                    if(tmp != '('){
                        push(tmp);
                        break;
                    }

                }

            }

            if(stack.pointer == -1){

                printf("Yes
");

            }else{

                printf("No
");

            }

        }

    }

    return 0;

}

void push(char ch){

    if(stack.pointer >= STACK_SIZE-1){

        printf("top overflow!
");

        exit(1);

    }

    stack.stack[++stack.pointer] = ch;

}

char pop(){

    return stack.stack[stack.pointer--];

}