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;
}

Related articles: