Given a string of balanced parentheses output all the matching pairs.（给定一串平衡括号，输出所有匹配对。）

Input

A string consisting of only parentheses '(' and ')'. The parentheses are balanced and the length of the string is no more than 100000.（只有括号‘(’和‘)’的字符串。括号是平衡的，字符串的长度不超过100000）

Output

For each pair of matched parentheses output their positions in the string.（对于每一对匹配的括号，输出它们在字符串中的位置。）

Sample Input

(())()()

Sample Output

1 4  
2 3  
5 6  
7 8

遇见括号匹配问题多与栈和队联系起来，也许就能解决，此题用栈来做就简单许多。遇见左括号就放入栈中，遇见右括号、那么它一定是和栈顶的左括号是一对匹配的括号，拿出栈顶括号后继续往前走，以此类推。

法一：用的系统提供的栈，这个就比较偷懒，但是很方便啊 ..

 1 #include<iostream>
 2 #include<cstring>
 3 #include<stack>
 4 using namespace std;
 5 const int maxn=1e5+5;
 6 int a[maxn];
 7 char s[maxn];
 8 stack<int> q;
 9 int main()
10 {
11     memset(a,-1,sizeof(a));//全部初始化为-1，便于后面遍历
12     cin>>s;
13     for(int i=0;i<strlen(s);i++)
14     {
15         if(s[i]=='(')
16         {
17             q.push(i+1);//i+1代表当前括号在原括号序列的位置，遇见'('就将此括号的位置放入栈中； 
18         }
19         else if(s[i]==')')//遇见')'就拿出栈顶元素； 
20         {
21             a[q.top()]=i+1;//q.top()表示左括号的位置，i+1表示对应右括号的位置。 
22             q.pop();//删除栈顶元素； 
23         }
24     }
25     for(int i=0;i<strlen(s);i++)
26     {
27         if(a[i]!=-1)
28         {
29             cout<<i<<" "<<a[i]<<endl;
30         }
31     }
32     return 0;
33 }

 

法二：自己写了一个栈，很显然代码量就很多，新手还是建议自己先写一个栈，熟练嘛。。。。

1 #include<stdio.h>

 2 #include<malloc.h>
 3 #include<string.h>
 4 typedef struct   //定义栈
 5 {
 6     int data[100000];
 7     int top;
 8     int bottom;
 9 }stack;
10 stack *StackCreate()  //创建栈
11 {
12     stack *p=(stack*)malloc(sizeof(stack));
13     if(p==NULL)
14     {
15         printf("error");
16         return 0;
17     }
18     p->bottom=p->top=0;
19     return p;
20 }
21 void StackInput(stack *p,int str)  //入栈
22 {
23     p->data[p->top]=str;
24     p->top++;
25 }
26 int StackOutput(stack *p,int str)  //出栈
27 {
28     if(p->top!=p->bottom )
29         str=p->data[p->top-1];
30     p->top--;
31     return str;
32 }
33 void fun(char*a)
34 {
35     int str;
36     int i,b[100000];
37     stack *p;
38     p=StackCreate();
39     for(i=0;i<strlen(a);i++)
40             {
41                 b[i]=-1;
42             }
43             for(i=0;a[i]!='\0';i++)
44             {
45                 if(a[i]=='(')
46                 {
47                     StackInput(p,i+1);
48                 }
49                 if(a[i]==')')
50                 {
51                     str=StackOutput(p,str);
52                     b[str]=i+1;
53                 }
54             }
55             for(i=0;i<strlen(a);i++)
56             {
57                 if(b[i]!=-1)
58                     printf("%d %d\n",i,b[i]);
59             }
60 }
61 int main()
62 {
63     char a[100000];
64     scanf("%s",a);
65     fun(a);
66     return 0;
67 }