c语言栈的括号匹配代码
时间: 2024-06-18 22:02:57 浏览: 19
栈是一种常用的数据结构,可以用于括号匹配的问题。下面是一个简单的C语言代码示例:
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define STACK_INIT_SIZE 100 // 栈的初始大小
#define STACKINCREMENT 10 // 栈的增量
typedef char ElemType;
typedef struct {
ElemType *top; // 栈顶指针
ElemType *base; // 栈底指针
int stacksize; // 当前已分配的存储空间,以元素为单位
} SqStack;
// 初始化栈
bool InitStack(SqStack *s) {
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!s->base) {
exit(1); // 存储分配失败
}
s->top = s->base;
s->stacksize = STACK_INIT_SIZE;
return true;
}
// 获取栈顶元素
bool GetTop(SqStack s, ElemType *e) {
if (s.top == s.base) {
return false; // 栈为空
}
*e = *(s.top - 1);
return true;
}
// 压栈操作
bool Push(SqStack *s, ElemType e) {
// 栈满,追加存储空间
if (s->top - s->base >= s->stacksize) {
s->base = (ElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!s->base) {
exit(1); // 存储分配失败
}
s->top = s->base + s->stacksize;
s->stacksize += STACKINCREMENT;
}
*(s->top++) = e;
return true;
}
// 弹栈操作
bool Pop(SqStack *s, ElemType *e) {
if (s->top == s->base) {
return false; // 栈为空
}
*e = *(--s->top);
return true;
}
// 判断是否匹配
bool Match(char a, char b) {
if ((a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}')) {
return true;
} else {
return false;
}
}
// 括号匹配函数
bool BracketMatch(char *str) {
SqStack s;
InitStack(&s);
char ch;
while (*str != '\0') {
switch (*str) {
case '(':
case '[':
case '{':
Push(&s, *str);
break;
case ')':
case ']':
case '}':
if (GetTop(s, &ch) && Match(ch, *str)) { // 匹配成功
Pop(&s, &ch);
} else { // 匹配失败
return false;
}
break;
default:
break;
}
++str; // 处理下一个字符
}
if (s.top == s.base) { // 栈为空,匹配成功
return true;
} else { // 栈非空,匹配失败
return false;
}
}
int main() {
char str[] = "{[(3+5)*2-1]+2}/2";
if (BracketMatch(str)) {
printf("括号匹配成功\n");
} else {
printf("括号匹配失败\n");
}
return 0;
}
```
这段代码中定义了一个栈的结构体`SqStack`,并实现了栈的初始化、获取栈顶元素、压栈、弹栈等基本操作。在括号匹配函数`BracketMatch`中,遍历输入字符串中的每个字符,并将左括号压入栈中;当遇到右括号时,取出栈顶元素进行匹配,若匹配成功则弹出栈顶元素,否则返回匹配失败。最后判断栈是否为空,若为空则说明括号全部匹配成功,否则匹配失败。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)