数据结构：括号匹配问题。

假设一个算术表达式中允许包含两种括号：()[] 其嵌套的次序随意，请设计一个算法判断一个算术表达式中的括号是否匹配

//用栈做的
#include
#include
#include

typedef struct _stack
{
char *base;
char *top;
int num;
}Sqstack;

void InitStack(Sqstack &s)
{
s.base=(char *)malloc(100*sizeof(char));
if(s.base==NULL)
{
printf("栈创建失败!\n");
return;
}
s.top=s.base;
*s.top=0;
s.num=100;
}
void push(Sqstack &s,char k)
{
if((s.top-s.base)>=s.num)
{
printf("栈已满!\n");
return;
}
*s.top++=k;
}

void pop(Sqstack &s)
{
if(s.base==s.top)
{
printf("该栈是空栈!\n");
return;
}
s.top--;
}

bool Isempty(Sqstack &s)
{
if(s.base==s.top)
return true;
return false;
}

bool Match(Sqstack &s)
{
char str[100];
int i;
printf("请输入括号串:");
scanf("%s",str);
for(i=0;i {
switch(str[i])
{
case '[':
push(s,'[');
break;
case ']':
if(*(s.top-1)=='[')
pop(s);
else
return false;
break;
case '(':
push(s,'(');
break;
case ')':
if(*(s.top-1)=='(')
pop(s);
else
return false;
break;
}
}
if(Isempty(s))
return true;
return false;
}

int main()
{
Sqstack s;
InitStack(s);
if(Match(s))
printf("输入的括号匹配!\n");
else
printf("输入的括号不匹配!\n");
free(s.base);
return 0;
}

#include"stdio.h" #define strackmaxsize 100 typedef struct{ char stack[strackmaxsize]; int top; }stack; void initstack(stack*s){ //初始化空栈 s->top=-1; } void push(stack*s,char ch){ (s->top)++;s->stack[s->top]=ch; } void pop(stack*s,char*p){ *p=s->stack[s->top];(s->top)--; } int stackempty(stack*s){ if(s->top==-1)return 1; else return 0; } void bracket(char*str){ stack s1,*s=&s1; char e; int i=0,flag1=0,flag2; initstack(s); while(str[i]!='\0'){ switch(str[i]){ case'(':push(s,'('); break; //进栈 case')':pop(s,&e); if(e!='(')flag1=1; break; default:break; } if(flag1)break; //出现不匹配,立即结束循环 i++; } flag2=stackempty(s); //flag2判断堆栈是否为空 if(!flag1 && flag2)printf("括号匹配!\n"); else printf("括号不匹配!\n"); } void main(){ char str[100]; printf("请输入表达式: "); gets(str); bracket(str); }

include "seqstack1.h" include "stdio.h" void BracketMatch(char str); void BracketMatch(char str)  { switch(str[i]) {case '(':case '[':case '{': Push(&S,str[i]);  break;case ')': case ']': case '}' if(IsEmpty(&S)) { printf("\n右括号多余!");   return;else{ GetTop(&S,&ch); if(Match(ch,str[i]))  /用Match判断两个括号是否匹配/ Pop(&S,&ch);      /已匹配的左括号出栈/else { printf("\n对应的左右括号不同类);   retur }/switch/}/for/ if(IsEmpty(&S))printf("\n括号匹配!"); elsprintf("\n左括号多余!");} void main(){ char str[100]; printf("please input:"); gets(str); BracketMatch(str);} 这是对所输入的字符串进行括号匹配，所有的括号都包括。