栈的经典应用之一：括号匹配检查

2019-11-06 06:09:06

字体：大中小

来源：转载

供稿：网友

功能：主要对字符串中的括号（包括“{}”、“[]”、“（）”）进行匹配；匹配成功时，打印匹配成功，否则打印匹配失败。

算法思路：从字符串的第一个字符开始扫描，若是普通字符则忽略，反之若是左符号则入栈操作；当遇见右符号的时候则从栈中弹出栈顶元素，并进行匹配；

匹配结束时：成功：所有字符扫描完毕，并且栈为空；失败：匹配失败或所有字符扫描完毕但是栈非空；

附：调试过程中，有些小问题，有时间了再修改；

.h文件#PRagma once#include<stdio.h>#include <stdlib.h>#include <string.h>#define true 1#define false 0#define SIZE 100typedef char ElemType;typedef struct stack { ElemType *base; int top; int stacksize; }Stack;//1.建立一个空栈void Init(Stack *s);//2.入栈int Push(Stack *s,ElemType d);//3.弹栈int Pop(Stack *s,ElemType *mPtr);//4.获取栈顶元素int GetTop(Stack *s,ElemType *e);//5.判断栈非空int Empty(Stack *s);//6.打印栈元素void List(Stack *s);//7.匹配括号int MyFunc(char *mString);.c文件#include "Stack.h"//1.建立一个空栈void Init(Stack *s) { s->base=(ElemType *)malloc (sizeof(ElemType)*SIZE); s->top=0; s->stacksize=SIZE; return ; }//2.入栈int Push(Stack *s,ElemType d) { //栈满 if (s->top>=s->stacksize) { s->base=(ElemType *)realloc (s->base,sizeof(s->stacksize+1)*sizeof(ElemType)); //判断栈内存空间是否分配成功 if (s->base==NULL) return false; s->stacksize++; } s->base[s->top++]=d; return true; }//3.弹栈int Pop(Stack *s,ElemType *mPtr) { if (s->top==0) return false; else { *mPtr=s->base[s->top--]; return true; } }//4.获取栈顶元素int GetTop(Stack *s,ElemType *e) { if (s->top==0) return false; *e=s->base[--s->top]; return true; }//5.判断栈非空int Empty(Stack *s) { if (s->top==0) return true; return false; }//6.打印栈元素void List(Stack *s) { if (s->top==0) return; while (s->top-1>=0) { printf ("data:%c/n",s->base[s->top-1]); s->top--; } }//7.匹配括号int MyFunc(char *mString) //mString->[26*(12+8)/(45-29)] { int i=0,flag=1; Stack s1; ElemType e; Init(&s1); while (mString[i]!='/0') { switch (mString[i]) { case '(':Push (&s1,'(');break; case '[':Push (&s1,'[');break; case '{':Push (&s1,'{');break; case ')':GetTop (&s1,&e); if (e=='(') Pop (&s1,&e); else flag=0; break; case ']':GetTop (&s1,&e); if (e=='[') Pop (&s1,&e); else flag=0; break; case '}':GetTop (&s1,&e); if (e=='{') Pop (&s1,&e); else flag=0; break; } ++i; } if (Empty (&s1)&&flag) return true; else return false; }test.c#include "Stack.h"int main(void) { char str[]="[20*(16+4)/(15-6)]"; if (MyFunc (str)) printf ("匹配成功！/n"); else printf ("匹配失败！/n"); system ("pause"); return 0; }

上一篇：链栈与链表间的关系

下一篇：【LeetCode】50. Pow(x, n)

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注