程序设计 括号匹配

括号匹配

描述

We give the following inductive definition of a “regular brackets” sequence:

the empty sequence is a regular brackets sequence,
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
if a and b are regular brackets sequences, then ab is a regular brackets sequence.
no other sequence is a regular brackets sequence
For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

输入

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

输出

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

样例输入

((()))
()()()
([]])
)[)(
([][][)
end

样例输出

6
6
4
0
6

#include <stdio.h> #include<stdlib.h> #include<string.h> typedef char StackItem; typedef struct astack *Stack; typedef struct astack { int top,maxtop; StackItem *data; }Astack; void Error(char *s) { printf("%s",s); // exit(1); } Stack StackInit(int size) { Stack S=(Stack)malloc(sizeof astack); S->data=(StackItem*)malloc(size*sizeof(StackItem)); S->maxtop=size; S->top=-1; return S; } int StackEmpty(Stack S) { return S->top<0; } int StackFull(Stack S) { return S->top==S->maxtop; } StackItem StackTop(Stack S) { if(StackEmpty(S))Error("Stack is empty"); else return S->data[S->top]; } void Push(StackItem x,Stack S) { if(StackFull(S))Error("Stack is full"); else S->data[++S->top]=x; } StackItem Pop(Stack S) { if(StackEmpty(S)) Error("Stack is empty"); else return S->data[S->top--]; } void Parenthsis(char *expr) { int i,n; Stack ss=StackInit(100); n=strlen(expr); for(i=1;i<=n;i++) { if(expr[i-1]=='(')Push(i,ss); else if(expr[i-1]==')') { if(StackEmpty(ss)) { printf("the right square at position %d is not matched \n",i); } else printf("%d %d \n",Pop(ss),i); } } while(!StackEmpty(ss)) printf("the left square at position %d is not matched \n",Pop(ss));

} int main(int argc, char* argv[]) { char s[40]; printf("Please input a formula including parenthsis:\n"); scanf("%s",s); Parenthsis(s); scanf("%s",s); return 0; } ///用栈解决