C语言括号匹配问题

清疚 2022-03-12 16:56 180阅读 0赞

**主要思路：**

1.  主要是借助栈对括号进行匹配，遍历整个字符串，若为左括号，则入栈；若为右括号，则判断栈是否为空，以及栈顶元素与当前元素是否匹配；
2.  要特别注意每个字符串的遍历结束的条件。

/*-------------------------------------------------------
    功能：可进行括号匹配，输入可包括{}, [], (), 其他任意字符
    输入示例：
    3
    {
       {
       {
       {
       {
       {
       {[[[[[1314]]]]]}}}}}}}
    {
       {
       {
       {
       {[[[(())]}}}}}
    ((({
       {
       {
       {
       {[[521]]}}}}})))
    输出示例：
    Yes
    No
    Yes
    Author: Zhang Kaizhou
    Date:2019-3-6 14:59:06
    --------------------------------------------------------*/
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 1000
    
    typedef struct node{ // 定义一个结点数据类型用于存放每行结果
        char res[10];
        struct node * pnext;
    } Node;
    
    typedef struct{ // 定义一个栈数据类型，用于符号判断
        char oper[MAXSIZE];
        int top;
    } OperStack;
    
    void judge_blanket_match(char * str, Node * p);
    void push_oper(OperStack * p_oper, char ch);
    void pop_oper(OperStack * p_oper, char * ch);
    void list_tail_insert(Node ** pphead, Node ** pptail, Node * p);
    void list_print(Node * phead);
    
    int main(){
        int n, i;
        char str[MAXSIZE] = { '\0' };
        Node * phead = NULL, * ptail = NULL;
        scanf("%d", &n);
        for(i = 0; i < n; i++){ // 循环输入n组测试数据
            scanf("%s", str);
            Node * pnew = (Node *)calloc(1, sizeof(Node)); // 产生一个结点用于存储结果
            judge_blanket_match(str, pnew);
            list_tail_insert(&phead, &ptail, pnew);
        }
        list_print(phead);
    
        free(phead);
        free(ptail);
        return 0;
    }
    
    void judge_blanket_match(char * str, Node * p){
        OperStack * p_oper = (OperStack *)calloc(1, sizeof(OperStack)); // 定义一个栈指针
        p_oper->top = -1; // 初始化栈顶指针
        int flag = 0;
        char temp;
        while(* str != '\0'){ // 遍历整个字符串
            switch(* str){
            case '{':
            case '[':
            case '(':
                push_oper(p_oper, * str); // 左括号直接入栈
                str++;
                break;
            case '}':
                if(p_oper->top >= 0 && p_oper->oper[p_oper->top] == '{'){ // 右括号时，若栈非空，判断与栈顶元素是否匹配
                    pop_oper(p_oper, &temp); // 若匹配，则出栈栈顶元素
                    str++;
                    break;
                }else{ // 不匹配，则结果为No，终止循环
                    strcpy(p->res, "No");
                    flag = 1;
                    * str = '\0'; // 终止遍历
                    break;
                }
            case ']':
                if(p_oper->top >= 0 && p_oper->oper[p_oper->top] == '['){
                    pop_oper(p_oper, &temp);
                    str++;
                    break;
                }else{
                    strcpy(p->res, "No");
                    flag = 1;
                    * str = '\0';
                    break;
                }
            case ')':
                if(p_oper->top >= 0 && p_oper->oper[p_oper->top] == '('){
                    pop_oper(p_oper, &temp);
                    str++;
                    break;
                }else{
                    strcpy(p->res, "No");
                    flag = 1;
                    * str = '\0';
                    break;
                }
            default:
                str++;
                break;
            }
        }
        if(flag == 0 && p_oper->top < 0){
            strcpy(p->res, "Yes");
        }else{
            strcpy(p->res, "No");
        }
        free(p_oper); // 释放操作数栈
        p_oper = NULL; // 原指针置空
        return;
    }
    
    void push_oper(OperStack * p_oper, char ch){
        if(p_oper->top == MAXSIZE - 1){
            printf("The operator stack is full!\n");
        }else{
            p_oper->top++;
            p_oper->oper[p_oper->top] = ch;
        }
        return;
    }
    
    void pop_oper(OperStack * p_oper, char * ch){
        if(p_oper->top < 0){
            printf("The operator stack is empty!\n");
        }else{
            * ch = p_oper->oper[p_oper->top];
            p_oper->top--;
        }
        return;
    }
    
    void list_tail_insert(Node ** pphead, Node ** pptail, Node * p){
        if(* pphead == NULL){
            * pphead = p;
            * pptail = p;
        }else{
            (*pptail)->pnext = p;
            * pptail = p;
        }
        return;
    }
    
    void list_print(Node * phead){
        while(phead != NULL){
            puts(phead->res);
            phead = phead->pnext;
        }
        return;
    }