栈的链式存储设计与实现(C语言版本)

偏执的太偏执、 2022-05-24 01:55 185阅读 0赞

# 栈的链式存储设计与实现 #

## 1、基本概念    ##

![70][]

//LinkList.h
 #ifndef _LINKLIST_H_
 #define _LINKLIST_H_
 
 //单链表的存储结构
 //结点中包含后继结点地址的指针域组成-可以理解为指向下一个结构体(结点)
 //(这里不包含数据域,是实现了 链表的api(链表的算法) 和 具体的数据分离)
 typedef struct _tag_LinkListNode
 {
 	struct _tag_LinkListNode *next;
 }LinkListNode;
 
 //为void 再重新多取一个名字，LinkList等价于void
 //typedef + 已有的数据类型+新的数据类型(自己取的新名字)
 typedef void LinkList;
 
 //创建并且返回一个空的链式的线性表 
 LinkList* LinkList_Create();
 
 //销毁一个链式的线性表list 
 void LinkList_Destroy(LinkList* list);
 
 //将一个链式线性表list中的所有元素清空, 链式线性表回到创建时的初始状态 
 void LinkList_Clear(LinkList* list);
 
 //返回一个链式线性表list中的所有元素个数
 int LinkList_Length(LinkList* list);
 
 //向一个链式线性表list的pos位置处插入新元素node 
 int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);
 
 //获取一个链式线性表list的pos位置处的元素 
 LinkListNode* LinkList_Get(LinkList* list, int pos);
 
 //删除一个链式线性表list的pos位置处的元素 返回值为被删除的元素，NULL表示删除失败
 LinkListNode* LinkList_Delete(LinkList* list, int pos);
 
 #endif
 
 
 //LinkStack.h
 #ifndef _LINKSTACK_H_
 #define _LINKSTACK_H_
 
 
 //栈的链式存储设计
 //这句话意思：
 //C语言里面的typedef, 字面上理解就是类型的定义, 也就是给内置的或自定义的数据类型重新命名
 //LinkStack* LinkStack_Create(); //这样一看返回值就知道是返回值是栈
 //void LinkStack_Destroy(LinkStack *stack); //如果这样，使用者一看只知道是返回指针，不知道具体的，可读性很差
 //所以才会给void起别名，封装好的底层函数，提供给使用者使用，使用者会给容易懂
 typedef void LinkStack;
 
 
 
 //创建链式栈相当于创建一个链式线性表
 LinkStack* LinkStack_Create();
 
 //销毁链式栈涉及到链表节点的生命周期管理。首先，清空栈中所有元素，然后再销毁栈
 void LinkStack_Destroy(LinkStack *stack);
 
 //清空一个栈 相当于 清空一个线性表
 //清空栈的时候 涉及到 栈元素生命周期的管理
 //清空链式栈：当栈的长度不为0时，一直Pop出栈中的元素。直到栈中不存在任何元素
 
 //所有入栈的结点都是malloc
 //若要清空栈 把栈中元素弹出 并且释放结点内存
 void LinkStack_Clear(LinkStack *stack);
 
 //向栈中压入元素相当于链式表的头插法
 // void *item栈的业务节点===>链表的业务节点
 int LinkStack_Push(LinkStack* stack, void* item);
 
 //出栈
 //栈中弹出元素 相当于 从线性表的头部删除元素
 //把线性表的业务结点 转化成 栈的业务结点
 void* LinkStack_Pop(LinkStack *stack);
 
 //获取栈顶元素 相当于 获取线性表的0号位置
 void* LinkStack_Top(LinkStack *stack);
 
 //求栈的大小 相当于 求线性表的len
 int LinkStack_Size(LinkStack *stack);
 
 #endif//_LINKSTACK_H_
 
 
 //LinkList.c
 #include <stdlib.h> 
 #include <string.h> 
 #include <stdio.h> 
 #include "LinkList.h"
 
 //定义头结点 链式存储头结点：表示链表中第一个节点,包含指向第一个数据元素的指针以及链表自身的一些信息
 //这样能把所有结点串起来
 typedef struct _tag_LinkList
 {
 	LinkListNode header;//要有个头指针---指向头结点的指针
 	int length;//底层库中加了多少个结点
 }TLinkList;
 
 
 
 //创建并且返回一个空的链式的线性表 
 LinkList* LinkList_Create()
 {
 	//1 申请动态内存空间
 	TLinkList *tmp = NULL;
 	tmp = (TLinkList *)malloc(sizeof(TLinkList));
 	if (NULL == tmp)
 	{
 		printf("func err malloc\n");
 		return NULL;
 	}
 	//2 让开辟的内存 完成链式线性表初始化 
 	memset(tmp,0,sizeof(TLinkList));
 
 	//3 链表的初始化
 	tmp->header.next = NULL;
 	tmp->length = 0;
 
 	return tmp;
 }
 
 //销毁一个链式的线性表list 
 //链表节点的生命周期由调用者负责，也就是main()函数负责，链表的销毁只需释放头结点空间
 void LinkList_Destroy(LinkList* list)
 {
 	//1 缓存下来 进行操作
 	TLinkList *tmp = NULL;
 	tmp = (TLinkList *)list;
 	if (NULL == list)
 	{
 		printf("func err LinkList_Destroy\n");
 	}
 	//2 释放头结点空间 
 	if (tmp!=NULL)
 	{
 		free(tmp);
 	}
 }
 
 //将一个链式线性表list中的所有元素清空, 链式线性表回到创建时的初始状态 
 //链表的清空只是将头结点的指针域指向NULL,以及链表的长度length赋值为0 
 void LinkList_Clear(LinkList* list)
 {
 	//1 缓存下来 进行操作
 	TLinkList *tmp = NULL;
 	tmp = (TLinkList *)list;
 	if (NULL == list)
 	{
 		printf("func err LinkList_Clear\n");
 	}
 	//2 清空链表
 	tmp->header.next = NULL;
 	tmp->length = 0;
 }
 
 //返回一个链式线性表list中的所有元素个数
 int LinkList_Length(LinkList* list)
 {
 	int ret = 0;
 	//1 缓存下来 进行操作
 	TLinkList *tmp = NULL;
 	tmp = (TLinkList *)list;
 	if (NULL == list)
 	{
 		ret = -1;
 		printf("func err LinkList_Length:%d\n",ret);
 		return ret;
 	}
 	ret = tmp->length;
 	return ret;
 }
 
 //向一个链式线性表list的pos位置处插入新元素node 
 int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
 {
 	int ret = 0;
 	//1 缓存下来 进行操作
 	TLinkList *tmp = NULL;
 	tmp = (TLinkList *)list;
 	//辅助指针 用来遍历当前指针位置
 	LinkListNode *pCur = NULL;
 	if (NULL == list || NULL == node || pos < 0)
 	{
 		ret = -1;
 		printf("func err (NULL == list || NULL == node || pos < 0):%d\n", ret);
 		return ret;
 	}
 	//1 当前指针 初始化 指向 头结点
 	pCur = &(tmp->header);
 	//2 进行遍历 找到插入位置
 	for (int i = 0; i < pos; i++)
 	{
 		pCur = pCur->next;
 	}
 	//3 进行插入操作
 	node->next = pCur->next;//1
 	pCur->next = node;
 
 	//4 链表长度++
 	tmp->length++;
 
 	return ret;
 }
 
 //获取一个链式线性表list的pos位置处的元素 
 LinkListNode* LinkList_Get(LinkList* list, int pos)
 {
 	int ret = 0;
 	//1 缓存下来 进行操作
 	TLinkList *tmp = NULL;
 	tmp = (TLinkList *)list;
 	//辅助指针 用来遍历当前指针位置
 	LinkListNode *pCur = NULL;
 	if (NULL == list || pos < 0)
 	{
 		ret = -1;
 		printf("func err (NULL == list|| pos < 0):%d\n", ret);
 		return NULL;
 	}
 	//1 当前指针 初始化 指向 头结点
 	pCur = &(tmp->header);
 	//2 进行遍历 找到pos位置
 	for (int i = 0; i < pos; i++)
 	{
 		pCur = pCur->next;
 	}
 
 	return pCur->next;
 }
 
 //删除一个链式线性表list的pos位置处的元素 返回值为被删除的元素，NULL表示删除失败
 LinkListNode* LinkList_Delete(LinkList* list, int pos)
 {
 	int ret = 0;
 	//1 缓存下来 进行操作
 	TLinkList *tmp = NULL;
 	tmp = (TLinkList *)list;
 	//辅助指针 用来缓存要删除的结点
 	LinkListNode *Deletemp = NULL;
 	//辅助指针 用来遍历当前指针位置
 	LinkListNode *pCur = NULL;
 	if (NULL == list || pos < 0)
 	{
 		ret = -1;
 		printf("func err (NULL == list|| pos < 0):%d\n", ret);
 		return NULL;
 	}
 	//1 当前指针 初始化 指向 头结点
 	pCur = &(tmp->header);
 	//2 进行遍历 找到要删除的pos位置
 	for (int i = 0; i < pos; i++)
 	{
 		pCur = pCur->next;
 	}
 	//3 缓存要删除的元素
 	Deletemp = pCur->next;
 	//4 进行删除操作
 	pCur->next = Deletemp->next;
 	//5 链表长度--
 	tmp->length--;
 
 	return Deletemp;
 }
 
 
 //LinkStack.c
 #include <stdlib.h> 
 #include <string.h> 
 #include <stdio.h> 
 #include "LinkList.h"
 #include "LinkStack.h"
 
 //链式栈的存储节点定义
 //包含链表的指针域节点和栈的业务结点
 //定义一个抽象的栈节点模型 
 //也就是用链式链表的抽象模型来存储item 以便插入元素
 typedef struct _tag_LinkstackNode
 {
 	LinkListNode node;	 //包含链表的结点
 	void* item;			//栈的业务结点
 
 }TLinkStack;
 
 //创建链式栈相当于创建一个链式线性表
 LinkStack* LinkStack_Create()
 {
 	return LinkList_Create();
 }
 
 //销毁链式栈涉及到链表节点的生命周期管理。首先，清空栈中所有元素，然后再销毁栈
 void LinkStack_Destroy(LinkStack *stack)
 {
 	//1 首先要清除所有元素,释放所有结点
 	LinkList_Clear(stack);
 	//2 再销毁栈
 	LinkList_Destroy(stack);
 }
 
 //清空一个栈 相当于 清空一个线性表
 //清空栈的时候 涉及到 栈元素生命周期的管理
 //清空链式栈：当栈的长度不为0时，一直Pop出栈中的元素。直到栈中不存在任何元素
 //所有入栈的结点都是malloc
 //若要清空栈 把栈中元素弹出 并且释放结点内存
 void LinkStack_Clear(LinkStack *stack)
 {
 	if (NULL == stack)
 	{
 		return;
 	}
 	while (LinkList_Length(stack) > 0)
 	{
 		LinkStack_Pop(stack);//在这个函数中释放结点的内存
 	}
 }
 
 //向栈中压入元素相当于链式表的头插法
 // void *item栈的业务节点===>链表的业务节点
 int LinkStack_Push(LinkStack* stack, void* item)
 {
 	int ret = 0;
 	if (NULL == stack || NULL == item)
 	{
 		ret = -1;
 		printf("LinkStack_Push (NULL == stack || NULL == item) Err:%d\n", ret);
 		return ret;
 	}
 	//1 先定义一个临时的TLinkStack指针变量tmp
 	TLinkStack *tmp = NULL;
 	//现在是想存储temp的 
 	//为了防止函数结束时tmp被析构必须分配内存 
 	tmp = (TLinkStack *)malloc(sizeof(TLinkStack));
 	//异常处理 
 	if (NULL == tmp)
 	{
 		ret = -2;
 		printf("LinkStack_Push Tmp malloc Err:%d\n",ret);
 		return ret;
 	}
 	//初始化
 	memset(tmp, 0, sizeof(TLinkStack));
 	//将item 也就是所需要存储的信息传递给tmp->item 
 	tmp->item = item;
 	//现在可以直接插入 
 	ret = LinkList_Insert(stack,(LinkListNode *)tmp,0);
 	if (ret!=0)
 	{
 		ret = -3;
 		printf("func LinkList_Insert tmp Err:%d\n",ret);
 		//为了防止内存插入失败而导致的内存泄漏
 		if (tmp!=NULL)
 		{
 			free(tmp);
 		}
 		return ret;
 	}
 	return ret;
 }
 //出栈
 //栈中弹出元素 相当于 从线性表的头部删除元素
 //把线性表的业务结点 转化成 栈的业务结点
 void* LinkStack_Pop(LinkStack *stack)
 {
 	if (NULL == stack)
 	{
 		printf("LinkStack_Pop(NULL == stack) Err\n");
 		return NULL;
 	}
 	//1 定义一个中间缓存
 	void* item = NULL;//栈的业务结点
 	TLinkStack *tmp = NULL;
 	//2 栈中弹出元素 相当于 从链表的头部删除元素
 	tmp = (TLinkStack *)LinkList_Delete(stack,0);
 	if (NULL == tmp)
 	{
 		printf("LinkList_Delete(NULL == tmp) Err\n");
 		return NULL;
 	}
 	//3 将tmp->item也就是所需要存储的信息传递给item
 	item = tmp->item;
 	//因为LinkList_Insert的时候，分配了内存， 所以LinkList_Delete释放内存
 	//栈中每一个结点都是malloc进去的,所以出来的时候,得把这个内存空间得释放掉
 	free(tmp);
 	return item;
 }
 
 //获取栈顶元素 相当于 获取线性表的0号位置
 void* LinkStack_Top(LinkStack *stack)
 {
 	if (NULL == stack)
 	{
 		printf("LinkStack_Top(NULL == stack) Err\n");
 		return NULL;
 	}
 	TLinkStack *tmp = NULL;
 	tmp = (TLinkStack *)LinkList_Get(stack,0);
 	if (NULL == tmp)
 	{
 		printf("LinkList_Get(NULL == tmp) Err\n");
 		return NULL;
 	}
 	return tmp->item;
 }
 //求栈的大小 相当于 求线性表的Length
 int LinkStack_Size(LinkStack *stack)
 {
 	return LinkList_Length(stack);
 }
 
 
 //栈的链式存储测试框架
 #include "LinkStack.h" 
 #include "LinkList.h" 
 #include <stdio.h> 
 #include <stdlib.h> 
 
 int main()
 {
 	LinkStack *stack = NULL;
 	int a[5];
 	int ret = 0;
 	stack = LinkStack_Create();
 	if (NULL == stack)
 	{
 		ret = -1;
 		printf("func err LinkStack_Create():%d\n", ret);
 		return ret;
 	}
 	//压栈
 	for (int i = 0; i < 5; i++)
 	{
 		a[i] = i + 1;
 		LinkStack_Push(stack, &a[i]);
 	}
 	//显示大小和栈顶元素
 	printf("Size:%d\n", LinkStack_Size(stack));
 
 	printf("Top:%d\n", *((int *)LinkStack_Top(stack)));
 
 	//出栈
 	while (LinkStack_Size(stack) > 0)
 	{
 		int tmp = *((int *)LinkStack_Pop(stack));
 
 		printf("%d ", tmp);
 	}
 	printf("\n===================我是分界线=============\n");
 	LinkList_Destroy(stack);
 	system("pause");
 	return ret;
 }

![70 1][]

<table> 
 <tbody> 
 <tr> 
 <td>应用2：中缀 后缀</td> 
 </tr> 
 <tr> 
 <td>计算机的本质工作就是做数学运算，那计算机可以读入字符串 “9 + (3 - 1) * 5 + 8 / 2”并计算值吗？</td> 
 </tr> 
 <tr> 
 <td>后缀表达式&nbsp; ==？符合计算机运算 波兰科学家在20世纪50年代提出了一种将运算符放在数字后面的后缀表达式对应的， 我们习惯的数学表达式叫做中缀表达式===》符合人类思考习惯 &nbsp;</td> 
 </tr> 
 <tr> 
 <td>实例： 5 + 4=&gt; 5 4 + 1 + 2 * 3 =&gt; 1 2 3 * + 8 + ( 3 – 1 ) * 5 =&gt; 8 3 1 – 5 * +&nbsp; </td> 
 </tr> 
 <tr> 
 <td>中缀表达式符合人类的阅读和思维习惯 后缀表达式符合计算机的“运算习惯” 如何将中缀表达式转换成后缀表达式？</td> 
 </tr> 
 <tr> 
 <td>中缀转后缀算法：</td> 
 </tr> 
 <tr> 
 <td>遍历中缀表达式中的数字和符号 对于数字：直接输出 对于符号： 左括号：进栈&nbsp; 运算符号：与栈顶符号进行优先级比较 若栈顶符号优先级低：此符合进栈&nbsp; （默认栈顶若是左括号，左括号优先级最低） 若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈 右括号：将栈顶符号弹出并输出，直到匹配左括号 遍历结束：将栈中的所有符号弹出并输出 中缀转后缀</td> 
 </tr> 
 </tbody> 
