原题：设计一个算法判别用字符串表示的表达式中开、闭括号是否配对出现。
#include
#include
#define INIT_SIZE 100//存储空间初始分配量
#define INCREMENT 10//存储空间分配增量
#define ElemType char
#define SIZE 100//字符串数组的大小
typedef struct
{
ElemType *base;//在栈构造之前和销毁之后，base值为NULL
ElemType *top;//栈顶指针
int stacksize;//当前已分配的存储空间，以元素为单位
}SqStack;
int InitStack(SqStack &S)
{//构造一个空栈
S.base=new ElemType[INIT_SIZE];
if(S.base == NULL)
{//溢出
cout<
}
S.top=S.base;//S.top=S.base表示为空栈
S.stacksize=INIT_SIZE;//为栈容量赋初值
return 1;
}
int Pop(SqStack &S,char &ch)
{//如栈非空，则删除栈顶元素
if(S.base == S.top)
{//栈空条件下执行
cout<
}
ch=*–S.top;//可利用e返回被删除的栈顶元素值
return 1;
}
int Push(SqStack &S,char ch)
{//入栈操作
if(S.top – S.base >= S.stacksize)
{//栈满条件下，扩大栈的容量
ElemType *tem,*p;
int i=0;
tem=new ElemType[S.stacksize + INCREMENT];//新栈的空间
if(tem == NULL)
{//溢出
cout<
}
p=S.base;
while(p != S.top)//复制数据元素值到tem所指空间中
tem[i++]=*p++;
delete[] S.base;//释放S.base所指空间
S.base=tem;//S.base指向新空间
S.top=S.base + S.stacksize;//设置新栈顶
S.stacksize+=INCREMENT;//设置新栈容量
}
*S.top++=ch;
return 1;
}
int GetTop(SqStack S,char &ch)
{//如栈非空，则将其打印输出
if(S.base == S.top)
{
cout<
}
ch=*(S.top – 1);//可利用e返回栈顶元素值
return 1;
}
int StackEmpty(SqStack S)//判断栈是否为空
{
if(S.top == S.base)
{
return 1;
}
else
{
return -1;
}
}
int Match(char *str)
{
SqStack S;
InitStack(S);//初始化栈
char *p=str;//p指向字符串的第一个字符
char ch;
while(*p!=’\0′)
{
if(*p=='(‘ || *p=='[‘)
Push(S,*p);//如果读入的字符是'(‘或'[‘，则入栈
else if(*p==’)’)
{//读入的字符是’)’
if(StackEmpty(S)==1)
{//如果栈空则不匹配
cout<
}
else if(GetTop(S,ch),ch=='(‘)
Pop(S,ch);//如果栈顶是'(‘，则出栈
else
{//否则不匹配
cout<
}
}
else if(*p==’]’)
{//读入的字符是’)’
if(StackEmpty(S)==1)
{//如果栈空则不匹配
cout<
}
else if(GetTop(S,ch),ch=='[‘)
Pop(S,ch);//如果栈顶是'[‘，则出栈
else
{//否则不匹配
cout<
}
}
p++;//当前读入的字符是其他字符或括号匹配，则继续读入
}
if(StackEmpty(S)==1)
{//栈空则括号匹配
cout<
}
else
{//栈不空则左右括号不匹配
cout<
}
}
int main()
{
char str[SIZE];
cout<
cin.getline(str,SIZE);
Match(str);
return 1;
}