c语言实现括号匹配算法
#include <stdio.h>
#define MaxSize 50
#define true 1
#define false 0
typedef int bool;
typedef int Elemtype;
//栈的数据结构
typedef struct {
Elemtype data[MaxSize];
int top;
}SqStack;
//初始化
void InitStack(SqStack *S){
S->top=-1;
}
//判空
bool StackEmpty(SqStack S){
if(S.top==-1){
return true;
}else{
return false;
}
}
//进栈
bool Push(SqStack *S,Elemtype x){
if(S->top==MaxSize-1){
return false;//栈满
}
S->top++;//先加1，再进栈
S->data[S->top]=x;
return true;
}
//出栈
bool Pop(SqStack *S,Elemtype *x){
if(S->top==-1){
return false;//栈空，不能进行出栈操作
}
(*x)=S->data[S->top];
S->top--;//先出栈，再减1
return true;
}
//求栈顶元素
bool GetTop(SqStack S,Elemtype *x){
if(S.top==-1){
return false;
}
(*x)=S.data[S.top--];
return true;
}
int left_or_right(char ch){
switch (ch) {
case '(': return 1;
case '[': return 3;
case '{': return 5;
case ')': return 2;
case ']': return 4;
case '}': return 6;
}
return 0;
}
//匹配算法
bool Match(SqStack *S,char str[MaxSize]){
if(strlen(str)%2){
//串长为奇数，直接匹配失败
printf("串长为奇数，直接匹配失败\n");
return false;
}
int i=0;
int state=0;
while(str[i]){
state=left_or_right(str[i]);
if(state%2){
//对2求余不为0则为奇数，则为左边括号,进栈
Push(S, str[i]);
i++;
}else {//为右括号，读取栈顶元素，“如果比当前序号小1”（switch的特殊设计），则匹配
int x;GetTop(*S, &x);
int y=left_or_right((char)x);
if((y+1)==state){
//匹配,出栈
int t;
Pop(S, &t);//t为临时变量
i++;
continue;
}else{
//不匹配,该串匹配失败
return false;
}
}
}
if(StackEmpty(*S)){
//栈空则匹配正确
return true;
}
return false;
}
int main(int argc, const char * argv[]) {
SqStack S;
InitStack(&S);
char str1[MaxSize] = "[(){}{()}]";
printf("待匹配的括号为: %s", str1);
printf("\t长度为%d\n",strlen(str1));
if(Match(&S,str1)){
printf("匹配成功！！！\n");
}else{
printf("匹配失败！！！\n");
}
return 0;
}
在判断左右括号是否是一对，我用了巧妙的switch设计使得既可以方便判断是左边还是右边，又可以判断是否左右匹配。
