数据结构 3.2章：括号匹配(c)_数据结构括号匹配

栈是一种常用的数据结构，可以用来实现括号匹配的分析。

括号匹配的问题可以简单描述为，在一串字符串中，括号是否能够正确匹配。具体地说，需要判断字符串中的每一个左括号是否都有与之对应的右括号，且左右括号的顺序应该符合基本的语法规则（即不允许跨越其他括号或其他字符）。

下面是基于栈的括号匹配分析算法：

(1) 遍历字符串，当遇到一个左括号时，将其压入栈中。

(2) 当遇到一个右括号时，弹出栈顶元素。检查该栈顶元素是否与当前的右括号匹配。如果匹配，则继续遍历下一个字符；如果不匹配，则返回false。

(3) 如果遍历完字符串后，栈为空，则说明括号匹配正确；否则，说明括号不匹配，返回false。

以上算法的核心思路是，将左括号压入栈中，每次遇到一个右括号，就弹出栈顶元素并检查其与当前右括号是否匹配。由于栈具有后进先出的特性，因此栈顶元素都是最近压入的未匹配的左括号，与当前的右括号最容易进行匹配。

基于栈的括号匹配分析算法具有时间复杂度O(n)和空间复杂度O(n)，且代码实现简单。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define STACK_MAX_SIZE 10

/**
 * Linear stack of integers. The key is data.
 */
typedef struct CharStack 
{
    int top;
    int data[STACK_MAX_SIZE]; //The maximum length is fixed.
}CharStack, *CharStackPtr;



void outputStack(CharStackPtr paraStack);
CharStackPtr charStackInit(void);
void push(CharStackPtr paraStackPtr, int paraValue);
char pop(CharStackPtr paraStackPtr);
void pushPopTest(void);
bool bracketMatching(char* paraString, int paraLength);
void bracketMatchingTest(void);

/**
 The entrance.
 */
void main() 
{
	// pushPopTest();
	bracketMatchingTest();
}// Of main


/**
 * Output the stack.
 */
void outputStack(CharStackPtr paraStack) 
{
	int i;
    for (i = 0; i <= paraStack->top; i ++) 
	{
        printf("%c ", paraStack->data[i]);
    }// Of for 
    printf("\r\n");
}// Of outputStack()

/**
 * Initialize an empty char stack. No error checking for this function.
 * @param paraStackPtr The pointer to the stack. It must be a pointer to change the stack.
 * @param paraValues An int array storing all elements.
 */
CharStackPtr charStackInit(void) 
{
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(struct CharStack));
	resultPtr->top = -1;

	return resultPtr;
}//Of charStackInit

/**
 * Push an element to the stack.
 * @param paraValue The value to be pushed.
 */
void push(CharStackPtr paraStackPtr, int paraValue) 
{
    // Step 1. Space check.
    if (paraStackPtr->top >= STACK_MAX_SIZE - 1) 
	{
        printf("Cannot push element: stack full.\n");
        return;
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top ++;

	// Step 3. Push element.
    paraStackPtr->data[paraStackPtr->top] = paraValue;
}// Of push

/**
 * Pop an element from the stack.
 * @return The popped value.
 */
char pop(CharStackPtr paraStackPtr) 
{
    // Step 1. Space check.
    if (paraStackPtr->top < 0) 
	{
        printf("Cannot pop element: stack empty.\n");
        return '\0';
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top --;

	// Step 3. Push element.
    return paraStackPtr->data[paraStackPtr->top + 1];
}// Of pop

/**
 * Test the push function.
 */
void pushPopTest(void) 
{
    printf("---- pushPopTest begins. ----\n");
    char ch;
    
	// Initialize.
    CharStackPtr tempStack = charStackInit();
    printf("After initialization, the stack is: ");
	outputStack(tempStack);

	// Pop.
	for (ch = 'a'; ch < 'm'; ch ++) 
	{
		printf("Pushing %c.\n", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}//Of for i

	// Pop()
	int i;
	for (i = 0; i < 3; i ++) 
	{
		ch = pop(tempStack);
		printf("Pop %c.\n", ch);
		outputStack(tempStack);
	}//Of for i

    printf("---- pushPopTest ends. ----\n");
}// Of pushPopTest

/**
 * Is the bracket matching?
 * 
 * @param paraString The given expression.
 * @return Match or not.
 */
bool bracketMatching(char* paraString, int paraLength) 
{
	// Step 1. Initialize the stack through pushing a '#' at the bottom.
    CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;

	// Step 2. Process the string.
	int i;
	for (i = 0; i < paraLength; i++) 
	{
		tempChar = paraString[i];

		switch (tempChar) 
		{
		case '(':
		case '[':
		case '{':
			push(tempStack, tempChar);
			break;
		case ')':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '(') 
			{
				return false;
			} // Of if
			break;
		case ']':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '[') 
			{
				return false;
			} // Of if
			break;
		case '}':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '{') 
			{
				return false;
			} // Of if
			break;
		default:
			// Do nothing.
			break;
		}// Of switch
	} // Of for i

	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') 
	{
		return false;
	} // Of if

	return true;
}// Of bracketMatching

/**
 * Unit test.
 */
void bracketMatchingTest(void) 
{
	char* tempExpression = "[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d\n", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d\n", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d\n", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d\n", tempExpression, tempMatch);


	tempExpression = ")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d \n", tempExpression, tempMatch);
}// Of bracketMatchingTest



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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225