The C language implements the parenthesis matching method
- 2020-09-28 09:02:14
- OfStack
1 requires
The program checks that the parentheses of the string are paired and cannot be crossed.
Input:
A string containing "()", "{}", "[]", and "#"
Output:
Success: means the parentheses appear in pairs and are nested correctly
Failure: Incorrect use of parenthesis characters.
2 analysis
You can solve this problem with 1 stack, the top character of the open bracket must match the close parenthesis character of the first push.
Stack description: A stack is a special kind of linear table, can only operate on the 1 side of the linear table.
Features of stacks: Last in, First out (LIFO)
Since you are learning about data structures, the definition and operation of the stack are self-written to consolidate the concept
3 code
#include<stdio.h>
#include <malloc.h>
#define STACK_INT_SIZE 100
#define STACKINCREMENT 10
#define bool int // The custom bool variable
#define SElemType char
typedef struct {
SElemType *base; // The stack base address
SElemType *top; // Address of the stack
int stacksize;
} SqStack;
//------ The algorithm description of the basic operation ------
// build 1 An empty stack
bool InitStack(SqStack *S) {
S->base = (SElemType *) malloc(STACK_INT_SIZE * sizeof(SElemType)); // Open up new space
if (!S->base) return 0; // Open failed return 0
S->top = S->base;
S->stacksize = STACK_INT_SIZE;
return 1;
}
// If the stack is not empty, returns the top element and returns true Otherwise returns false
bool GetTop(SqStack S) {
if (S.top == S.base) return 0;
return *(S.top - 1);
}
// Insert elements For the new top of the stack element
bool Push(SqStack *S, SElemType e) {
if (S->top - S->base >= S->stacksize) // If the stack is full Need more space
{
S->base = (SElemType *) realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
if (!S->base) return 0;
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*(S->top++) = e;
return 1;
}
// If the stack is not empty, delete the top element of the stack e Returns its value. Returns true . Otherwise returns false
bool Pop(SqStack *S, SElemType *e) {
if (S->top == S->base) return 0;
*e = *(--S->top);
return 1;
}
// Check the position of the parenthesis characters in the character set
int CheckChar(char c, char OP[]) {
int i;
for (i = 0; i < 3; i++)
if (c == OP[i])return i;
return 999;
}
int main() {
SqStack OPTR;
InitStack(&OPTR);
Push(&OPTR, '#');
printf(" Type in brackets to" # "At the end \n");
char c;
c = getchar();
int m = 1; // Determine if the final match is perfect An exact match A value of 1 , or for 0
char OP1[] = {'[', '(', '{'}; // Parenthetical character set
char OP2[] = {']', ')', '}'}; // Postbracketed character set
while (c != '#') {
if (CheckChar(c, OP1) < 3) {
Push(&OPTR, c);
c = getchar();
} else {
if (CheckChar(GetTop(OPTR), OP1) == CheckChar(c, OP2)) {
// If two symbols that need to be checked are in the same place in the set of preposition and postposition parentheses, the pairing is successful
// For example, [ and ] . [ The position in the set of leading parentheses 1 . ] The position in the set of postparenthesis 1 , so the match is successful
Pop(&OPTR, &c);
c = getchar();
continue;
} else {
m = 0;
break;
}
}
}
if (GetTop(OPTR) != c)m = 0;
if (m == 1)printf("\n The brackets match! ");
else printf("\n The bracket match failed! ");
return 0;
}