//栈的应用-括号匹配
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSIZE 1024

//栈的结构体
struct SStack
{   
    //将数组头作为栈顶，因为如果作为栈顶的话来回出入元素时间开销比较大
    void *data[MAXSIZE]; //数组
    int size;
};

typedef void * sstack;

//初始化栈
sstack init_stack(){
    struct SStack * myStack = malloc(sizeof(struct SStack));
    if (myStack==NULL)
    {
        return NULL;
    }
    memset(myStack->data,0,sizeof(void *)*MAXSIZE); //给数组赋初值0
    myStack->size=0; //初试化栈的大小
    return myStack;
}

//入栈
void push_stack(sstack stack,void *data ){
    if (stack==NULL)
    {
        return;
    }
    if (data==NULL)
    {
        return;
    }
    struct SStack *myStack=stack; //把用户传过来的指针转换成栈结构体指针

    //判断栈满
    if (myStack->size==MAXSIZE)
    {
        return;
    }
    
    //入栈就是尾插数组
    myStack->data[myStack->size]=data;
    myStack->size++;
}

//出栈
void pop_stack(sstack stack){
    if (stack==NULL)
    {
        return;
    }
    struct SStack *myStack=stack;

    //判断栈空
    if (myStack->size==0)
    {
        return;
    }
    
    //出栈其实就是尾删
    myStack->data[myStack->size-1]=NULL;
    myStack->size--;
}
//判断栈是否为空
int isempty_stack(sstack stack){
    if (stack==NULL)
    {
        return -1; //返回-1代表栈空
    }
    struct SStack *myStack=stack;
    if (myStack->size==0)
    {
        return -1;
    }
    return 0;
}
//返回栈顶
void * top_stack(sstack stack)
{
	if (stack == NULL)
	{
		return NULL;
	}

	struct SStack * mystack = stack;

	if (mystack->size == 0)
	{
		return NULL;
	}
	return mystack->data[mystack->size - 1];
}
//销毁栈
void destroy_stack(sstack stack){
    if (stack==NULL)
    {
        return;
    }    
    free(stack);
    stack=NULL;
}

//发生错误时在控制台打印错误类型
void printWrong(char *str,char * wrongType,char *p){
    printf("%s:",str);
    printf("%s\n",wrongType);

    int num=p-str;
    for (int i = 0; i < num; i++)
    {
        printf(" ");
    }
    printf("|\n");
}









void test01(){
    char *str="5+5*(6)+9/3*((1+3)"; //一般字符串用双引号，字符用单引号
    char *p=str;

    //初始化一个栈
    sstack mystack=init_stack();

    while (*p!='\0')
    {   
        //如果左括号，入栈
        if (*p=='(')
        {
            push_stack(mystack,p);
        }
        
        //如果是右括号，栈中元素出栈
        if (*p==')')
        {
            if (!isempty_stack(mystack)) //如果栈不空，执行出栈
            {
                pop_stack(mystack);
            }
            else
            {
                //右括号没有匹配到对应的左括号
                //printf("%s:右括号没有匹配到对应的左括号\n",str);
                printWrong(str,"右括号没有匹配到对应的左括号",p);
                break;
            }
        }   
        p++;
    }
    //遍历完字符串后检查栈中是否还有元素
    if (isempty_stack(mystack))
    {
        printf("匹配成功！\n");

    }
    else
    {
        printWrong(str,"左括号没有匹配到对应的右括号",top_stack(mystack));//栈顶元素就是左括号的地址
    }
    destroy_stack(mystack);
    mystack=NULL; //!!不要忘了将栈指针置空以防止野指针的出现。
}


int main()
{   
    test01();
    return 0;
}