题目
编写一个算法，检查一个程序中的花括号、方括号和圆括号是否配对，若全部配对，则返回1, 否则返回0.对于程序中出现的对单 引号或双引号内的字符不进行括号配对检查。 39为单引号的ASCII值，34 为双引号的ASCII值，单引号和双引号如果出现则必成对出现。
假设stack是已经定义的顺序栈结构体。可以直接调用的元素进栈/出栈、取栈顶元素、判断栈空的函数定义如下:
- void push(stack &S, char ch) ;
- void pop(stack &S, char &ch) ;
- void getTop(stack S,char &ch) ;
- int isEmpty(stack S) ;//若栈S空，则返回1,否则返回0
分析
在算法中，扫描程序中的每一个字符，当扫描到每个左花括号、左方括号、左圆括号时，令其进栈:当扫描到右花括号、右方括号、右圆括号时，则检查栈顶是否为相应的左括号，若是则做退栈处理，若不是则表明出现了语法错误，返回0.当扫描到程序文件结尾后，若栈为空，则表明没有发现括号配对错误，返回1:否则表明栈中还有未配对的括号，返回0。另外，对于一对单引号或双引号内的字符不进行括号配对检查。
代码
核心代码：
/* 对字符数组str中所有的字符进行括号配对 */
int bracketsCheck(char str[],int n) {
SqStack st;// 定义一个栈
/* 必须初始化栈 */
initStack(st);
int i=0;// 定义一个变量，记录数组下标
while(i<n) {
if(str[i]==39) {// 判断字符是否是单引号
i++;// 跳过第一个单引号
while(str[i]!=39) {
i++;// 跳过单引号中的内容
}
i++;// 跳过最后一个单引号
} else if(str[i]==34) {// 判断字符是否是双引号
i++;// 跳过第一个双引号
while(str[i]!=34) {
i++;// 跳过双引号中的内容
}
i++;// 跳过最后一个双引号
} else {// 跳过单引号和双引号后进行括号配对
if(str[i]=='('||str[i]=='['||str[i]=='{') {
push(st,str[i]);// 将符合上述情况的字符压入栈中
} else if(str[i]==')') {// 判断是否配对括号"()"
char x;
getTop(st,x);// 获取栈顶元素
if(x=='(') {
pop(st,x);// 如果配对成功，则将该字符出栈
} else {
return 0;
}
} else if(str[i]==']') {// 判断是否配对括号"[]"
char x;
getTop(st,x);
if(x=='[') {
pop(st,x);
} else {
return 0;
}
} else if(str[i]=='}') {// 判断是否配对括号"{}"
char x;
getTop(st,x);
if(x=='{') {
pop(st,x);
} else {
return 0;
}
}
i++;
}
}
/* 判断最后结果，如果为空则全部配对正确，否则未配对成功 */
if(isEmpty(st)==1) {
return 1;// 配对成功返回1
} else {
return 0;// 配对失败返回0
}
}完整代码：
#include <stdio.h>
#define maxSize 20
typedef struct {
char data[maxSize];// 存放栈中元素，maxSize是已经定义好的常量
int top;// 栈顶指针
} SqStack; // 顺序栈类型定义
/* 初始化顺序栈 */
/* &st指的是要操作的顺序栈 */
void initStack(SqStack &st) {
=-1; // 只需将栈顶指针设置为-1，本栈中将top=-1规定为栈空状态
}
/* 判断栈空 */
/* st指的是要进行判空的顺序栈 */
int isEmpty(SqStack st) {
// 栈为空的时候返回1，否则返回0
if(==-1) { // 判空的条件是栈顶指针是否等于-1
return 1;
} else {
return 0;
}
}
/* 判断栈满 */
/* st指的是要进行判满的顺序栈 */
int isFull(SqStack st) {
// 如果栈顶指针等于maxSize-1那么栈满，否则栈空
if(==maxSize-1) { // maxSize是栈中最大元素个数，已经定义
return 1;// 栈满返回1
} else {
return 0;// 栈空返回0
}
}
/* 进栈 */
/* &st指的是要操作的栈；x指的是要进栈的数据 */
int push(SqStack &st,char x) {
/* 进栈首先要判断栈是否栈满，如果满栈则不能进栈 */
if(isFull(st)==1) {
return 0;// 如果栈满返回0，表示不能进栈
} else {
// 注意：++top和top++在这里的作用是一样的，都可以使用，如果是a=++top和a=top++，那么两个a的值是不一样的，最后top的值还是一样
++;// 先移动指针，再进栈
st.data[]=x;
return 1;// 进栈成功返回1
}
}
/* 出栈 */
/* &st指的是要操作的栈；&x指的是要出栈的数据 */
int pop(SqStack &st,char &x) {
/* 出栈之前要判断栈是否为空 */
if(isEmpty(st)==1) {// 1表示栈空，0表示非空
return 0;// 如果栈空，不能出栈，返回0
} else {
x=st.data[];// 先取出元素，再出栈
--;
return 1;// 出栈成功返回1
}
}
/* 得到栈顶元素 */
void getTop(SqStack st,char &x) {
if(isEmpty(st)==1) { // 如果栈空
x=' ';
} else {
x=st.data[];
}
}
/* 打印栈，从左到右表示栈底到栈顶 */
/* stack表示要被打印的栈 */
void printStack(SqStack stack) {
printf("\n");
for(int i=0; i<=; i++) {// 注意：data[0]表示栈底元素，data[top]表示栈顶元素
printf("%c\t",stack.data[i]);// 打印栈中元素
}
printf("\n");
}
/* 对字符数组str中所有的字符进行括号配对 */
int bracketsCheck(char str[],int n) {
SqStack st;// 定义一个栈
/* 必须初始化栈 */
initStack(st);
int i=0;// 定义一个变量，记录数组下标
while(i<n) {
if(str[i]==39) {// 判断字符是否是单引号
i++;// 跳过第一个单引号
while(str[i]!=39) {
i++;// 跳过单引号中的内容
}
i++;// 跳过最后一个单引号
} else if(str[i]==34) {// 判断字符是否是双引号
i++;// 跳过第一个双引号
while(str[i]!=34) {
i++;// 跳过双引号中的内容
}
i++;// 跳过最后一个双引号
} else {// 跳过单引号和双引号后进行括号配对
if(str[i]=='('||str[i]=='['||str[i]=='{') {
push(st,str[i]);// 将符合上述情况的字符压入栈中
} else if(str[i]==')') {// 判断是否配对括号"()"
char x;
getTop(st,x);// 获取栈顶元素
if(x=='(') {
pop(st,x);// 如果配对成功，则将该字符出栈
} else {
return 0;
}
} else if(str[i]==']') {// 判断是否配对括号"[]"
char x;
getTop(st,x);
if(x=='[') {
pop(st,x);
} else {
return 0;
}
} else if(str[i]=='}') {// 判断是否配对括号"{}"
char x;
getTop(st,x);
if(x=='{') {
pop(st,x);
} else {
return 0;
}
}
i++;
}
}
/* 判断最后结果，如果为空则全部配对正确，否则未配对成功 */
if(isEmpty(st)==1) {
return 1;// 配对成功返回1
} else {
return 0;// 配对失败返回0
}
}
int main() {
SqStack st;
char str[]="(('[){}''[()}])'\")[}\"([)";
int n=24;
int r=bracketsCheck(str,n);
printf("括号配对结果（1表示成功，0表示失败）：%d",r);
return 0;
}运行结果：
