Bracket matching test

1、 Algorithm description

Define in the bracket matching algorithm int flag = 1 Variable to mark whether the matching result is successful or failed ！

 Using data structure stack , Scan strings from left to right ：

     If encountering the left parenthesis, put it on the stack ;

     If you encounter a closing parenthesis ：
  
         If the stack is not empty , Use Pop(s,topElem) The operation gets the top element , Match with the current closing parenthesis . If the current right parenthesis does not match the top element , So modify flag The value of is 0, Matching failure , And print an error message ！
     
         If the stack is empty , Then it means that all the currently scanned right parentheses cannot match without the left parenthesis , modify flag by 0, Matching failure , And print an error message ！  
                                   
 After scanning the whole string from left to right ：

     If the stack is empty and  flag The value of is 1, That is, the matching is successful ！（ Because if not flag, that (] This is also a successful match ！ So the logic of the algorithm will produce errors ！）
   
     Otherwise, the matching fails in other cases ！

2、 The specific code is as follows

// Bracket matching algorithm 

#include<stdio.h>
#include<stdlib.h> //malloc Function header file  
#define MaxSize 20
#include<iostream>
using namespace std;
#define OK 1;
#define ERROR 0; 

// Structure definition  
typedef struct{
    
	char *data;  // The base address of the storage space  
	int top;     // The pointer at the top of the stack records the subscript  
}SqStack;

// Initialization stack  
void InitStack(SqStack &s){
    
	s.data = (char *) malloc(sizeof(char)*MaxSize); 
	s.top = -1; 
} 

// Judge whether the stack is empty 
int SqStackIsEmpty(SqStack s) {
    
	if (s.top == -1)
         return OK; // The stack is empty 
    return ERROR;  // Stack is not empty.  
}

// Into the stack, 
void Push(SqStack &s,char c){
    
	if(s.top == MaxSize - 1)   // Stack full  
	    printf(" Stack full ！\n");
	s.top = s.top + 1;
	s.data[s.top] = c;
} 

// The stack, 
void Pop(SqStack &s, char &c){
    
	if(SqStackIsEmpty(s))
	    printf(" The stack is empty ！\n");
	c = s.data[s.top];
	s.top = s.top - 1;
} 

// Parentheses match functions 
void bracketCheck(char str[], int length){
    
	SqStack s;
	InitStack(s); 
	int flag = 1; // Whether the flags match successfully  
    for(int i = 0; i<length;i++){
    
    	if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
    
    		Push(s,str[i]); // Scan from left to right , Run the stack operation when you encounter the left parenthesis  
		}
    	else if(str[i] == ')' || str[i] == ']' || str[i] == '}'){
     // When you encounter the right parenthesis, judge the symbol in the stack  
    		    if(!SqStackIsEmpty(s))
			    {
    
			    	char topElem;
			        Pop(s,topElem);
					if(str[i] == ')' && topElem != '('){
    
						flag = 0; 
						printf(" Matching failure , The first  %d  Right parenthesis  %c  And stack top symbol  %c  Mismatch \n",i+1,str[i],topElem); 
					}  
					if(str[i] == ']' && topElem != '['){
    
						flag = 0; 
						printf(" Matching failure , The first  %d  Right parenthesis  %c  And stack top symbol  %c  Mismatch \n",i+1,str[i],topElem);
					}
					if(str[i] == '}' && topElem != '{'){
    
						flag = 0; 
						printf(" Matching failure , The first  %d  Right parenthesis  %c  And stack top symbol  %c  Mismatch \n",i+1,str[i],topElem);
					}
				}
				else  {
    
					printf("\n Matching failure , The first  %d  One is the single right bracket  %c \n",i+1,str[i]); // The stack is empty , There is a single right parenthesis 
					flag = 0;
				}
		}
	}
	if(SqStackIsEmpty(s) && flag == 1){
    
		printf("\n The match is successful !!!!!!!\n");
	} 
	else printf("\n Matching failure !!!!!!!\n");
}

// The main function  
int main(){
    
	char str[MaxSize] = "\0"; // Character array initialization \0
	//puts(str);
	printf(" Please enter the expression you want to judge :\t");
	gets(str);
	printf("\n");
    bracketCheck(str,MaxSize);	
} 

3、 Core code

// Parentheses match functions 
void bracketCheck(char str[], int length){
    
	SqStack s;
	InitStack(s); 
	int flag = 1; // Whether the flags match successfully  
    for(int i = 0; i<length;i++){
    
    	if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
    
    		Push(s,str[i]); // Scan from left to right , Run the stack operation when you encounter the left parenthesis  
		}
    	else if(str[i] == ')' || str[i] == ']' || str[i] == '}'){
     // When you encounter the right parenthesis, judge the symbol in the stack  
    		    if(!SqStackIsEmpty(s))
			    {
    
			    	char topElem;
			        Pop(s,topElem);
					if(str[i] == ')' && topElem != '('){
    
						flag = 0; 
						printf(" Matching failure , The first  %d  Right parenthesis  %c  And stack top symbol  %c  Mismatch \n",i+1,str[i],topElem); 
					}  
					if(str[i] == ']' && topElem != '['){
    
						flag = 0; 
						printf(" Matching failure , The first  %d  Right parenthesis  %c  And stack top symbol  %c  Mismatch \n",i+1,str[i],topElem);
					}
					if(str[i] == '}' && topElem != '{'){
    
						flag = 0; 
						printf(" Matching failure , The first  %d  Right parenthesis  %c  And stack top symbol  %c  Mismatch \n",i+1,str[i],topElem);
					}
				}
				else  {
    
					printf("\n Matching failure , The first  %d  One is the single right bracket  %c \n",i+1,str[i]); // The stack is empty , There is a single right parenthesis 
					flag = 0;
				}
		}
	}
	if(SqStackIsEmpty(s) && flag == 1){
    
		printf("\n The match is successful !!!!!!!\n");
	} 
	else printf("\n Matching failure !!!!!!!\n");
}

If not used c Language , The above stack 、 Various operations such as UN stacking can be used c++、java Directly operate on the customized stack , Simplify the code ！

4、 Code demonstration