那么每个右括号将于最近遇到的那个未匹配的左括号相匹配，在从左至右的扫描工程中把所遇到的左括号
存放到堆栈内，每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该
左括号 以下是完整的C程序，该算法的时间复杂性为O(n),其中n为输入串的长度：
1 #include "stdio.h" 2 #include "string.h" 3 #include "stdlib.h" 4 5 6 #define StackSize 100 //假定预分配的栈空间最多为100个元素 7 #define MaxLength 100 //最大的字符串长度 8 9 typedef int DataType; //假定栈元素的数据类型为整数 10 typedef struct 11 { 12 DataType data[StackSize]; 13 int top; 14 }SeqStack; 15 16 void Initial(SeqStack *S); 17 int IsEmpty(SeqStack *S); 18 int IsFull(SeqStack *S); 19 void Push(SeqStack *S, DataType x); 20 DataType Pop(SeqStack *S); 21 DataType Top(SeqStack *S); 22 void PrintMatchedPairs(char *expr); 23 24 25 void main(void) 26 { 27 char expr[MaxLength]; 28 printf("请输入符号个数小于%d的表达式：\n",MaxLength); 29 30 gets(expr); 31 32 printf("括号对是：\n"); 33 34 PrintMatchedPairs(expr); 35 36 return; 37 } 38 39 //置栈空 40 void Initial(SeqStack *S) 41 { 42 S -> top = -1; 43 } 44 45 //判断栈是否空 46 int IsEmpty(SeqStack *S) 47 { 48 return S -> top == -1; 49 } 50 51 //判断栈是否满 52 int IsFull(SeqStack *S) 53 { 54 return S -> top == StackSize -1; 55 } 56 57 //进栈 58 void Push(SeqStack *S, DataType x) 59 { 60 if(IsFull(S)) 61 { 62 printf("栈上溢!"); 63 exit(1); 64 } 65 66 S -> data[++ S -> top] = x; 67 68 return; 69 } 70 71 //出栈 72 DataType Pop(SeqStack *S) 73 { 74 if(IsEmpty(S)) 75 { 76 printf("栈为空！"); 77 return -1; 78 } 79 80 return S -> data[S -> top--]; //栈顶指针加1后将x入栈 81 } 82 83 //取栈顶元素 84 DataType Top(SeqStack *S) 85 { 86 if(IsEmpty(S)) 87 { 88 printf("栈为空！"); 89 exit(1); 90 } 91 92 return S -> data[S -> top]; 93 } 94 95 //括号匹配 96 void PrintMatchedPairs(char *expr) 97 { 98 SeqStack S; 99 int i , j , length = strlen(expr); 100 101 Initial(&S); 102 103 for(i = 1 ; i <= length ; i++) 104 { 105 if(expr[i - 1] == '(') 106 { 107 Push(&S,i); 108 } 109 else if(expr[i - 1] == ')') 110 { 111 j = Pop(&S); 112 if(j == -1) 113 { 114 printf("没有对应第%d个右括号的左括号\n", i); 115 } 116 else 117 { 118 printf("%d %d\n",i,j); 119 } 120 } 121 } 122 123 while(!IsEmpty(&S)) 124 { 125 j = Pop(&S); 126 printf("没有对应第%d个左括号的右括号\n", j); 127 } 128 }
最新评论