就近匹配
算法思路
在这里插入代码片 复制
总结
分文件编写
stack.h
#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
#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
#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("具体错误信息：%s\n", str);
printf("%s\n", 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 != '\0')
{
//判断是否为左括号，如果是放入栈中
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;
} 复制