This is the 18th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

1. Compile and run

  • demand

Write a program to determine whether a sequence of parentheses containing “(” and”) “matches. If a Match is displayed, Match is displayed. If not, it calculates the minimum number of parentheses needed to make the sequence a match (only parentheses are allowed at the beginning and end of the sequence) and outputs a valid match sequence after adding the minimum parentheses.

  • Input format

The input is a string containing no more than 100,000 parentheses.

  • The output format

If the input parenthesis sequence matches, Match is printed. If not, the output is divided into two lines. The first line is an integer representing the minimum number of parentheses required to make the sequence a match, and the second line is a string representing the legal matching sequence after the minimum parentheses were added.

2. The sample

  • Input Example 1:

(())()

  • Example 1:

Match

  • Input Example 2:

) (

  • Example 2:

2

() ()

  • Input Example 3:

4

((())) (())

3. The code block

  • Sequential stacks store structure definitions
typedef struct{
	// The top pointer points to the top of the stack
	SElemType *top;
	// Base points to the bottom of the stack
	SElemType *base;
	// The sequential stack size
	int stackSize;
}SqStack;
Copy the code
  • The sequential stack S is initialized
Status InitStack(SqStack &S){
	// Dynamically allocate a space of type SElemType MAXSIZE
	// Assign the address to the bottom pointer of the sequential stack S
	S.base = new SElemType[MAXSIZE];
	// If the bottom pointer of the sequential stack (s.case) is empty and there is no address, then the allocation is not successful
	if(! S.base)return ERROR;
	// Empty sequential stack, so top pointer = bottom pointer
	S.top=S.base;
	// Empty sequence stack, by MAXSIZE space can be stored
	S.stackSize = MAXSIZE;
	return OK;
}
Copy the code
  • Push, push E into the sequential stack S
Status push(SqStack &S,SElemType e){
	// Check whether the stack is full
	if(S.top-S.base==S.stackSize) return ERROR;
	// store e to s.top and move the pointer to top++ up
	*S.top++=e;
	return OK;
}
Copy the code
  • Out of the stack, give the top element to E
Status pop(SqStack &S,SElemType &e){
	// Check whether there are elements in the stack
	if(S.top==S.base) return ERROR;
	// Move the top pointer down and assign the top element to e
	e=*--S.top;
	return OK; 
} 
Copy the code
  • Take the top element on the stack and assign it to e
Status GetTop(SqStack S,SElemType &e){
	// Check whether there are elements in the stack
	if(S.top==S.base) return ERROR; 
	// Returns the value of the top element of the stack, with the top pointer unchanged
	e=*(S.top- 1); 
	return OK; 
}
Copy the code
  • Check whether the stack is empty
int stackEmpty(SqStack S){
	// null returns 1
	if(S.top==S.base) 
		return 1;
	// non-null returns 0
	return 0; 	
} 
Copy the code
  • Parentheses matching
	int flag =1; 
	char e;
	for(int i=0; i<str.length(a); i++){switch(str[i]){	
			//1. Open parenthesis to stack
			case '(':
				push(S,str[i]);	
				break;
			// 2. Close bracket
			case ') ':
				{
					// If the stack is not empty and the top of the stack is an open bracket of the same type, then the stack is removed, indicating a match
					GetTop(S,e);									
					if(!stackEmpty(S)	&&	e=='(') 
						pop(S,e);
					// If the stack is empty, there are too many close parentheses, which do not match, and the left parentheses need to be supplemented
					else{
						left++;
						flag=0; }}break; }}Copy the code
  • Prints Match or the parentheses that need to be filled
if(	stackEmpty(S)	&&	flag==1	) {
		cout<<"Match"<<endl;
	// If the stack is empty, there are still left parentheses in the stack, indicating that there are too many left parentheses
	}else{
		if(!stackEmpty(S))
			right =right+S.top-S.base;		
		cout<<left+right<<endl;	
		for(int i=0; i<left; i++) cout<<'(';
		cout<<str;
		for(int i=0; i<right; i++) cout<<') ';
	}			
Copy the code

4. The source code

#include<iostream>
using namespace std;
#define ERROR 0
#define OK 1
#define MAXSIZE 100001
typedef char SElemType;
typedef int Status;

typedef struct{
	// The top pointer points to the top of the stack
	SElemType *top;
	// Base points to the bottom of the stack
	SElemType *base;
	// The sequential stack size
	int stackSize;
}SqStack;

// The sequential stack S is initialized
Status InitStack(SqStack &S){
	// Dynamically allocate a space of type SElemType MAXSIZE
	// Assign the address to the bottom pointer of the sequential stack S
	S.base = new SElemType[MAXSIZE];
	// If the bottom pointer of the sequential stack (s.case) is empty and there is no address, then the allocation is not successful
	if(! S.base)return ERROR;
	// Empty sequential stack, so top pointer = bottom pointer
	S.top=S.base;
	// Empty sequence stack, by MAXSIZE space can be stored
	S.stackSize = MAXSIZE;
	return OK;
}

// push e into the sequential stack S
Status push(SqStack &S,SElemType e){
	// Check whether the stack is full
	if(S.top-S.base==S.stackSize) return ERROR;
	// store e to s.top and move the pointer to top++ up
	*S.top++=e;
	return OK;
}

// Go off the stack and give e the top element
Status pop(SqStack &S,SElemType &e){
	// Check whether there are elements in the stack
	if(S.top==S.base) return ERROR;
	// Move the top pointer down and assign the top element to e
	e=*--S.top;
	return OK; 
} 

// Take the top element of the stack and assign it to e
Status GetTop(SqStack S,SElemType &e){
	// Check whether there are elements in the stack
	if(S.top==S.base) return ERROR; 
	// Returns the value of the top element of the stack, with the top pointer unchanged
	e=*(S.top- 1); 
	return OK; 
} 

// Check whether the stack is empty
int stackEmpty(SqStack S){
	// null returns 1
	if(S.top==S.base) 
		return 1;
	// non-null returns 0
	return 0; 	
} 

// eliminate a group of parentheses using the stack advanced after exit
int match(SqStack &S,string str,int &count){}int main(a){
	// create stack S
	SqStack S;
	// Record the left parenthesis to be filled
	int left=0;
	// Record the closing parenthesis to be filled
	int right=0;
	// initialize stack S
	InitStack(S);
	string str;	
	cin>>str;
	// output match or not match according to 1,0 returned by match
	int flag =1; 
	char e;
	for(int i=0; i<str.length(a); i++){switch(str[i]){	
			//1. Open parenthesis to stack
			case '(':
				push(S,str[i]);	
				break;
			// 2. Close bracket
			case ') ':
				{
					// If the stack is not empty and the top of the stack is an open bracket of the same type, then the stack is removed, indicating a match
					GetTop(S,e);									
					if(!stackEmpty(S)	&&	e=='(') 
						pop(S,e);
					// If the stack is empty, there are too many close parentheses, which do not match, and the left parentheses need to be supplemented
					else{
						left++;
						flag=0; }}break; }}// If the stack is empty and flag==1, Match is displayed
	if(	stackEmpty(S)	&&	flag==1	) {
		cout<<"Match"<<endl;
	// If the stack is empty, there are still left parentheses in the stack, indicating that there are too many left parentheses
	}else{
		// if the stack is not empty, all parentheses in the stack are '(').
		if(!stackEmpty(S))
			right =right+S.top-S.base;	
		// Prints the number of braces needed
		cout<<left+right<<endl;	
		for(int i=0; i<left; i++) cout<<'(';
		cout<<str;
		for(int i=0; i<right; i++) cout<<') ';
	}														
	return 0;
} 
Copy the code