软件设计师第5部分工作流程和算法流程

　　●试题4

　　阅读下列说明和算法，回答问题1和问题2，将解答填人答题纸的对应栏内。

　　【说明】

　　算法2一l可以用来检查某文本文件中的尖括号是否匹配。若文件中存在尖括号没有对应的左括号或者右括号，则给出相应的提示信息，如下所示：

　　文件提示信息

　　head>缺少对应左括号：第2行，第5列

　　< top HREF=”+urlresuh+”>>>缺少对应左括号：第3行，第10列

　　<<

　　><

　　缺少对应右括号：第5行，第2列;第4行，第1列

　　在算法2—1中，stack为一整数栈。算法中各函数的说明见表5.3。

　　表5.3

　 【算法2—1】

　　将栈stack置空，置EOF为false

　　ch<一nextChar();

　　while(not EOF)

　　k<一type(CH);

　　if(k==(1))

　　push((2));push((3));

　　else if(k==(4))

　　if(not isEmpty()) pop();pop();

　　else

　　显示错误信息(缺少对应左括号或右括号);

　　显示行号low;显示列号col;

　　endif endif ch<一nextChar();

　　endwhile

　　if(not isEmpty())

　　显示错误信息(缺少对应左括号或右括号);

　　while(not isEmpty())

　　row<一pop();col<一pop();

　　显示行号row;显示列号col;

　　endwhile

　　endif

　　为了识别更多种类的括号，对算法2一1加以改进后得到算法2—2。算法2—2能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数type(chat ch)的参数及其对应的返回值见表5.4。

　　表5.4

　　【算法2—2】

　　将栈stack置空，置EOF为false

　　ch<一nextChar();

　　while(not EOF) k<一type(ch);

　　if(k>0)

　　if(判断条件1)

　　push((5));push((6));push((7));

　　elseif(判断条件2and判断条件3)

　　pop();pop();pop();

　　else

　　显示错误信息(缺少对应左括号或右括号);

　　显示行号row;显示列号col;

　　endif

　　endif

　　ch<一nextChar();

　　endwhile

　　if(not isEmpty())

　　显示错误信息(缺少对应左括号或右括号);

　　while(not isEmpty())

　　pop();row←pop();col←pop();

　　显示行号row;显示列号col;

　　endwhile

　　endif

　　【问题1】

　　请将【算法2—1】和【算法2—2】中(1)～(7)处补充完整。

　　【问题2】

　　请从下面的选项中选择相应的判断逻辑填补【算法2—2】中的“判断条件1”至“判断条件3注意，若“判断条件2”的逻辑判断结果为假，就无需对“判断条件3”进行判断。

　　(a)字符是括号

　　(b)字符是左括号

　　(c)字符是右括号

　　(d)栈空

　　(e)栈不空

　　(f)栈顶元素表示的是与当前字符匹配的左括号

　　(g)栈顶元素表示的是与当前字符匹配的右括号

　　【问题1】解答：

　　(1)1 类型为左括号时入栈。

　　(2)col 先压入col

　　(3)row 后压入lOW

　　(4)2 类型为右括号时出栈。

　　(5)col 先弹出col

　　(6)row 后弹出row

　　(7)k

　　【问题2】解答：

　　判断条件l：(b)判断字符是否是左括号

　　判断条件2：(e)栈是否空

　　判断条件3 1(f)栈顶元素表示的是否是与当前字符匹配的左括号