1）凡出现左括弧，则进栈；
2）凡出现右括弧，首先检查栈是否空
若栈空，则表明该“右括弧”多余，
否则和栈顶元素比较，
若相匹配，则“左括弧出栈”
，
否则表明不匹配。
3）表达式检验结束时，
若栈空，则表明表达式中匹配正确，
否则表明“左括弧”有余。
头文件：（另存为SeqStack.h）typedef
struct
{
DataType
stack[MaxStackSize]
int
top
}
SeqStack
void
StackInitiate(SeqStack
*S)
/*初始化顺序堆栈S*/
{
S->top
=
0
/*定义初始栈顶下标值*/
}
int
StackNotEmpty(SeqStack
S)
/*判顺序堆栈S非空否，非空则返回1，否则返回0*/
{
if(S.top
<=
0)
return
0
else
return
1
}
int
StackPush(SeqStack
*S,
DataType
x)
/*把数据元素值x压入顺序堆栈S，入栈成功则返回1，否则返回0
*/
{
if(S->top
>=
MaxStackSize)
{
printf("堆栈已满无法插入!
\n")
return
0
}
else
{
S->stack[S->top]
=
x
S->top
++
return
1
}
}
int
StackPop(SeqStack
*S,
DataType
*d)
/*弹出顺序堆栈S的栈顶数据元素值到参数d
，出栈成功则返回1，否则返回0*/
{
if(S->top
<=
0)
{
printf("堆栈已空无数据元素出栈!
\n")
return
0
}
else
{
S->top
--
*d
=
S->stack[S->top]
return
1
}
}
int
StackTop(SeqStack
S,
DataType
*d)
/*取顺序堆栈S的当前栈顶数据元素值到参数d
，成功则返回1，否则返回0*/
{
if(S.top
<=
0)
{
printf("堆栈已空!
\n")
return
0
}
else
{
*d
=
S.stack[S.top
-
1]
return
1
}
}
括号问题
#include
<string.h>
#include
<stdio.h>
#include
<stdlib.h>
#define
MaxStackSize
100
typedef
char
DataType
#include
"SeqStack.h"
void
ExpIsCorrect(char
exp[],
int
n)
//判断有n个字符的字符串exp左右括号是否配对正确
{
SeqStack
myStack
//定义链式堆栈
int
i
char
c
StackInitiate(&myStack)
for(i
=
0
i
<
n
i++)
{
if((exp[i]
==
'(')
||
(exp[i]
==
'[')
||
(exp[i]
==
'{'))
StackPush(&myStack,
exp[i])
//入栈
else
if(exp[i]
==
')'
&&
StackNotEmpty(myStack)
&&
StackTop(myStack,
&c)
&&
c
==
'(')
StackPop(&myStack,
&c)
//出栈
else
if(exp[i]
==
')'
&&
StackNotEmpty(myStack)
&&
StackTop(myStack,
&c)
&&
c
!=
'(')
{
printf("左右括号配对次序不正确！\n")
return
}
else
if(exp[i]
==
']'
&&
StackNotEmpty(myStack)
&&
StackTop(myStack,
&c)
&&
c
==
'[')
StackPop(&myStack,
&c)
//出栈
else
if(exp[i]
==
']'
&&
StackNotEmpty(myStack)
&&
StackTop(myStack,
&c)
&&
c
!=
'[')
{
printf("左右括号配对次序不正确！\n")
return
}
else
if(exp[i]
==
'}'
&&
StackNotEmpty(myStack)
&&
StackTop(myStack,
&c)
&&
c
==
'{')
StackPop(&myStack,
&c)
//出栈
else
if(exp[i]
==
'}'
&&
StackNotEmpty(myStack)
&&
StackTop(myStack,
&c)
&&
c
!=
'{')
{
printf("左右括号配对次序不正确！\n")
return
}
else
if(((exp[i]
==
')')
||
(exp[i]
==
']')
||
(exp[i]
==
'}'))
&&
!StackNotEmpty(myStack))
{
printf("右括号多于左括号！\n")
return
}
}
if(StackNotEmpty(myStack))
printf("左括号多于右括号！\n")
else
printf("左右括号匹配正确！\n")
}
void
main(void)
{
char
a[]
=
"(())abc{[)(]}"
//测试例子1。左右括号配对次序不正确
char
b[]
=
"(()))abc{[]}"
//测试例子2。右括号多于左括号
char
c[]
=
"(()()abc{[]}"
//测试例子3。左括号多于右括号
char
d[]
=
"(())abc{[]}"
//测试例子4。左右括号匹配正确
int
n1
=
strlen(a)
int
n2
=
strlen(b)
int
n3
=
strlen(c)
int
n4
=
strlen(d)
ExpIsCorrect(a,
n1)
ExpIsCorrect(b,
n2)
ExpIsCorrect(c,
n3)
ExpIsCorrect(d,
n4)
}
二者放于同一目录下即可
#include <stdio.h>#include <string.h>
#define MaxSize 100
typedef char ElemType//定义数据类型
//定义顺序栈
typedef struct
{
ElemType data[MaxSize]//数据域
int top//栈顶指针
}SeqStack
//栈初始化
int InitStack(SeqStack *s)
{
s->top=-1//初始化栈顶,指向空
return 1
}
//入栈
int Push(SeqStack *s,ElemType x)
{
if (s->top == MaxSize -1 )
{
printf("栈已满,不能入栈.\n")
return 0
}
else
{
s->top++//栈顶指针上移
s->data[s->top] = x//数据元素入栈
}
return 1
}
//出栈
int Pop(SeqStack *s,ElemType *x)
{
if (s->top == -1)
{
printf("栈为空,不能出栈.\n")
return 0
}
else
{
*x=s->data[s->top]//取出栈顶元素值
s->top--//栈顶指针下移
}
return 1
}
//取栈顶值
int GetTop(SeqStack *s,ElemType *x)
{
if (s->top == -1)
{
printf("栈为空,不能取值.\n")
return 0
}
else
{
*x=s->data[s->top]//取出栈顶元素值
}
return 1
}
//判断栈是否为空
int IsEmpty(SeqStack *s)
{
if(s->top==-1)
return 1
return 0
}
int Check(char str[],int len)
{
int i
int flag=1//合法标志0-不合法 1-合法
int exist=0//小括号存在标志 0-不在 1-在
ElemType x
SeqStack s//栈s
//栈初始化
InitStack(&s)
for(i=0i<leni++)
{
if(str[i]=='{')//大括号{
{
if(IsEmpty(&s))//栈空，直接入栈
{
if(Push(&s,str[i])!=1)
{
flag=0
break
}
}
else//栈非空,判断合法性
{
if(GetTop(&s,&x)!=1)//取栈顶值
{
flag=0
break
}
if(x=='{' || x=='[' || x== '(')//如果是{,[或者(，非法
{
flag=0
break
}
else//否则入栈
{
if(Push(&s,str[i])!=1)
{
flag=0
break
}
}
}
}
else if(str[i]=='[')//方括号[
{
if(IsEmpty(&s))//栈空，直接入栈
{
if(Push(&s,str[i])!=1)
{
flag=0
break
}
}
else//栈非空,判断合法性
{
if(GetTop(&s,&x)!=1)//取栈顶值
{
flag=0
break
}
if(x=='[' || x== '(')//如果是[或者(，非法
{
flag=0
break
}
else//否则入栈
{
if(Push(&s,str[i])!=1)
{
flag=0
break
}
}
}
}
else if(str[i]=='(')//小括号(
{
//直接入栈
if(Push(&s,str[i])!=1)
{
flag=0
break
}
exist=1//小括号存在
}
else if(str[i]==')')//小括号)
{
if(Pop(&s,&x)!=1)
{
flag=0
break
}
if(x!='(')//如果出栈非(，非法
{
flag=0
break
}
}
else if(str[i]==']')//方括号]
{
if(Pop(&s,&x)!=1)
{
flag=0
break
}
if(x!='[')//如果出栈非[，非法
{
flag=0
break
}
if(exist==0)//小括号不存在,单独[]，非法
{
flag=0
break
}
}
else if(str[i]=='}')//大括号}
{
if(Pop(&s,&x)!=1)
{
flag=0
break
}
if(x!='{')//如果出栈非{，非法
{
flag=0
break
}
if(exist==0)//小括号不存在,单独[]，非法
{
flag=0
break
}
}
else//其它字符跳过
continue
}
if(!IsEmpty(&s))//循环完毕,栈非空，非法
flag=0
return flag
}
//主函数
int main(void)
{
char str[MaxSize]//录入字符串
int i,len
while(1)
{
printf("输入字符串\n")
gets(str)
len=strlen(str)
if(len>=MaxSize)//超过定义长度
return 1
if(Check(str,len)==1)
printf("匹配合法!\n")
else
printf("不合法\n")
printf("是否继续? 1-是,0否 :")
if(scanf("%d",&i)!=1 || i!=1)
break
fflush(stdin)
}
return 0
}
