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 = 0i <ni++)
{
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 <stdlib.h>
int main()
{
int i,count
char ch[10001],ch1[10001]
while(gets(ch)!=NULL)
{
count=-1
for(i=0ch[i]!='\0'i++)
{
if(ch[i]=='('||ch[i]=='['||ch[i]=='<'||ch[i]=='{')
{
ch1[++count]=ch[i]
}
else
{
if(ch[i]-ch1[count]<3)
{
count--
}
else
{
break
}
}
}
if(count==-1)
printf("YES\n")
else
printf("NO\n")
}
return 0
}