栈之括号匹配问题

习题1：括号匹配问题

问题简单描述

本来( )这两个括号是成对存在的，如果遇到出现不成对情况，并且成对的括号是以(左括号在前，)右括号在后成对存在的，连续单独出现左括号、右括号或者左括号里面夹杂不合理的左右括号都是错误信息。也就是当出现一个右括号，栈里面必须由个左括号进行匹配，否则失败。

问题解题思路

其实这里就是很简单，放进栈里面的 ( 是为了等会遇到）进行匹配用的，有几个（，就必须有几个 )  进行匹配。而且这里先放进栈里面的左括号匹配思想与括号也是先匹配后遇到的左括号思想保持一致。也就是后进先出原则。

具体的代码设计

第一种方式是利用已经做好的动态库来做

我先把之前做的栈设计成一个动态库，这样我们直接可以调用栈里面的所有方法

关于怎么设计成动态库，可以参考我之前的文章linux之动态库与静态库。

好了话不多说，上代码。

先把之前做的栈设计成库，这里就用栈的顺序存储吧。

先把头放到我自己的库文件位置下面：

在把stack.c做成动态库放到我自己的库文件位置下面：

然后来看业务逻辑代码：

main.c

#include 
#include 
#include "stack.h"int main() {//用于接收我们需要判断的字符序列，稍微设计大一点避免溢出char str[100] = { '\0' };//创建一个栈t_seq_stack *stack = create_stack();while(scanf("%s",str) != EOF && stack != NULL) {//数组循环角标int index = 0;//如果出现前面前面都匹配成功，最后一个是‘)’,//那么就会造成一种，也会造成栈为空，因此给一个标识，出错，就是flag = 1//在结合栈是否为空就可以做出判断是否序列出错int errFlag = 0;while(str[index] != '\0') {//这里只要等于(左括号直接入栈if(str[index] == '(') {push_stack(stack,str[index]);} else if(str[index] == ')') {//当等于右括号的时候，判断栈是否有元素，//有出栈，没有出错让errFlag = 1,循环结束if(is_empty(stack)) {errFlag = 1;//说明出错了break;} else {pop_stack(stack);}}index++;}//当循环结束，只要栈里面还有数据，依旧是错的，说明左括号没与//右括号匹配成功，然后出栈。同时考虑边界情况，假如最后一个是)//前面都正常匹配出栈，数组循环完毕，但是也没有报错，栈为空//所以去匹配errFalgif(is_empty(stack) && errFlag == 0) printf("序列成功\n");else {printf("序列出错\n");}}return 0;
}

运行结果：

第二种方式现场设计一个栈来做

bug分析1：指针与整数不能==进行比较 

这里解决一下bug

第一种情况bug解决：

我想说一下

除了上面这种情况之外的情况，都是错误的

 下面直接上源代码

#include 
#include 
#include //定义数据元素
typedef char elem_type;//定义结点类型
typedef struct _link_stack link_stack;//定义具体的结点
struct _link_stack {elem_type data;link_stack *next;//单链表采用指针，链接结点表头信息也封装进来
};//last in  first  out
link_stack* create_stack() 
{link_stack *p_head = (link_stack*)malloc(sizeof(link_stack));if(p_head != NULL) {p_head->data = 0;p_head->next = NULL;}return p_head;
}//进栈
int push_stack(link_stack *p_head,elem_type data) 
{int res = (p_head != NULL);link_stack *p_node = NULL;if(res) {//给数据结点分配空间p_node = (link_stack*)malloc(sizeof(link_stack));if(p_node != NULL) {p_node->data = data;p_node->next = NULL;}}res = res && (p_node != NULL);if(res) {//进栈位置限定，头部插入p_node->next = p_head->next;p_head->next = p_node;	p_head->data++;}return res;
}	//出栈
elem_type pop_stack(link_stack *p_head)
{elem_type res = ' ';if(p_head != NULL && p_head->data != 0) {link_stack *p_node = p_head->next;//出栈就必须要断链p_head->next = p_node->next;p_head->data--;res = p_node->data;//返回删除结点的值		}return res;
}int main() 
{link_stack *p_head = create_stack();//定义一个字符串数组存放我们需要的数据char str[100] = {'\0'};while(scanf("%s",str) != EOF && (p_head != NULL)) {int len = strlen(str);int flag = 0;//遍历整个字符串数组for(int i = 0;i < len;i++) {if(str[i] == '(') {//等于左括号我们就要进栈push_stack(p_head,'(');}//遇到‘)’就要开始出栈if(str[i] == ')') {elem_type ch = pop_stack(p_head);if(ch == ' ') {flag = 1;break;//跳出遍历循环}}}//整体判定//如果栈为空和flag!=1,说明序列正确if(p_head->data == 0 && flag != 1) {printf("序列正确\n");} else {printf("序列出错\n");}}return 0;	
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！