就近匹配
在开发的过程中，我们常常遇到成对出现的符号，比如"(" 与")"，如果算式中仅仅出现其中一个，则说明算式错误。运用栈一数据结构模型，可以很好进行匹配。
算法思路：
1、从第一个字符开始扫描
2、遇见普通字符时忽略
3、当遇见左括号时压入栈中
4、当遇见右括号时弹出返回栈顶元素，并进行匹配
5、匹配成功，进入下一个字符
6、匹配失败，立即停止并进行报错
7、结束：
成功：所有字符匹配完毕，且栈为空
失败：匹配失败或者所有字符扫描完毕但是栈为非空
代码
"seqStack.h"文件
包含了栈的模型结构与常用接口声名
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 1024
//struct SStack
//{
// void * data[MAX]; //栈的数组
//
// int m_Size; //栈大小
//};
typedef void * SeqStack;
//初始化栈
SeqStack init_SeqStack();
//入栈
void push_SeqStack(SeqStack stack, void * data);
//出栈
void pop_SeqStack(SeqStack stack);
//返回栈顶
void * top_SeqStack(SeqStack stack);
//返回栈大小
int size_SeqStack(SeqStack stack);
//判断栈是否为空
int isEmpty_SeqStack(SeqStack stack);
//销毁栈
void destroy_SeqStack(SeqStack stack);
"seqStack.c"文件
包含了栈的各自接口的实现，看不懂不了解栈模型的欢迎查看本栏数据结构-线性栈
数据结构 -链表栈
#include "seqStack.h"
struct SStack
{
void * data[MAX]; //栈的数组
int m_Size; //栈大小
};
//初始化栈
SeqStack init_SeqStack()
{
struct SStack * myStack = malloc(sizeof(struct SStack));
if (myStack == NULL)
{
return NULL;
}
//初始化数组
memset(myStack->data, 0, sizeof(void *)* MAX);
//初始化栈大小
myStack->m_Size = 0;
return myStack;
}
//入栈
void push_SeqStack(SeqStack stack, void * data)
{
//入栈本质 --- 数组尾插
if (stack == NULL)
{
return;
}
if (data == NULL)
{
return;
}
struct SStack * mystack = stack;
if (mystack->m_Size == MAX)
{
return;
}
mystack->data[mystack->m_Size] = data;
mystack->m_Size++;
}
//出栈
void pop_SeqStack(SeqStack stack)
{
//出栈本质 --- 数组尾删
if (stack == NULL)
{
return;
}
struct SStack * mystack = stack;
if (mystack->m_Size == 0)
{
return;
}
mystack->data[mystack->m_Size - 1] = NULL;
mystack->m_Size--;
}
//返回栈顶
void * top_SeqStack(SeqStack stack)
{
if (stack == NULL)
{
return NULL;
}
struct SStack * mystack = stack;
if (mystack->m_Size == 0)
{
return NULL;
}
return mystack->data[mystack->m_Size - 1];
}
//返回栈大小
int size_SeqStack(SeqStack stack)
{
if (stack == NULL)
{
return -1;
}
struct SStack * mystack = stack;
return mystack->m_Size;
}
//判断栈是否为空
int isEmpty_SeqStack(SeqStack stack)
{
if (stack == NULL)
{
return -1;//返回-1代表真 空栈
}
struct SStack * mystack = stack;
if (mystack->m_Size == 0)
{
return 1;
}
return 0; //返回0 代表 不是空栈
}
//销毁栈
void destroy_SeqStack(SeqStack stack)
{
if (stack == NULL)
{
return;
}
free(stack);
stack = NULL;
}
具体实现代码
//
// Created by szw on 2021/9/23.
//
#include "Proximity matching of stacks.h"
#include <stdio.h>
#include "stdlib.h"
#include "string.h"
#include "seqStack.h"
//算法思路
/*
* 栈的应用案例
就近匹配
1、从第一个字符开始扫描
2、遇见普通字符时忽略
3、当遇见左括号时压入栈中
4、当遇见右括号时弹出返回栈顶元素，并进行匹配
5、匹配成功，进入下一个字符
6、匹配失败，立即停止并进行报错
7、结束：
成功：所有字符匹配完毕，且栈为空
失败：匹配失败或者所有字符扫描完毕但是栈为非空
*/
//判断左括号
int isLeft(char * p)
{
return '('== *p;
}
//判断右括号
int isRight(char * p)
{
return ')' ==* p;
}
//打印错误函数
void printError(char *str ,char *Msg ,char *pos)
{
printf("错误信息：%s\n",Msg);
printf("%s\n",str);
int mis_num = pos - str;//计算出错位置
for (int i = 0; i <mis_num ; ++i) {
printf(" ");
}
printf("^\n");
}
void test01(){
// char *str = "5+5*(6)+9/3*1)-(1+3(";
char *str = "5+5*(6)+9/3*1-(1+3(";
//定义一个指针指向字符串的首地址
char * p =str;
//初始化栈
SeqStack myStack = init_SeqStack();
//开始循环扫描操作
while (*p != '\0')
{
//判断如果是左括号,则进行入栈
if (isLeft(p)){
push_SeqStack(myStack,p);
}
//如果是右括号
if (isRight(p))
{
//情况1 如果是空栈报错
//情况2 不为空栈,出栈
if(size_SeqStack(myStack)>0)
{
//情况2
pop_SeqStack(myStack);
}
else
{
//情况1 立即停止报错
printError(str,"右括号无法匹配左括号",p);
break;
}
}
p++;
}
//左括号没有匹配到右括号的情况
//如果没有匹配到，栈一定不为空
while (size_SeqStack(myStack)>0)
{
printError(str,"左括号没有匹配到右括号", top_SeqStack(myStack));
pop_SeqStack(myStack);
}
//销毁栈
destroy_SeqStack(myStack);
}
int main() {
test01();
return 0;
}
运行图例
