栈的应用（括号匹配问题、中缀表达式转为后缀表达式、求栈内最小值 、共享栈）

• 一、括号匹配问题

• 说明：遇到左括号时，入栈；遇到右括号时，与栈顶元素匹配。

#include<stdio.h>
#include<stdlib.h>
#include"stack.h"
#include<assert.h>

#define INIT_SIZE 10
typedef struct stack
{
	int* base;
	int top;
	int stacksize;
}Stack, * PStack;

//初始化
void InitStack(PStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return;
	}
	ps->base = (int*)malloc(INIT_SIZE * sizeof(int));
	assert(ps->base != NULL);

	ps->top = 0;//相当于空表
	ps->stacksize = INIT_SIZE;

}

//判满
static bool IsFull(PStack ps)//没有满的概念，一满就扩容
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}
	return ps->top == ps->stacksize;

}

//扩容
static void Inc(PStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return;
	}
	ps->stacksize *= 2;//常用两倍或1.5倍
	ps->base = (int*)realloc(ps->base, ps->stacksize * sizeof(int));
	assert(ps->base != NULL);
	//ps->top不用处理
}

//往栈中填入数据（入栈）
bool Push(PStack ps, int val)//时间复杂度：O（1）
{
	//参数判断
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}

	if (IsFull(ps))//判满
	{
		Inc(ps);//扩容
	}

	//在表尾处插入，即入栈
	ps->base[ps->top++] = val;
	//ps->top++;

	return true;
}

//获取栈顶元素的值，但不删除
bool GetTop(PStack ps, int* rtval)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}
	if (IsEmpty(ps))
	{
		return false;
	}

	*rtval = ps->base[ps->top - 1];//输出参数
	return true;
}

//获取栈顶元素的值，且删除（出栈）
bool Pop(PStack ps, int* rtval)//时间复杂度：O（1）
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}
	if (IsEmpty(ps))
	{
		return false;
	}
	*rtval = ps->base[--ps->top];//前置--,这一步就是删除
	//ps->top--;
	return true;

}
//判空
bool IsEmpty(PStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}
	return ps->top == 0;
}

bool IsBracketMatching(const char* str)
{
	assert(str != NULL);
	if (str == NULL)
	{
		return false;
	}
	Stack s;
	InitStack(&s);
	int i ;//count = 0;
	int temp;//保存栈顶的符号
	while (*str != '\0')
	{
		如果碰到左括号，入栈Push
		if (*str == '(' || *str == '[' || *str == '{')
		{
			Push(&s, *str);
		}
		如果碰到右括号，需要和栈顶的括号比较
		else if (*str == ')')
		{
			if (!IsEmpty(&s))
			{
				return false;
			}
			Pop(&s, &temp);
			if (temp != '(')
			{
				return false;
			}
		}
		else if (*str == ']')
		{
			if (!IsEmpty(&s))
			{
				return false;
			}
			Pop(&s, &temp);
			if (temp != '[')
			{
				return false;
			}
		}
		else if (*str == '}')
		{
			if (!IsEmpty(&s))
			{
				return false;
			}
			Pop(&s, &temp);
			if (temp != '{')
			{
				return false;
			}
		}
		str++;
	}
			
	判断是否为空栈
	if (!IsEmpty(&s))
	{
		return false;
	}

	return true;
}

int main()
{
	if (IsBracketMatching("{3+4*[3+2*(5-2)]}"))
	{
		printf("括号匹配成功\n");
	}
	else {
		printf("括号匹配不成功\n");
	}
	return 0;
}

• 二、中缀表达式转为后缀表达式

• 三、求栈内最小值

• 说明：定义一个新的栈结构，在该结构中可以获取当前栈内最小值Min，要求在该栈中调用入栈Push，出栈Pop和获取最小值Min的函数的时间复杂度都为O(1)。