</table>

#include "LinkStack.h"
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 /*中缀转后缀的算法
 遍历表达式中的数字和符号
 对于数字：直接输出
 对于符号：
 左括号：进栈
 运算符号：与栈顶元素进行优先级比较
 若栈顶符号优先级低：此符号进栈（默认：栈顶若是左括号，左括号优先级最低）
 若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
 右括号：将栈顶符号弹出并输出
 遍历结束：将栈中所有符号弹出并输出
 中缀转后缀
 */
 /*计算表达式结果：
 
 */
 int isNumber(char c)//数字
 {
 	return ('0' <= c) && (c <= '9');
 }
 
 int isOperator(char c)//符号
 {
 	return (c == '+') || (c == '-') || (c == '*') || (c == '/');
 }
 
 //左括号
 int isLeft(char c)
 {
 	return (c == '(');
 }
 
 //右括号
 int isRight(char c)
 {
 	return (c == ')');
 }
 //优先级比较
 int priority(char c)
 {
 	int ret = 0;
 	if ((c == '+')||(c == '-'))
 	{
 		ret = 1;
 	}
 	if ((c == '*')||(c == '/'))
 	{
 		ret = 2;
 	}
 	return ret;
 }
 
 void output(char c)
 {
 	if (c != '\0')
 	{
 		printf("%c",c);
 	}
 }
 
 int transform(const char *exp)
 {
 	int i = 0;
 	//1 建立一个空栈
 	LinkStack *stack = LinkStack_Create();
 
 	//2 开始遍历表达式中的符号
 	//对于符号：
 	//左括号：进栈
 	//运算符号：与栈顶元素进行优先级比较
 	//若栈顶符号优先级低：此符号进栈（默认：栈顶若是左括号，左括号优先级最低）
 	//若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
 	//右括号：将栈顶符号弹出并输出
 	//遍历结束：将栈中所有符号弹出并输出
 	while (exp[i] != '\0')
 	{
 		if (isNumber(exp[i]))//1 遍历表达式中的数字和符号 对于数字：直接输出 
 		{
 			output(exp[i]);
 		}
 		else if (isOperator(exp[i]))
 		{
 			//运算符号：与栈顶元素进行优先级比较
 			//若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
 			while (LinkStack_Size(stack) > 0 && priority(exp[i]) <= priority(LinkStack_Top(stack)))
 			{
 				output((char)(int)LinkStack_Pop(stack));
 			}
 			//运算符的优先级高 栈顶符号优先级低 此符号进栈（默认：栈顶若是左括号，左括号优先级最低）
 			LinkStack_Push(stack,(void *)(int)exp[i]);
 		}
 		else if (isLeft(exp[i]))//左括号：进栈
 		{
 			LinkStack_Push(stack, (void*)(int)exp[i]);
 		}
 		else if (isRight(exp[i]))//右括号：将栈顶符号弹出并输出 
 		{
 			//char c = '\0';
 			//如果遇到一个右括号，那么就将栈元素弹出 将符号写出直到遇到一个对应的左括号，但是这个左括号只被弹出 并不输出
 			//1 当输入字符是右括号,栈顶元素不为左括号时候，将栈元素弹出 并输出
 			while (!isLeft((char)(int)LinkStack_Top(stack)))
 			{
 				output((char)(int)LinkStack_Pop(stack));
 			}
 			//2 当遇到右括号 栈顶元素为左括号时候，将栈顶元素（弹出，不输
 			LinkStack_Pop(stack);
 		}
 		else
 		{
 			printf("Invalid expression!");
 			break;
 		}
 		i++;
 	}
 	//遍历结束：将栈中所有符号弹出并输出
 	while ((LinkStack_Size(stack) > 0) && (exp[i] == '\0'))
 	{
 		output((char)(int)LinkStack_Pop(stack));
 	}
 	LinkStack_Destroy(stack);
 }
 
 
 int main()
 {
 
 	transform("8+(3-1)*5");
 
 	printf("\n");
 	return 0;
 }

