数据结构【完整代码】之（C语言实现【栈与队列】实现括号匹配([{ ）

本文包含两个文件的代码和两张测试效果图：

• StackAndQueue.h文件： 用于存储信息：存放函数、结构体、栈的函数实现、变量名等
• blockMatch.cpp文件： 用于测试
• 效果图：（位于最上方）

测试图：

StackAndQueue.h文件:

#include<stdio.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status; 

//---------------栈
typedef char SElemType;
typedef struct{
  SElemType data[MAXSIZE];
  int top; //用于栈顶指针 
}SqStack;

Status InitStack(SqStack *S){
  for(int i = 0; i < MAXSIZE; i++){
    S->data[i] = ' '; //用0初始化 
  }
  S->top = -1;
}

Status StackSize(SqStack S){
  return (S.top+1);
}

Status Push(SqStack *S, SElemType e){ //------进栈 
  if(S->top == MAXSIZE - 1){ //栈满 
    return ERROR;
  }
  S->top++; //栈顶指针增加一 
  S->data[S->top] = e; //将新插入元素赋值给栈顶空间
  return OK; 
}

Status Pop(SqStack *S, SElemType *e){
  if(S->top == -1){ //栈空 
    return ERROR;
  }
  *e = S->data[S->top];
  S->top--;
  return OK;
}

//-------------队列
typedef char QElemType;
typedef struct{
  QElemType data[MAXSIZE];
  int front;
  int rear;
}SqQueue;
 
Status InitQueue(SqQueue *Q){
  Q->front = 0;
  Q->rear = 0;
  return OK;
}

int QueueLength(SqQueue Q){
  return (Q.rear - Q.front +MAXSIZE) % MAXSIZE;
}

Status EnQueue(SqQueue *Q, QElemType e){ //入队列 
  if((Q->rear + 1) % MAXSIZE == Q->front){ //队列满
    return ERROR; 
  }
  Q->data[Q->rear] = e;
  Q->rear = (Q->rear + 1) % MAXSIZE;
  return OK;
}

Status DeQueue(SqQueue *Q, QElemType *e){ //出队列 
  if(Q->front == Q->rear){
    return ERROR;
  }
  *e = Q->data[Q->front];
  Q->front = (Q->front + 1) % MAXSIZE;
  return OK;
}

blockMatch.cpp文件：

#include "StackAndQueue.h"

void match(char* input){
  SqStack S;
  InitStack(&S);
  int ok = 1;
  char e;
  int len = strlen(input);
  for(int i = 0; i < len; i++){
    if(input[i] == '(' || input[i] == '[' || input[i] == '{'){
      Push(&S, input[i]);
    }
    else if(input[i] == ')'){
      Pop(&S, &e);
      if(e == '('){
        printf("已匹配一对()\n");
      }
      else{
        ok = 0;
        printf(") 匹配失败\n");
        Push(&S, e);
      }
    }
    else if(input[i] == ']'){
      Pop(&S, &e);
      if(e == '['){
        printf("已匹配一对[]\n");
      }
      else{
        ok = 0;
        printf("] 匹配失败\n");
        Push(&S, e);
      }
    }
    else if(input[i] == '}'){
      Pop(&S, &e);
      if(e == '{'){
        printf("已匹配一对{}\n");
      }
      else{
        ok = 0;
        printf("} 匹配失败\n");
        Push(&S, e);
      }
    }
    e = ' ';
  }
  int flag = StackSize(S);
  if(flag != 0){
    ok = 0;
    for(int i = 0; i < flag; i++){
      Pop(&S, &e);
      printf("%c 匹配失败\n", e);
    }
  }
  if(ok == 1){
    printf("------------最终匹配成功！------------"); 
  }
  else if(ok == 0){
    printf("------------最终匹配失败！------------");
  } 
}

int main(){
  char input[101];
  gets(input);
  match(input); 
}