数据结构 栈

• 栈的相关操作
• • 栈的结构
  • 栈的初始化
  • 入栈
  • 出栈
  • 判断栈是否为空
• 栈的应用
• • 有效的括号
• 全部代码

typedef struct
{
	char* top;
	char* base;
	int stacksize;
}Stack;

void Initstack(Stack *s)
{
	s->base=(char *)malloc(sizeof(char)*Initsize);
	s->top=s->base;
	s->stacksize =Initsize;
}

void push(Stack *s,char ch)
{
	if(s->top-s->base==s->stacksize )
	{
		printf("栈已满，追加空间");
		s->base=(char *)realloc(s->base,sizeof(char)*(Initsize+10));
		s->top=s->base+s->stacksize;
		s->stacksize=Initsize+10;
	}
	*(s->top)=ch;
	s->top++;
}

void pop(Stack *s,char *ch)
{
	if(s->top==s->base)
	{
		printf("栈为空");
		return;
	}
	s->top--;
	*ch=*(s->top);
}

bool empty(Stack s)
{
	if(s.top==s.base)
	return true;
	return false;
}

括号不匹配的情况有三种：
1.左右括号不匹配
2.缺少左括号
3.缺少右括号

#include
#include
#include
#include
#include
#define Initsize 30
typedef struct
{
	char* top;
	char* base;
	int stacksize;
}Stack;
void Initstack(Stack *s)
{
	s->base=(char *)malloc(sizeof(char)*Initsize);
	s->top=s->base;
	s->stacksize =Initsize;
}
void push(Stack *s,char ch)
{
	if(s->top-s->base==s->stacksize )
	{
		printf("栈已满，追加空间");
		s->base=(char *)realloc(s->base,sizeof(char)*(Initsize+10));
		s->top=s->base+s->stacksize;
		s->stacksize=Initsize+10;
	}
	*(s->top)=ch;
	s->top++;
}
void pop(Stack *s,char *ch)
{
	if(s->top==s->base)
	{
		printf("栈为空");
		return;
	}
	s->top--;
	*ch=*(s->top);
}
bool empty(Stack s)
{
	//栈为空，返回1，否则返回0 
	if(s.top==s.base)
	return true;
	return false;
}
char gettop(Stack s)
{
	return *(--s.top);
}
//括号匹配问题 
bool bracketMatching(char *paraString)
{
	int len=strlen(paraString);
	int i;
	Stack s;
	Initstack(&s);//初始化辅助栈 
	char ch,p;
	for(i=0;i
		switch(paraString[i])
		{
			case '{':
			case '[':
			case '(':
				push(&s,paraString[i]);
				break;
			case '}':
				pop(&s,&ch);
				if(empty(s)==false||ch!='{')//缺少左括号或者括号不匹配返回0 
				return false;
				break;
			case ']':
				pop(&s,&ch);
				if(empty(s)==false||ch!='[')
				return false;
				break;
			case ')':
				pop(&s,&ch);
				if(empty(s)==false||ch!='(')
				return false;
				break;
			default://当是数字或者符号的时候直接跳过 
				break;
		}
	}
	if(empty(s)==0)//栈不为空也就是缺少右括号的情况return 0 
	return false;
	return true; 
}

 
int main()
{
	char str[100];
	printf("输入一个多项式n");
	gets(str);
	bool temp=bracketMatching(str);
	printf("多项式%s括号是否匹配(%d)",str,temp);
	
}