在C语言中，使用栈来实现括号匹配的检验是一个常见的应用。栈的特性（后进先出）使得它非常适合用来处理这类问题，因为我们可以按照括号的出现顺序将其压入栈中，当遇到闭合括号时，从栈顶弹出一个元素进行比较。
以下是括号匹配检验的基本规则：
· 遇到左括号（(、[、{ 或 <）时，将其压入栈中。
· 遇到右括号时，检查栈顶元素是否与之匹配。如果匹配，则弹出栈顶元素；否则，说明括号不匹配。
· 在遍历完所有字符后，如果栈为空，则说明所有括号都匹配；否则，说明存在未匹配的括号。
以下是使用C语言实现括号匹配检验的示例代码：
|
#include <stdio.h> |
|
#include <stdlib.h> |
|
#include <stdbool.h> |
|
|
|
#define MAX_STACK_SIZE 100 |
|
|
|
typedef struct { |
|
char data[MAX_STACK_SIZE]; |
|
int top; |
|
} Stack; |
|
|
|
void initStack(Stack *s) { |
|
s->top = -1; |
|
} |
|
|
|
bool isEmpty(Stack *s) { |
|
return s->top == -1; |
|
} |
|
|
|
bool push(Stack *s, char c) { |
|
if (s->top >= MAX_STACK_SIZE - 1) { |
|
return false; |
|
} |
|
s->data[++s->top] = c; |
|
return true; |
|
} |
|
|
|
bool pop(Stack *s, char *c) { |
|
if (isEmpty(s)) { |
|
return false; |
|
} |
|
*c = s->data[s->top--]; |
|
return true; |
|
} |
|
|
|
bool isMatchingPair(char open, char close) { |
|
return (open == '(' && close == ')') || |
|
(open == '[' && close == ']') || |
|
(open == '{' && close == '}') || |
|
(open == '<' && close == '>'); |
|
} |
|
|
|
bool checkParentheses(const char *expr) { |
|
Stack s; |
|
initStack(&s); |
|
|
|
for (int i = 0; expr[i] != '\0'; i++) { |
|
char c = expr[i]; |
|
if (c == '(' || c == '[' || c == '{' || c == '<') { |
|
if (!push(&s, c)) { |
|
return false; // 栈满，无法继续检查 |
|
} |
|
} else if (c == ')' || c == ']' || c == '}' || c == '>') { |
|
char open; |
|
if (!pop(&s, &open) || !isMatchingPair(open, c)) { |
|
return false; // 栈空或括号不匹配 |
|
} |
|
} |
|
} |
|
|
|
return isEmpty(&s); // 如果栈为空，则所有括号都匹配 |
|
} |
|
|
|
int main() { |
|
const char *expr1 = "[({})]"; // 匹配 |
|
const char *expr2 = "[(}]"; // 不匹配 |
|
|
|
if (checkParentheses(expr1)) { |
|
printf("表达式 '%s' 中的括号匹配。\n", expr1); |
|
} else { |
|
printf("表达式 '%s' 中的括号不匹配。\n", expr1); |
|
} |
|
|
|
if (checkParentheses(expr2)) { |
|
printf("表达式 '%s' 中的括号匹配。\n", expr2); |
|
} else { |
|
printf("表达式 '%s' 中的括号不匹配。\n", expr2); |
|
} |
|
|
|
return 0; |
|
} |
这个代码定义了一个栈结构体Stack，并实现了栈的基本操作（初始化、判断是否为空、入栈和出栈）。isMatchingPair函数用于判断一对括号是否匹配。checkParentheses函数遍历输入的表达式，根据括号类型进行压栈或匹配检查。最后，如果栈为空，说明所有括号都匹配；否则，存在未匹配的括号。
