算法分析——括号匹配

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法分析——括号匹配，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2973字，纯文字阅读大概需要5分钟。

内容图文

原文链接：http://www.cnblogs.com/liangyan19910818/archive/2011/09/10/2173342.html

括号匹配问题是指要匹配一个字符串的左，右括号：
括号问题可以用来解决C语言中的“{”和“}”的匹配问题，可以观察到，如果从左至右扫描一个字符串，

那么每个右括号将于最近遇到的那个未匹配的左括号相匹配，在从左至右的扫描工程中把所遇到的左括号

存放到堆栈内，每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该

左括号
以下是完整的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 }

转载于:https://www.cnblogs.com/liangyan19910818/archive/2011/09/10/2173342.html

内容总结

以上是互联网集市为您收集整理的算法分析——括号匹配全部内容，希望文章能够帮你解决算法分析——括号匹配所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---