![70 2][]

//后缀表达式的计算
 /*
 基础知识：
 但是，平时使用的时候建议加上#include<string.h>（尤其在以下情况下）
 1、使用string类型
 2、使用cin、cout语句来输入输出string类型变量（注意，同时还需要 #include<iostream>）
 3、使用memset()、strlen()、strcpy()等函数时
 
 只要用到stdio里面定义的库函数，就要包含它
 这些库函数包括scanf，printf等等
 
 是引用stdlib.h头文件，即#include <stdlib.h>。这里的.h是不可缺少的。
 stdlib.h中，包含了C语言的一些常用库函数。如
 动态内存相关的malloc, realloc,zalloc,calloc,free等。
 随机数相关的rand,srand等。
 系统相关的system, getenv,setenv等。
 字符串转数值函数，atoi, atof,strtoul等。
 如果在代码中，调用了这个头文件中的函数或者宏定义，则需要引用该头文件。
 */
 #include "LinkStack.h"
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 /*
 遍历后缀表达式中的数字和符号
 对于数字：进栈
 对于符号：
 从栈中弹出符号的右操作数
 接着从栈中弹出符号的左操作数
 同时根据遇到的符号进行运算
 将运算结果压入栈中
 遍历结束后：栈中的唯一数字作为计算结果
 
 */
 //判断字符是否为数字
 int isNumber(char c)
 {
 	return (c >= '0') && (c <= '9');
 }
 
 //判断是否为符号
 int isOperator(char c)
 {
 	return (c == '+') || (c == '-') || (c == '*') || (c == '/');
 }
 
 //char ==>转成int
 int value(char c)
 {
 	return (c - '0');
 }
 
 int express(int left, int right, char op)
 {
 	int ret = 0;
 	switch (op)
 	{
 	case '+':
 		ret = left + right;
 		break;
 	case '-':
 		ret = left- right;
 		break;
 	case '*':
 		ret = left * right;
 		break;
 	case '/':
 		ret = left / right;
 		break;
 	default:
 		break;
 	}
 	return ret;
 }
 int compute(const char *exp)
 {
 	int ret = 0;
 	int i = 0;
 	//1 建立一个空栈
 	LinkStack *stack = LinkStack_Create();
 	if (NULL == stack)
 	{
 		return -1;
 	}
 	//遍历后缀表达式中的数字和符号
 	while (exp[i] != '\0')
 	{
 		// 对于数字：直接进栈
 		if (isNumber(exp[i]))
 		{
 			//把字符中数字转成int,来入栈
 			LinkStack_Push(stack,(void *)value(exp[i]));
 		}
 		//对于符号：
 		//从栈中弹出右操作数
 		//从栈中弹出左操作数
 		//根据符号进行运算
 		//将运算结果压入栈中
 		else if (isOperator(exp[i]))
 		{
 			//从栈中弹出右操作数
 			int right = (int)LinkStack_Pop(stack);
 			//从栈中弹出左操作数
 			int left = (int)LinkStack_Pop(stack);
 			//根据符号进行运算
 			int result = express(left,right,exp[i]);
 			//将运算结果压入栈中
 			LinkStack_Push(stack,(void *)result);
 		}
 		else{
 			printf("Invalid char expression!");
 			break;
 		}
 		i++;
 	}
 	//遍历结束：栈中的唯一数字作为计算最终结果
 	if ((LinkStack_Size(stack) == 1) && (exp[i] == '\0'))
 	{
 		ret = (int)LinkStack_Pop(stack);
 	}
 	else
 	{
 		printf("Invalid expression!\t");
 	}
 
 	LinkStack_Destroy(stack);
 
 	return ret;
 }
 int main()
 {
 	int final = compute("831-5*+");
 	printf("8 +(3 - 1) * 5 = %d\t",final);
 
 	system("pause");
 	return 0;
 }

