2004年上半年下午算法相关考题

2014年1月2日 作者： 来源：

阅读下列说明和算法，回答问题1和问题2，将解答填入答题纸的对应栏内。
[说明]
算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如下所示：

文件	提示信息
(1+2)
abc)	缺少对应左括号：第2行，第4列
((def)gx))	缺少对应左括号：第3行，第10列
(((h)
ij)(k
(lml)	缺少对应左括号：第5行，第4列；第4行，第1列

在算法2-1中，stack为一整数栈。算法中各函数的说明如下表的示：

函数名	函数功能
push(int i)	将整数i压入栈顶元素
pop()	stack的栈顶元素出栈
empty()	判断stack栈是否为空。若为空，函数返回1，否则函数返回0。
nextch()	读取文本文件中的下一个字符，并返回该字符的ASCII值，将字符所在的行号以及字符在行中的位置分别存储到变量row和col中，若遇到文件结束符，则将变量EOF置为ture。
kind(char ch)	判断字符ch是在左括号还是右括号，若是左括号，函数返回1，若是右括号，函数返回2，若两者都不是，返回o。

 [算法2-1]
将栈stack置空，置EOF为false
　ch <- nextch();
　while(not EOF)
　　　k <- kind(ch);
　　　if (k== (1) )
　　　　　push( (2) ); push( (3) );
　　　elseif (k == (4) );
　　　if(not empty())
　　　　pop();pop();
　　　else
　　显示错误信息（缺少对应左括号或右括号）；
　　显示行号row;显示列号col;
　　endif
　　endif
　ch <- nextch();
　endwhile
　　　if (not empty())
　　显示错误信息（缺少对应左括号或右括号）；
　　while(not empty())
　　row <- pop(); col <- pop();
　　显示行号row;显示列号col;
　　endwhile
　　endif
　　为了识别更多种类的括号，对算法2-1加以改进后得到算法2-2。算法2-2能够识别圆括号，方括号和花括号（不同类型的括号不能互相匹配）。改进后，函数kind(char ch)的参数及其对应的返回值如下表所示：

Ch	(	)	{	}	[	]	其它
返回值	1	2	3	4	5	6	0

 [算法2-2]
将栈stack置空，置EOF为false
　ch <- nextch();
　while(not EOF)
　　　k <- kind(ch);
　　if (k>0)
　　　　if (判断条件1)
　　　　　　push( (5) );push( (6) );push( (7) )；
　　　elseif （判断条件2 and 判断条件3）
　　　　pop(); pop(); pop();
　　　else
　　显示错误信息（缺少对应左括号或右括号）;
　　显示行号row;显示列号col;
　　endif
　　endif
　　ch <- nextch();
　　　　endwhile
　　if (not empty())
　　显示错误信息（缺少对应左括号或右括号）;
　　　while(not empty())
　　　　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）栈顶元素表示的是与当前字符匹配的右括号