数据结构--栈的应用--括号合法性判断(机判断) 链表栈实现

数据结构–栈的应用–括号合法性判断(机判断) 链表栈实现

本文代码中的栈用不带头结点的链栈实现

题目如下：

假设一个算术表达式中包含圆括号、方括号和花括号3种类型的括号，编写一个算法来判別表式中的括号是否配対，以字符“ \0”作为算术表式的结束符。

ps：题目来源2025王道数据结构

解题思路

1. 用栈来维护括号的匹配
2. 从左到右扫描，遇到左括号进栈，遇到右括号出栈看看栈中是不是所匹配的左括号（如果此时栈空，那么一定是非法的括号）
3. 扫描完如果栈非空，那么一定是非法的括号

解决代码

严格按照上述的思路编写的代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#define MAXSIZE 100
using namespace std;
typedef struct Linknode
{
	char data;
	Linknode *next;
}Linknode;
bool isEmpty(Linknode *top)
{
	return top == NULL;
}
void push(Linknode **top, char val)
{
	Linknode *newnode = (Linknode*)malloc(sizeof(Linknode));
	if (newnode == NULL) {
        printf("内存分配失败，入栈操作失败。\n");
        return;
    }
	newnode->data = val;
	newnode->next = *top;
	*top = newnode;
}
void pop(Linknode **top, char &val)
{
	if (isEmpty(*top)) {
        printf("栈已空，无法进行出栈操作。\n");
        return;
    }
	Linknode *tmp = *top;
	val = (*top)->data;
	*top = (*top)->next;
	free(tmp);
}
int main()
{
	char arr[MAXSIZE];
	cin >> arr;
	int i = 0;
	Linknode *top = NULL;
	while (arr[i] != '\0')
	{
		if (arr[i] == '(' || arr[i] == '[' || arr[i] == '{')
			push(&top, arr[i]);
		else 
		{
			char ch;
			if (isEmpty(top))
			{
				cout << "括号非法！！！" << endl;
				return 0;
			}
			pop(&top, ch);
			if ((ch == '(' && arr[i] != ')') || (ch == '[' && arr[i] != ']') || (ch == '{' && arr[i] != '}'))
			{
				cout << "括号非法！！！" << endl;
				return 0;
			}
		}
		i++;
	}
	if (!isEmpty(top))
		cout << "括号非法！！！" << endl;
	else
		cout << "括号合法" << endl;
	return 0;
}
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