![70 3][]

/*
 从第一个字符开始扫描，当遇见普通字符时忽略，
 当遇见左符号时压入栈中，当遇见右符号时从栈中弹出栈顶符号，
 并进行匹配，匹配成功：继续进入下一个字符
 匹配失败：立即停止，报告错误
 结束：成功，所有字符扫描完毕，且栈为空
 失败：匹配失败或所有字符扫描完毕但栈非空
 */
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include "LinkStack.h"
 
 //判别左符号
 int isLeft(char c)
 {
 	int ret = 0;
 	switch (c)
 	{
 	case '<':
 	case '/':
 	case '(':
 	case '[':
 	case '{':
 		ret = 1;
 		break;
 	default:
 		ret = 0;
 		break;
 	}
 	return ret;
 }
 
 //判别右符号
 int isRight(char c)
 {
 	int ret = 0;
 	switch (c)
 	{
 	case '>':
 	case ']':
 	case '}':
 	case ')':
 		ret = 1;
 		break;
 	default:
 		ret = 0;
 		break;
 	}
 	return ret;
 }
 //进行匹配判断
 int match(char left, char right)
 {
 	int ret = 0;
 	switch (left)
 	{
 	case '<':
 		ret = (right == '>');
 		break;
 	case '(':
 		ret = (right == ')');
 		break;
 	case '[':
 		ret = (right == ']');
 		break;
 	case '{':
 		ret = (right == '}');
 		break;
 	default:
 		ret = 0;
 		break;
 	}
 	return ret;
 }
 int scanner(const char *exp)
 {
 	int ret = 0;
 	int i = 0;
 	//1.建立一个空栈 需要一个先进后出的场合 来做就近匹配
 	LinkStack *stack = LinkStack_Create();
 	if (NULL == stack)
 	{
 		ret = -1;
 		printf("func err LinkStack_Create()\n");
 		return ret;
 	}
 	//2.从第一个字符开始扫描，当遇见普通字符时忽略 进行i++,进入下一次扫描
 	while (exp[i] != '\0')
 	{
 		//3.当遇见左符号时压入栈中
 		if (isLeft(exp[i]))
 		{
 			//LinkStack_Push(stack,(void *)(int)exp[i]);
 			//进栈的时候可以存入的是实际数据在内存中的地址
 			//也可以将实际数据直接转换成int型的数据当作地址存入结构体的item成员 
 			//int LinkStack_Push(LinkStack* stack, void* item)
 			//LinkStack_Push(stack,(void *)exp[i]);
 			LinkStack_Push(stack, (void *)(exp + i));
 		}
 		//4.当遇见右符号时从栈中弹出栈顶符号
 		if (isRight(exp[i]))
 		{
 			char *c = (char *)LinkStack_Pop(stack);//遇到右符号，出栈一个符号，与之进行匹配
 			//5.并进行匹配，匹配成功：继续进入下一个字符
 			if ((c == NULL) || !match(*c, exp[i]))//匹配成功，返回来match(*c, code[i])为0，c不为NULL,则错误，不执行下面语句，继续下一轮扫描
 			{
 				//6.匹配失败：立即停止，报告错误
 				printf("%c does not match %c\n", *c, exp[i]);
 				ret = 0;
 
 				break;
 			}
 		}
 		i++;
 	}
 	//7.结束：成功，所有字符扫描完毕，且栈为空
 	if (LinkStack_Size(stack) == 0 && (exp[i] == '\0'))
 	{
 		printf("Succeed!\n");
 		ret = 1;
 	}
 	//8.失败：匹配失败或所有字符扫描完毕但栈非空
 	else
 	{
 		printf("Invalid code!\n");
 	}
 	LinkStack_Destroy(stack);
 	return ret;
 }
 int main()
 {
 	const char * code = "{[4](*p)[4]";
 	scanner(code);
 	system("pause");
 	return 0;
 }

