判断字符串中的括号是否匹配－C语言

逃离我推掉我的手 2022-08-19 14:28 202阅读 0赞

## 判断字符串中的括号是否匹配－C语言 ##

递归实现：  
先检搜一对匹配的括号，再对里面的内容进行匹配，匹配完后再继续往下匹配……  
![这里写图片描述][20160121125402765]

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // 在start与end中搜索匹配 
    int fun(char *str, int start, int end)
    {
        char chLeft;        // 左括号
        char chRight;       // 右括号
        while((start<=end) && (str[start] != '\0'))
        {
            switch(str[start])
            {
                case '(':
                    chLeft = str[start];
                    chRight = ')';
                    break;
                case '[':
                    chLeft = str[start];
                    chRight = ']';
                    break;
                case '{':
                    chLeft = str[start];
                    chRight = '}';
                    break;
    
                case ')':
                case ']':
                case '}':
                    return 0;
                default:
                    chLeft = '\0';
                    break;
            }
            if(str[start] == chLeft)
            {
                int a = 1;
                int b=0;
                int t = start+1;
                while((t<=end) && (str[t] != '\0')) // 搜索匹配的右括号 
                {
                    if(str[t] == chLeft)
                        ++a;
                    if(str[t] == chRight)
                        ++b;
                    if(b>a)
                        return 0;
                    if(a == b)      // 再对匹配括号里面的括号进行匹配 
                    {
                        if(0 == fun(str, start+1, t-1)) // 递归调用 
                            return 0;
                        start=t;
                        break;
                    }
                    ++t;
                }
                if(a>b)
                    return 0;
            }
            ++start;
        }
        return 1;
    }
    
    int main(void){
        char str[1024];
        gets(str);
        int length = strlen(str);
        int i = fun(str, 0, length-1);
        if(i == 1){
            printf("括号匹配！\n");
        }else{
            printf("括号不匹配！\n");
        }
        return 0;
    }

把Hello World输进去：  
![这里写图片描述][20160121122226191]

栈实现：  
将字符逐个取出，若遇到左括号，则进栈；若遇到右括号，这时侯栈为空的话括号就不匹配，不为空，则出栈，并判断左括号与右括号是否对；当字符串判断完后，栈应为空，否则括号不匹配。栈是一种后进先出的数据结构，相关知识请自行百度

![这里写图片描述][20160121132641934]

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define STACKLENGTH 1024
    
    char stack[STACKLENGTH];
    int top = STACKLENGTH;
    
    /*判断栈是否为空*/
    int empty(){
        if(top == STACKLENGTH)
            return 1;
        return 0;
    }
    
    /*进栈*/
    void push(char ch)
    {
        top--;
        stack[top] = ch;
    }
    
    /*出栈*/
    char pop()
    {
        char ch = stack[top];
        top++;
        return ch;
    }
    
    int fun(char *str)
    {
        while(*str != '\0')
        {
            char chLeft = '\0';
            char chRight = '\0';
            char ch = *str;
            switch(ch)
            {
                case '(':
                case '[':
                case '{':
                    push(ch);   // 找到左括号 进栈
                    break;
                case ')':
                    chLeft = '(';
                    chRight = ch;
                    break;
                case ']':
                    chLeft = '[';
                    chRight = ch;
                    break;
                case '}':
                    chLeft = '{';
                    chRight = ch;
                    break;
                default:
                    break;
            }
            if(chRight == ch)   // 找到右括号 
            {
                if(empty())
                {
                    return 0;
                }
                else
                {
                    char t = pop(); // 出栈 
                    if(t != chLeft){
                        return 0;
                    }
                }
            }
            str++;
        }
        if(empty())
        {
            return 1;
        }
        return 0;
    }
    
    int main(void)
    {
        char array[1024];
        gets(array);
        int i = fun(array);
        if(i == 1){
            printf("括号匹配！\n");
        }else{
            printf("括号不匹配！\n");
        }
        return 0;
    }

试一试：  
![这里写图片描述][20160121123957713]

![这里写图片描述][20160121124159416]  
编译环境：Dev-C++5.11

[20160121125402765]: /images/20220731/6a540d440c154a1e8c25551bbef501ff.png
[20160121122226191]: /images/20220731/0515c639801e4a3db697c377c0f2d75a.png
[20160121132641934]: /images/20220731/9fafcd79f33448b39f1379bd2c4c85c6.png
[20160121123957713]: /images/20220731/1217d140c3384209bcf1bb6b3278d907.png
[20160121124159416]: /images/20220731/ecf4559fb6034aa9b7df850b8bee757a.png