admin 管理员组文章数量: 1087649
栈实现括号匹配
栈实现括号匹配
匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。
算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。另外,在算法的开始和结束时,栈都应该是空的.所以匹配到最后还要判断栈是否为空,若非空,则说明匹配失败.
创建一个StackTest.h的文件
//以下是括号匹配具体代码
void BracketMatch(const char *str,int size)
{Stack stack;char ch;char leftBracket;int i = 0;StackInit(&stack);for (i=0;i<size;i++){ch = str[i];switch(ch){case '(':case '[':case '{':StackPush(&stack,(DataType)ch);break;case ')':case ']':case '}':if (StackEmpty(&stack)){printf("右括号多\n");StackDestory(&stack);return;}leftBracket = (char)StackTop(&stack);StackPop(&stack);if (leftBracket == '(' && ch != ')'){printf("不匹配\n");return;}if (leftBracket == '[' && ch != ']'){printf("不匹配\n");return;}if (leftBracket == '{' && ch != '}'){printf("不匹配\n");return;}default:break;}}if (!StackEmpty(&stack)){printf("左括号多\n");return;}printf("匹配正常\n");
}
//以下是Stack.h文件
typedef int DataType;#define MAX_SIZE (100)typedef struct Stack{DataType arr[MAX_SIZE];int top;
}Stack;void StackInit(Stack *stack)
{stack->top = 0;
}void StackDestory(Stack *stack)
{stack->top = 0;
}void StackPush(Stack *stack,DataType data)
{assert(stack->top <MAX_SIZE);stack->arr[stack->top++] = data;
}void StackPop(Stack *stack)
{assert(stack->top > 0);stack->top--;
}DataType StackTop(const Stack *stack)
{assert(stack->top > 0);return stack->arr[stack->top-1];
}int stackSize(Stack *stack)
{return stack->top;
}int StackFull(Stack *stack)
{return stack->top >= MAX_SIZE;
}int StackEmpty(Stack *stack)
{return stack->top <= 0;
}
//以下我们测试括号是否匹配
void TestBracket()
{const char *seq[]={"(())abc{[(])}","(()))abc{[]}","(()()abc{[]}","(())abc{[]()}"};int i = 0;for (i=0;i<4;i++){BracketMatch(seq[i],strlen(seq[i]));}
}打印结果：
不匹配
右括号多
左括号多
匹配正常
//以上就是括号匹配的问题，如有问题望批评指正本文标签： 栈实现括号匹配
版权声明：本文标题：栈实现括号匹配 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700299621a386265.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论