我的网站: www.mengyingjie.com http://www.mengyingjie.com/
1 要求
编写程序检查该字符串的括号是否成对出现, 而且不能交叉出现.
输入:
一个字符串, 里边可能包含 "()","{}","[]" 三种括号,"#" 结束
输出:
成功: 代表括号成对出现并且嵌套正确
失败: 未正确使用括号字符.
2 分析
用一个栈, 就能解决该问题, 左括号栈顶字符必须和第一个入栈的右括号字符匹配.
栈介绍: 栈是一种特殊的线性表, 仅能在线性表的一端操作.
栈的特性: 后进先出(LIFO)
由于正在学数据结构, 于是栈的定义与操作都是自己编写的, 为了巩固概念
3 代码
- #include<stdio.h>
- #include <malloc.h>
- #define STACK_INT_SIZE 100
- #define STACKINCREMENT 10
- #define bool int // 自定义 bool 变量
- #define SElemType char
- typedef struct {
- SElemType *base; // 栈基地址
- SElemType *top; // 栈顶地址
- int stacksize;
- } SqStack;
- //------ 基本操作的算法描述 ------
- // 构建一个空栈
- bool InitStack(SqStack *S) {
- S->base = (SElemType *) malloc(STACK_INT_SIZE * sizeof(SElemType)); // 开辟新的空间
- if (!S->base) return 0; // 开辟失败返回 0
- S->top = S->base;
- S->stacksize = STACK_INT_SIZE;
- return 1;
- }
- // 若栈不为空, 返回栈顶元素, 并返回 true 否则返回 false
- bool GetTop(SqStack S) {
- if (S.top == S.base) return 0;
- return *(S.top - 1);
- }
- // 插入元素 为新的栈顶元素
- bool Push(SqStack *S, SElemType e) {
- if (S->top - S->base>= S->stacksize) // 如果栈满 需要增加空间
- {
- S->base = (SElemType *) realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
- if (!S->base) return 0;
- S->top = S->base + S->stacksize;
- S->stacksize += STACKINCREMENT;
- }
- *(S->top++) = e;
- return 1;
- }
- // 若栈不为空, 则删除栈顶元素, 用 e 返回其值, 返回 true, 否则返回 false
- bool Pop(SqStack *S, SElemType *e) {
- if (S->top == S->base) return 0;
- *e = *(--S->top);
- return 1;
- }
- // 检查括号字符在字符集中的位置
- int CheckChar(char c, char OP[]) {
- int i;
- for (i = 0; i < 3; i++)
- if (c == OP[i])return i;
- return 999;
- }
- int main() {
- SqStack OPTR;
- InitStack(&OPTR);
- Push(&OPTR, '#');
- printf("输入括号以"#"结尾 \ n");
- char c;
- c = getchar();
- int m = 1; // 判断最终是否完全匹配 完全匹配 值为 1, 否则为 0
- char OP1[] = {'[', '(', '{'}; // 前置括号字符集
- char OP2[] = {']', ')', '}'}; // 后置括号字符集
- while (c != '#') {
- if (CheckChar(c, OP1) < 3) {
- Push(&OPTR, c);
- c = getchar();
- } else {
- if (CheckChar(GetTop(OPTR), OP1) == CheckChar(c, OP2)) {
- // 如果需要检验的两个符号在前置和后置括号集中的位置相同则表示配对成功
- // 例如 [和],[在前置括号集中的位置 1,] 在后置括号集中的位置 1, 所以匹配成功
- Pop(&OPTR, &c);
- c = getchar();
- continue;
- } else {
- m = 0;
- break;
- }
- }
- }
- if (GetTop(OPTR) != c)m = 0;
- if (m == 1)printf("\n 括号完全匹配!");
- else printf("\n 括号匹配失败!");
- return 0;
- }
遇到此类问题, 但看了文章还是未解决,
评论或加 QQ:781378815
来源: https://www.cnblogs.com/mengyingjie/p/11595513.html