数据结构考研分类复习真题 第三章 答案[17]

[题目分析]判断表达式中括号是否匹配可通过栈简单说是左括号时进栈右括号时退栈退栈时若栈顶元素是左括号则新读入的右括号与栈顶左括号就可消去如此下去输入表达式结束时栈为空则正确否则括号不匹配

int EXYX(char E[]int n)

//E[]是有n字符的字符数组存放字符串表达式以#结束本算法判断表达式中圆括号是否匹配

{char s[]; //s是一维数组容量足够大用作存放括号的栈

int top=; //top用作栈顶指针

s[top]= #; //#先入栈用于和表达式结束符号#匹配

int i=; //字符数组E的工作指针

while(E[i]!= #) //逐字符处理字符表达式的数组

switch(E[i])

{case(: s[++top]=(; i++ ; break ;

case): if(s[top]==({top; i++; break;}

else{printf(括号不配对);exit();}

case#: if(s[top]==#){printf(括号配对\n);return ();}

else {printf( 括号不配对\n);return ();} //括号不配对

default : i++; //读入其它字符不作处理

}

}//算法结束

[算法讨论]本题是用栈判断括号匹配的特例只检查圆括号的配对一般情况是检查花括号（{}）方括号（[]）和圆括号（（））的配对问题编写算法中如遇左括号（{[或（）就压入栈中如遇右括号（}]或））则与栈顶元素比较如是与其配对的括号（左花括号左方括号或左圆括号）则弹出栈顶元素否则就结论括号不配对在读入表达式结束符#时栈中若应只剩#表示括号全部配对成功否则表示括号不匹配

另外由于本题只是检查括号是否匹配故对从表达式中读入的不是括号的那些字符一律未作处理再有假设栈容量足够大因此入栈时未判断溢出

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []