Application of stack -- using stack to realize bracket matching (C language implementation)

The application of the stack — Realize bracket matching with stack (C Language implementation )

Preface

​ Bracket matching should be common .

​ for example : ①()[{}] ②{ {]]}}

​ ① Can match success ,② Matching failure . That is, each left parenthesis can find the matching right parenthesis , vice versa .

Algorithmic thought

​ Use an array to store parentheses , Write it down as str[], for example str[] = “{[()]}”

​ Read the elements of the array in turn , If left parenthesis is encountered , Then push it onto the stack ; If you encounter a closing parenthesis , First judge whether the stack is empty , If the stack is empty , Matching failure , If the stack is not empty , Then pop up the top element of the stack , See if the pop-up element can match the closing bracket , If it doesn't match , Description bracket matching failed . When traversing to the end of the array , Check whether the stack is empty , If it is empty , The match is successful , If not empty , Matching failure .

All the code

​ I have written an article about implementing sequence stack before C Language implementation sequence stack , Using chain stack is similar , For the sake of convenience , I implemented it directly with the sequence stack . This time, the structure is changed a little on the basis of the previous article , Then write the function implementation of bracket matching .

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> // according to C99 standard ,C Language use bool Type needs to add this header file 
#define MaxSize 10 // The sequence stack uses the static allocation method here , So manually specify the maximum capacity  

typedef char ElemType;//
 
//------- Structure definition part ------ //
typedef struct{
    
	ElemType data[MaxSize];
	int top;// Pointer to the top element of the stack  
}MyStack;
//------- Structure definition part ------ //
 
//------- Function declaration part ------ //
void InitStack(MyStack *S);// Initialization of stack  
bool Push(MyStack *S,ElemType e);// Put the element e Push to stack  
bool Pop(MyStack *S,ElemType *x);// Out of the stack 
bool GetTop(MyStack *S,int *x);// Get the current stack top element  
bool StackEmpty(MyStack *S);// Stack empty  
bool BraketCheck(char a[],int length);// Parentheses matching  
//------- Function declaration part ------ //


int main()
{
    
// ElemType arr[] = "[]{[]}";
	ElemType arr[] = "[){[]}";
	if(BraketCheck(arr,sizeof(arr)-1))
		printf(" The match is successful ！");
	else
		printf(" Matching failure ！");
	return 0;
}

// Initialization of stack  
void InitStack(MyStack *S)
{
    
	// To initialize the stack, you need to assign the stack top pointer to -1, At this point, the number of elements in the stack is 0 
	S->top = -1;
} 

// Push  
bool Push(MyStack *S,ElemType e)
{
    
	if(S->top == MaxSize -1) // If the stack is full   You can also judge  length==MaxSize 
		return false;
	else 
		S->data[++S->top] = e;// The pointer first adds and then puts the element on the stack  
	return true;
} 

// Out of the stack 
bool Pop(MyStack *S,ElemType *x)
{
    
	 
	if(S->top == -1)// The stack is empty  
		return false;
	else
		*x = S->data[S->top--];// Get the element first , Pointer re execution -- operation 
	return true;
} 

// Get the current stack top element 
bool GetTop(MyStack *S,int *x)
{
    
	if(S->top == -1)// If the stack is empty , Then there is no stack top element  
		return false;
	else
		*x = S->data[S->top];// Get the stack top element  
	return true;
} 

// Judge stack empty  
bool StackEmpty(MyStack *S)
{
    
	return S->top==-1?true:false; 
}

// Parentheses matching   Parameters received ： Array and length of array  
bool BraketCheck(ElemType str[],int length)
{
    
	MyStack S;//
	InitStack(&S);// Initialize the stack 
	
	// Read array elements 
	for(int i=0;i<length;i++)
	{
    
		if(str[i]=='('||str[i]=='['||str[i]=='{'){
    
			Push(&S,str[i]);// The left bracket is stacked  
		}
		else{
    // 
			if(StackEmpty(&S))
				return false;// Encountered a closing parenthesis and the current stack is empty , Matching failure  
			char topElem;
			Pop(&S,&topElem);// Stack top element out of stack  
			if(str[i]==')'&&topElem!='(')
				return false;
			if(str[i]==']'&&topElem!='[')
				return false;
			if(str[i]=='}'&&topElem!='{')
				return false;
		} 
	} 
	return StackEmpty(&S);// After all matching , If the stack is empty, the matching is successful  
}

test