首页 > 代码库 > CDZSC_2015寒假新人（4）——搜索 - P
CDZSC_2015寒假新人（4）——搜索 - P
Description
| Parentheses Balance |
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:
- (a)
- if it is the empty string
- (b)
- if A and B are correct, AB is correct,
- (c)
- if A is correct, (A ) and [A ] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.
Input
The file contains a positive integer n and a sequence of n strings of parentheses () and [], one string a line.
Output
A sequence of Yes or No on the output file.
Sample Input
3([])(([()])))([()[]()])()
Sample Output
YesNoYes
Miguel Revilla
2000-08-14
题解：栈。括号匹配问题，左括号全压栈，右括号若是与栈顶匹配，则出栈顶，否则压栈，注意输入有可能是空串，要用 gets() 或 cin.getline() 输入，这坑了我一下，英语文盲的悲剧。详见代码。
1 #include <stdio.h> 2 #include <string.h> 3 #include <stack> 4 using namespace std; 5 6 const int MAX = 256; 7 char str[MAX]; 8 int Map[MAX]; 9 10 11 int main()12 {13 #ifdef CDZSC_OFFLINE14 freopen("in.txt", "r", stdin);15 freopen("out.txt", "w", stdout);16 #endif17 Map[‘(‘] = -1; Map[‘)‘] = 1;18 Map[‘[‘] = -2; Map[‘]‘] = 2;19 20 int t, len;21 scanf("%d", &t);22 getchar();23 while(t--)24 {25 gets(str);26 27 len = strlen(str);28 stack<char> st;29 for(int i = 0; i < len; i++)30 {31 if(str[i] == ‘(‘ || str[i] == ‘[‘)32 {33 st.push(str[i]);34 }35 else36 {37 if(!st.empty() && !(Map[st.top()] + Map[str[i]]))38 {39 st.pop();40 }41 else42 {43 st.push(str[i]);44 }45 }46 }47 printf("%s\n", st.empty() ? "Yes" : "No");48 }49 return 0;50 }
CDZSC_2015寒假新人（4）——搜索 - P
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。