<table> 
 <tbody> 
 <tr> 
 <td>应用1：就近匹配</td> 
 </tr> 
 <tr> 
 <td>几乎所有的编译器都具有检测括号是否匹配的能力 如何实现编译器中的符号成对检测？ #include &lt;stdio.h&gt; int main() { int a[4][4]; int (*p)[4]; p = a[0]; return 0; &nbsp;</td> 
 </tr> 
 <tr> 
 <td>算法思路 从第一个字符开始扫描 当遇见普通字符时忽略，当遇见左符号时压入栈中 当遇见右符号时从栈中弹出栈顶符号，并进行匹配 匹配成功：继续读入下一个字符 匹配失败：立即停止，并报错 结束： 成功: 所有字符扫描完毕，且栈为空 失败：匹配失败或所有字符扫描完毕但栈非空</td> 
 </tr> 
 <tr> 
 <td>当需要检测成对出现但又互不相邻的事物时 可以使用栈“后进先出”的特性 栈非常适合于需要“就近匹配”的场合</td> 
 </tr> 
 </tbody> 
</table>

[70]: /images/20220524/3d1691ec974545a3ad01b685d0312b89.png
[70 1]: /images/20220524/d7cb6b7fe671441c91c3cec03ee08338.png
[70 2]: /images/20220524/be62a8ad099e40f886a3fd67f901d296.png
[70 3]: /images/20220524/939db660920b4191b4e37e6c678f17d7.png