3. 括号匹配

- 日理万妓 2022-04-06 04:56 122阅读 0赞

## 3. 括号匹配 ##

假设一个算术表达式中包含圆括号、方括号两种类型的括号，试编写一个判断表达式中括号是否匹配的程序，匹配返回Match succeed!，否则返回Match false!。

例

\[1+2\*(3+4\*(5+6))\]括号匹配

(1+2)\*(1+2\*\[(1+2)+3)括号不匹配

## 输入 ##

包含圆括号、方括号两种类型括号的算术表达式

## 输出 ##

匹配输出Match succeed!

不匹配输出 Match false!

例

输入\[1+2\* (3+4\*(5+6))\]

输出Match succeed!

#include "stdio.h"
    #include "stdlib.h"
    
    typedef struct list{
        char ch;
        struct list *next;
    } NODE;
    
    int main(int argc, char const *argv[])
    {
        char kuohao, check;
        int flag = 0;
        NODE *head, *p, *q, *q1;
        p = (NODE *)malloc(sizeof(NODE));
        p->ch = '\0';
        p->next = NULL;
        head = p;
        q = head;
    
        while((kuohao = getchar()) != '\n'){
            if(kuohao != '(' && kuohao != ')' && kuohao != '[' && kuohao != ']')
                continue;
            if(kuohao == '(' || kuohao == '['){
                p = (NODE *)malloc(sizeof(NODE));
                p->ch = kuohao;
                p->next = q->next;
                q->next = p;
            }
            else{
                if(q->next == NULL){
                    flag = 1;
                    printf("Match false!\n");
                    break;
                }
                else{
                    if((q->next->ch == '(' && kuohao == ')') || (q->next->ch == '[' && kuohao == ']')){
                        q1 = q->next;
                        q->next = q->next->next;
                        free(q1);
                    }
                    else{
                        flag = 1;
                        printf("Match false!\n");
                        break;
                    }
                }
            }
        }
        if(flag == 0 && head->next != NULL){
            printf("Match false!\n");
        }
        else if(flag == 0 && head->next == NULL){
            printf("Match succeed!\n");
        }
        return 0;
    }