首页 > 代码库 > POJ1068-Parencodings

POJ1068-Parencodings

2024-07-23 14:30:33   219人阅读

　　这个题主要考的对栈的操作，题目的意思是：有一组由小括号组成的队列S，P(i)表示当前队列中第i个右括号前面的左括号的个数，W(i)表示左括号和右括号配对成功的里面的右括号的个数（包括当前的左右括号）。要求是：输入P的值，计算输出W的值。

　　我的思路是：根据P的输入值计算出当前的队列S，左括号用0表示，右括号用1表示，然后用栈计算成对的括号的位置start和end，最后计算start和end之间的右括号的数量（包括end）

 

#include "stdio.h"#include "math.h"#include "string.h"#include "stdlib.h"int main(int argc, char const *argv[]){	int _i, _j, _k, start, n, m, t, sum, data[25], num[225];	int stack[225], top;	scanf("%d", &t);	while(t--)	{		scanf("%d", &n);		data[0]=0, top=-1;		for(_i=1; _i<=n; _i++){			scanf("%d", &data[_i]);		}		_i=1, _j=0, start=0;		while(_i<=n){			_k = data[_i]-data[_i-1];			for(_j=start; _j<start+_k; _j++){				num[_j] = 0;			}			num[_j] = 1;			start += _k+1;			_i++;		}		for(_i=0; _i<start; _i++){			if(num[_i]==0){				top++;				stack[top] = _i;			}else if(num[_i]==1){				// printf("%d\n", stack[top]);				sum = 0;				for(_j=stack[top]; _j<=_i; _j++){					sum += num[_j];				}				printf("%d ", sum);				top--;			}		}		printf("\n");	}	return 0;}

POJ1068-Parencodings


联系
我们