2. 考研
  3. 判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组E[n]中，‘#’为字符表达式的结束符。给出一个算法，用于判断表达式中括号(’(’和’)’)是否配对。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或Java语言描述算法

判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组E[n]中，‘#’为字符表达式的结束符。给出一个算法，用于判断表达式中括号(’(’和’)’)是否配对。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或Java语言描述算法

admin2019-08-01  46
问题 判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组E[n]中，‘#’为字符表达式的结束符。给出一个算法，用于判断表达式中括号(’(’和’)’)是否配对。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
选项
答案(1)算法的基本思想：判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 在读入表达式结束符’#’时，栈中若只剩’#’，表示括号全部配对成功；否则表示括号不匹配。另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。因假设栈容量足够大，因此入栈时未判断溢出。 (2)算法的设计如下： int exyx(char E[]，int n){ ／／判断表达式中圆括号是否匹配 char s[30]； ／／s是一维数组，容量足够大，用作存放括号的栈 int top=0； ／／top用作栈顶指针 s[top]=’#’； ／／’#’先入栈，用于和表达式结束符号’#’匹配 int i=0； ／／字符数组E的工作指针 while(E[i]!=’#’) ／／逐字符处理字符表达式的数组 switch(E[i]){ case’(’：s[++top]=’(’；i++；break； case’)’：if(s[top]==’(’){top一一；i++；break；} else{printf(”括号不配对”)；exit(0)；} case’#’：if(s[top]==’#’){printf(”括号配对＼n”)；return(1)：} else{printf(”括号不配对＼n”)；return(0)；}／／括号不配对 default：i++； ／／读入其他字符，不作处理 } }
解析
转载请注明原文地址:https://kaotiyun.com/show/okCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)