| 栈的应用 | 您所在的位置：网站首页 › c语言括号怎么用 › 栈的应用 |
栈的应用
|
栈的应用—用栈实现括号匹配(C语言实现)
前言
括号匹配应该很常见了。 例如: ①()[{}] ②{{]]}} ①能匹配成功，②匹配失败。即每一个左括号都能找到与之匹配的右括号，反之亦然。 算法思想 用一个数组存储括号，记为 str[]，例如 str[] = “{[()]}” 依次读取数组的元素，若是遇到左括号，则将其压入栈中；若是遇到右括号，则先判断栈是否空了，如果栈已经空了，匹配失败，如果栈不空，则弹出栈顶元素，看弹出的元素是否能与该右括号匹配，如果不能匹配，说明括号匹配失败。等遍历到数组的末尾时，看栈是否为空，如果空了，匹配成功，如果不空，匹配失败。 全部代码 之前已经写过一篇实现顺序栈的文章C语言实现顺序栈，用链栈也差不多，为图方便，我直接用顺序栈实现了。本次是在之前这篇文章的基础上改了一点结构，然后编写括号匹配的函数实现。 #include #include #include //根据C99标准,C语言使用bool类型需要添加这个头文件 #define MaxSize 10 //顺序栈这里使用静态分配的方式，所以手动规定最大容量 typedef char ElemType;// //-------结构体定义部分------ // typedef struct{ ElemType data[MaxSize]; int top;//指向栈顶元素的指针 }MyStack; //-------结构体定义部分------ // //-------函数声明部分------ // void InitStack(MyStack *S);//栈的初始化 bool Push(MyStack *S,ElemType e);//将元素e压入栈 bool Pop(MyStack *S,ElemType *x);//出栈 bool GetTop(MyStack *S,int *x);//获取当前栈顶元素 bool StackEmpty(MyStack *S);//栈判空 bool BraketCheck(char a[],int length);//括号匹配 //-------函数声明部分------ // int main() { // ElemType arr[] = "[]{[]}"; ElemType arr[] = "[){[]}"; if(BraketCheck(arr,sizeof(arr)-1)) printf("匹配成功！"); else printf("匹配失败！"); return 0; } //栈的初始化 void InitStack(MyStack *S) { //栈的初始化需要把栈顶指针赋值为-1,此时栈中元素个数为0 S->top = -1; } //入栈 bool Push(MyStack *S,ElemType e) { if(S->top == MaxSize -1) //如果栈满 也可以判断 length==MaxSize return false; else S->data[++S->top] = e;//指针先加一再将元素入栈 return true; } //出栈 bool Pop(MyStack *S,ElemType *x) { if(S->top == -1)//栈空 return false; else *x = S->data[S->top--];//先获得元素，指针再执行--操作 return true; } //获取当前栈顶元素 bool GetTop(MyStack *S,int *x) { if(S->top == -1)//如果栈空，则没有栈顶元素 return false; else *x = S->data[S->top];//获得栈顶元素 return true; } //判断栈空 bool StackEmpty(MyStack *S) { return S->top==-1?true:false; } //括号匹配 接收的参数：数组和数组的长度 bool BraketCheck(ElemType str[],int length) { MyStack S;// InitStack(&S);//对栈进行初始化 //读取数组元素 for(int i=0;i Push(&S,str[i]);//左括号则入栈 } else{// if(StackEmpty(&S)) return false;//遇到右括号且当前栈空,匹配失败 char topElem; Pop(&S,&topElem);//栈顶元素出栈 if(str[i]==')'&&topElem!='(') return false; if(str[i]==']'&&topElem!='[') return false; if(str[i]=='}'&&topElem!='{') return false; } } return StackEmpty(&S);//全部匹配完后,栈空则说明匹配成功 } 测试
|
【本文地址】
公司简介
联系我们