【数据结构--栈的应用--括号匹配】_数据结构括号匹配

作者：盐析白兔 | 2024-06-03 18:05:12

踩

数据结构括号匹配

文章目录

- 括号匹配

括号匹配

前言

括号匹配问题是较为经典的栈的应用了，在Leetcode和数据结构书中时常出现

例如

给定一个字符串，其包含( , ) ,{ , } , [ , ]以及数字，要求判断其括号是否匹配，即：

左括号必须用相同类型的右括号闭合
左括号必须以正确的顺序闭合

实例 1：

输入: "[2 + (1 - 3)] * 4"
输出：1
1
2

实例 2：

输入："(  )    )"
输出：0
1
2

算法思想

当遇到 ‘(’ ，’[’ ，’{’ 时进行压栈操作，将其压入栈中
当遇到 ‘)’ ，’]’， ‘}’ 时进行弹栈操作，若此时弹出的元素和此时遇到的括号匹配，则继续进行，否则直接退出（即不匹配）
为了防止出现单独的 ‘)’ ，’]’ 或 ‘}’ 导致判断错误，在栈的栈底添加了 ‘#’ 标识符，若匹配结束而最后弹出的不是 ‘#’ 则表示有多余单独的 ‘)’ ，’]’ 或 ‘}’ ，则直接退出（即也不匹配）

栈的定义及其操作

typedef struct CharStack
{
    int top;    /* 用于栈顶指针 */
    int data[MAXSIZE];
} *CharStackPtr,CharStack;

//输出栈
void outPutStack(CharStackPtr tempStack)
{
    for(int i = 0; i <= tempStack->top; ++i)
    {
        printf("%c ",tempStack->data[i]);
    }
    printf("\n");
}

//初始化栈
CharStackPtr CharStackInit()
{
    CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
    resultPtr->top = -1;
    return resultPtr;
}

//压栈
void push(CharStackPtr tempStackPtr, char tempValue)
{
    if(tempStackPtr->top >= MAXSIZE - 1)
    {
        printf("无法压入元素%c：堆栈已满!\n",tempValue);
        return ;
    }
    tempStackPtr->top ++;
    tempStackPtr->data[tempStackPtr->top] = tempValue;
}

//弹栈
char pop(CharStackPtr tempStackPtr)
{
    if (tempStackPtr->top == -1)
    {
        printf("不能弹出元素：堆栈为空!\n");
        return NULL;
    }
    tempStackPtr->top --;
    return tempStackPtr->data[tempStackPtr->top+1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

括号匹配核心代码

//括号匹配
bool parenthesisMatching(char* tempString)
{
    /* 在栈底部压入'#'并初始化堆栈。 */
    CharStackPtr tempStack = CharStackInit();
    push(tempStack,'#');
    char tempChar,tempPopedChar;
    for(int i = 0; i< strlen(tempString); ++i)
    {
        tempChar = tempString[i];
        switch (tempChar)
        {
        case '(':
        case '[':
        case '{':
            push(tempStack,tempChar);
            break;
        case ')':
            tempPopedChar = pop(tempStack);
            if(tempPopedChar != '(')
            {
                return false;
            }
            break;
        case ']':
            tempPopedChar = pop(tempStack);
            if(tempPopedChar != '[')
            {
                return false;
            }
            break;
        case '}':
            tempPopedChar = pop(tempStack);
            if(tempPopedChar != '{')
            {
                return false;
            }
            break;
        default:
            break;
        }
    }
    tempPopedChar = pop(tempStack);
    if(tempPopedChar != '#')
    {
        return false;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

完整代码

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define MAXSIZE 10

typedef struct CharStack
{
    int top;    /* 用于栈顶指针 */
    int data[MAXSIZE];
} *CharStackPtr,CharStack;

//输出栈
void outPutStack(CharStackPtr tempStack)
{
    for(int i = 0; i <= tempStack->top; ++i)
    {
        printf("%c ",tempStack->data[i]);
    }
    printf("\n");
}

//初始化栈
CharStackPtr CharStackInit()
{
    CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
    resultPtr->top = -1;
    return resultPtr;
}

//压栈
void push(CharStackPtr tempStackPtr, char tempValue)
{
    if(tempStackPtr->top >= MAXSIZE - 1)
    {
        printf("无法压入元素%c：堆栈已满!\n",tempValue);
        return ;
    }
    tempStackPtr->top ++;
    tempStackPtr->data[tempStackPtr->top] = tempValue;
}

//弹栈
char pop(CharStackPtr tempStackPtr)
{
    if (tempStackPtr->top == -1)
    {
        printf("不能弹出元素：堆栈为空!\n");
        return NULL;
    }
    tempStackPtr->top --;
    return tempStackPtr->data[tempStackPtr->top+1];
}

//括号匹配
bool parenthesisMatching(char* tempString)
{
    /* 在栈底部压入'#'并初始化堆栈。 */
    CharStackPtr tempStack = CharStackInit();
    push(tempStack,'#');
    char tempChar,tempPopedChar;
    for(int i = 0; i< strlen(tempString); ++i)
    {
        tempChar = tempString[i];
        switch (tempChar)
        {
        case '(':
        case '[':
        case '{':
            push(tempStack,tempChar);
            break;
        case ')':
            tempPopedChar = pop(tempStack);
            if(tempPopedChar != '(')
            {
                return false;
            }
            break;
        case ']':
            tempPopedChar = pop(tempStack);
            if(tempPopedChar != '[')
            {
                return false;
            }
            break;
        case '}':
            tempPopedChar = pop(tempStack);
            if(tempPopedChar != '{')
            {
                return false;
            }
            break;
        default:
            break;
        }
    }
    tempPopedChar = pop(tempStack);
    if(tempPopedChar != '#')
    {
        return false;
    }
    return true;
}

//测试
void parenthesisMatchingTest()
{
    char *tempExpression;
    tempExpression = "[2 + (1 - 3)] * 4";
    bool tempMatch = parenthesisMatching(tempExpression);
    printf("表达式%s括号匹配吗?  %d\n",tempExpression,tempMatch);

    tempExpression = "(  )    )";
    tempMatch = parenthesisMatching(tempExpression);
    printf("表达式%s括号匹配吗?  %d\n",tempExpression,tempMatch);

    tempExpression = "()()(())";
    tempMatch = parenthesisMatching(tempExpression);
    printf("表达式%s括号匹配吗?  %d\n",tempExpression,tempMatch);
    
    tempExpression = "({}[])";
    tempMatch = parenthesisMatching(tempExpression);
    printf("表达式%s括号匹配吗?  %d\n",tempExpression,tempMatch);

    tempExpression = ")(";
    tempMatch = parenthesisMatching(tempExpression);
    printf("表达式%s括号匹配吗?  %d\n",tempExpression,tempMatch);
}

int main()
{
    parenthesisMatchingTest();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

运行测试

表达式[2 + (1 - 3)] * 4括号匹配吗?  1
表达式(  )    )括号匹配吗?  0
表达式()()(())括号匹配吗?  1
表达式({}[])括号匹配吗?  1
表达式)(括号匹配吗?  0
1
2
3
4
5

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】