suit_list.cpp

利用堆栈解决括号的匹配问题 括号的匹配问题

// ① 利用堆栈解决括号的匹配问题

#define size 100
#define stackincrement 10
typedef char SElemType;
typedef struct 
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;


#include <stdio.h>
#include<stdlib.h>

void Pop(SqStack *s,SElemType *e);   //进栈
void Push(SqStack *s,SElemType n);   //出栈

void main()
{
	SqStack s;
	SElemType e,c;
    int sign=0;
	int input=0;     //输入标志
                                //构建一个空栈
    s.base=(SElemType *)malloc(size*sizeof(SElemType));
	s.top=s.base;
	s.stacksize=size;

	printf("Input parenthesis:\n");

	while((c=getchar())!='\n')
	{
		input=1;           //有输入
		if(c=='['||c=='(')			
			Push(&s,c);
		
		if(c==']'||c==')')
		{
			if(s.top==s.base)   //避免先输入的是右括号
			{   sign=1;         //是，括号不符规则，退出
				break;
			}

			Pop(&s,&e);

			if((e=='['&&c==')') || (e=='('&&c==']'))
			{
				sign=1;           //不匹配，则置标志并退出循环
				break;
			}
		}
	}
	if(!input)                   //无任何输入
		printf("\nYou haven't input anything.\n");
	else
	   if(sign||s.top!=s.base)
		   printf("\nParenthesis are not appropriate.\n");
	   else
		   printf("\nParenthesis are  appropriate.\n");


	
}

void Push(SqStack *s,SElemType n)
{
	if((*s).top-(*s).base>=(*s).stacksize)
	{
		(*s).base=(SElemType *)realloc((*s).base,((*s).stacksize+stackincrement)*sizeof(SElemType));
		(*s).top=(*s).base+(*s).stacksize;
		(*s).stacksize +=stackincrement;
	}

	*((*s).top++)=n;
}


void Pop(SqStack *s,SElemType *e)
{
	if((*s).top==(*s).base)  return;
	*e=*(--(*s).top);
}