栈的应用案例---就近匹配

就近匹配

算法思路

代码语言：javascript复制

在这里插入代码片

总结

分文件编写

stack.h

代码语言：javascript复制

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<string.h>
#define MAX 1024
//栈:注意和动态数组的区别：
//动态数组这里用的指针是二级指针因为数组的大小无法提前确定，并且用户数组类型无法确定，要用void*一级指针来接收
//所以要在堆区动态开辟数组存放void*类型数据要用二级指针来接收

//这里的栈已经知道数组的最大长度，因此不需要再用在堆区再次开辟一块内存来用二级指针指向
struct sStack
{
	//因为不确定用户数据类型，所以用void*指针来接收用户输入的数据地址
	//指针数组----里面存放的是地址或者指针
	void* data[MAX];
	int size;
};
//隐藏数据，不让用户能够得到操作结构体的接口
//类似c  类中的private属性
typedef void* seqStack;
//初始化栈----返回栈的结构体,为了隐藏数据用万能指针作为返回值
seqStack init_stack();
//入栈
void push_stack(seqStack stack, void* data);
//出栈:尾删
void pop_stack(seqStack stack);
//返回栈顶元素
seqStack top_stack(seqStack stack);
//返回栈的大小
int size_stack(seqStack stack);
//判断栈是否为空
bool empty_stack(seqStack stack);
//销毁栈
void destroy_stack(seqStack stack);

stack.cpp

代码语言：javascript复制

#include"stack.h"
//初始化栈----返回栈的结构体,为了隐藏数据用万能指针作为返回值
seqStack init_stack()
{
	//为栈结构体开辟空间
	sStack* stack = (sStack*)malloc(sizeof(sStack));
	if (stack == NULL)
	{
		return NULL;
	}
	//初始化数组--清空数组，一开数组里面会有随机值
	memset(stack->data, NULL, sizeof(void*) * MAX);
	//长度初始哈
	stack->size = 0;
	//返回栈的结构体
	return stack;
}
//入栈
void push_stack(seqStack stack, void* data)
{
	//尾插
	if (stack == NULL)
		return;
	if (data == NULL)
		return;
	//把传入的void*数据转为sStack*数据类型
	sStack* mystack = (sStack*)stack;
	//判断当前栈内元素是否超过最大容量
	if (mystack->size == MAX)
	{
		return;
	}
	//下面从数组尾部开始插入
	mystack->data[mystack->size] = data;
	//长度加一
	mystack->size  ;
}
//出栈:尾删
void pop_stack(seqStack stack)
{
	if (stack == NULL)
		return;
	sStack* mystack = (sStack*)stack;
	if (mystack->size == 0)
		return;
	//尾删:将数组中最后一个元素置空---把指针置空
	//这里指针置空后相当于断掉了指针指向用户的数据，相当于做了删除操作
	//因为我们这里不清楚用户的数据是开辟在堆区还是栈区
	mystack->data[mystack->size - 1] = NULL;
	//更新长度
	mystack->size--;
}
//返回栈顶元素
seqStack top_stack(seqStack stack)
{
	if (stack == NULL)
		return NULL;
	sStack* mystack = (sStack*)stack;
	if (mystack->size == 0)
		return NULL;
	return mystack->data[mystack->size - 1];
}
//返回栈的大小
int size_stack(seqStack stack)
{
	if (stack == NULL)
		return -1;
	sStack* mystack = (sStack*)stack;
	return mystack->size;
}
//判断栈是否为空
bool empty_stack(seqStack stack)
{
	if (stack == NULL)
		return true;//表示为空
	sStack* mystack = (sStack*)stack;
	if (mystack->size == 0)
		return -1;//为空
	return 0;//不为空
}
//销毁栈
void destroy_stack(seqStack stack)
{
	if (stack == NULL)
		return;
	//只有栈结构体分配到堆区
	free(stack);
}

main.cpp

代码语言：javascript复制

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include"stack.h"
bool isLeft(char ch)
{
	if (ch == '(')
	{
		return true;
	}
	return false;
}
bool isRight(char ch)
{
	if (ch == ')')
	{
		return true;
	}
	return false;
}
void printError(const char* p, const char* str,char* p1)
{
	printf("具体错误信息：%sn", str);
	printf("%sn", p);
	//打印空格数量:两个指针相减，用int类型来接收可以得到相差的元素个数
	int num = p1 - p;
	for (int i = 0; i < num; i  )
		printf(" ");
	printf("|n");
}
int main()
{
	const char* p = "5 5*(6) 9/3*1-(1 3(";
	char* p1 = (char*)p;
	seqStack stack = init_stack();
	while (*p1 != '')
	{
		//判断是否为左括号，如果是放入栈中
		if (isLeft(*p1)) 
		{
			//入栈:void*无法接收const char*,要用const void*才可以
			push_stack(stack, p1);
		}
		//如果是右括号
		if (isRight(*p1))
		{
			//栈中有元素就---出栈
			if (size_stack(stack) > 0)
			{
				pop_stack(stack);
			}
			else
			{
				//右括号没有匹配到对应的左括号
				printError(p, "右括号没有匹配到对应的左括号",p1);
				break;
			}
		}
		p1  ;
	}
	//遍历结束，判断是否有左括号没有匹配到右括号
	while (1)
	{
		if (size_stack(stack) > 0)
		{
			//栈顶就是错误位置的地址:因为返回栈顶，是返回栈顶void*存储用户输入的数据的地址
			printError(p, "左括号没有匹配到右括号", (char*)top_stack(stack));
			//出栈
			pop_stack(stack);
		}
		else 
		{
			break;
		}
	}
	//销毁栈
	destroy_stack(stack);
	stack = NULL;
	return 0;
}

stack 算法

0 人点赞