poj 1068 parencondings

题目描述：

定义 S 为一个合法的括号字符串。S 可以用以下两种方式编码：
1. 用一个整数数组 P 来表示，其中元素 p[i] 是 S 中每个 ')' 前的 '(' 的个数；
2. 用一个整数数组 W 来表示，表示 S 中的第 i 个 ')' 与往前数的第 w[i] 个 '(' 能配对。
举个例子：

	S  (((()()())))
	P      4 5 6666
	W      1 1 1456

你的任务是将 P 数组转换为等价的 W 数组。

输入：

第一行一个正整数 t∈[1,10]，表示输入数据的组数。
每组数据包含两行输入，用来表示采用第 1 种编码方式对 S 进行编码得到的 P 数组：
第一行为一个正整数 n∈[1,20] 表示 P 数组数字的个数；
第二行为 P 数组的内容。

输出：

每组测试数据输出一行，表示转换后W的内容。

样例输入：

2
6
4 5 6 6 6 6
9 
4 6 6 6 6 8 9 9 9

样例输出：

1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

解题思路：

首先定义三个数组，p和w数组用来存输入和输出，数组k用来存每个括号，其中左括号用0表示，右括号用1表示。然后把数据都读入进去，随后定义一个栈q，我们把左括号的位置依次存入栈中，当碰到右括号时，栈首元素就是离当前右括号最近的一个左括号，最后通过左括号和右括号的下标计算出计算当前右括号往前数所对应第几个左括号 

代码如下：

#include<iostream>
#include <cstdio>
#include <stack>
using namespace std;
int p[30];//存p 
int w[30];//存w 
int k[30];//存括号 
int main()
{
	int n,t;
	cin >> t;
	while(t--)
	{
		cin >> n;
		for(int i=1;i<=n;i++)
		{
			cin >> p[i];
		}
		p[0]=0;
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			int len=p[i]-p[i-1];
			for(int j=1;j<=len;j++)
			{
				k[++cnt]=0;//左括号用0表示 
			}
			k[++cnt]=1;//右括号用1表示 
		}
		stack<int>q;
		int res=0;
		for(int i=1;i<=cnt;i++)
		{
			if(!k[i])
			{
				q.push(i);//左括号入栈 
			}
			else
			{
				w[++res]=(i-q.top()+1)/2;
				//计算当前右括号往前数所对应左括号的下标 
				//除以2是因为存在右括号 
				q.pop();
			}
		}
		for(int i=1;i<=res;i++)
		{
			cout << w[i]<<" ";
		}
		cout <<endl;
	}
	return 0;
 } 

大数据201 ly