（棧的應用）括号比對

題目來源：PIPIOJ 1036 括号比對

【問題描述】

PIPI給你一個合法的括号序列，希望跟你按左括号下标遞增順序給出每對括号在序列中的下标。（下标從1開始）

【輸入輸出】

**1.輸入：**    
  多組資料，請處理到EOF。
  對于每組資料，第一行包括一個隻包含'(',')'的字元串，保證輸入的括号比對序列合法，長度不超過100000
**2.輸出：**
  按左括号下标遞增順序給出每對括号在序列中的下标。
           

【樣例】

樣例輸入：(())()()

樣例輸出： 
1 4  
2 3  
5 6  
7 8 
           

【算法思路】

本題需要用到棧的相關知識：
  可以先定義一個棧類型Stack，并設定一個棧s，假設輸入的括号字元串名為
  ls[maxSize]， 記錄右括号的下表數組為index[maxSize]，則周遊ls字元串，
  遇到左括号下标入棧，遇到右括号下标出棧，并且出棧時，記錄左括号的下
  标為j，則與之相比對的右下邊表示為index[j]。
           

【算法描述】

#include<iostream>
#include<cstring>
using namespace std;

/*定義棧*/
#define maxSize 100100
typedef struct Stack
{
	int data[maxSize];
	int top = -1;
}Stack; 

int main()
{
	Stack s;	//聲明一個棧
	char ls[maxSize];	//一個合法的括号序列
	int index[maxSize];	//存放右括号的下标 
	
	while (scanf("%s",&ls)!=EOF)
	{
		int l = strlen (ls);
		for (int i=0; i < l; ++i)
		{
			if (ls[i] == '(')	
				s.data[++s.top] = i+1;	//遇到左括号，下标入棧
			else
			{
				int j = s.data[s.top--];	//遇到右括号，下标出棧 ；j為比對左括号的下标
				index[j] = i+1;	//比對右括号下标	
			} 
		}
		
		/*輸出括号在序列中的下标*/
		for (int i = 0; i < l; ++i)
		{
			if (index[i] !=0)	//假如右括号不存在，則不輸出 
            	cout << i << " " << index[i] << endl;
            index[i] = 0; 	
		}
	} 
	return 0; 
}