问答题
阅读下列说明和算法,回答问题1和问题2。
【说明】
算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号,则给出相应的提示信息,如下所示:
文件 提示信息
(1+2)
abc) 缺少对应左括号:第2行,第4列
((def)gx) 缺少对应左括号:第3行,第10列
(((h)
ij)(k
(1ml) 缺少对应右括号:第5行,第4列;第4行,第1列
在算法2-1中,stack为一整数栈。算法中各函数的说明见表4。
{{B}}表4{{/B}}
函数名
函数功能
push (int i) 将整数i压人栈stack中
pop( ) stack的栈顶元素出栈
empty( ) 判断stack栈是否为空。若为空,函数返回1,否则函数返回0
nextch( ) 读取文本文件中的下—个字符,井返回该字符的ASCII值,将字
符所在的行号以及字符在行中的位置分别存储到变量row和col
中,若遇到文件结束符,则将变量EOF置为true
kind (char ch) 判断字符ch是左括号还是右括号,若是左括号,函数返回1,
若是右括号,函数返回2,若两者都不是,函数返回。
【算法2-1】将栈stack 置空,置EOF为false ch < - nextch(); while( not EOF) k < - kind(CH); if(k=={{U}} (1) {{/U}}) push({{U}} (2) {{/U}});push({{U}} (3) {{/U}}); elseif(k=={{U}} (4) {{/U}}) 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)的参数及其对应的返回值见表5。               {{B}}表五{{/B}}
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({{U}} 判断条件1 {{/U}})
push({{U}} (5) {{/U}});push({{U}} (6) {{/U}});push({{U}} (7) {{/U}});
elseif({{U}} 判断条件2 {{/U}}and{{U}} 判断条件3 {{/U}})
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)处补充完整。
【正确答案】
【答案解析】(1)1 (2)col (3)row (4)2 (5)col (6)row (7)k [解析] (1)栈置空,置EOF为false,并从文件中读取第一个字符到ch,然后进入循环,循环体执行一次处理一个ch。进人循环,利用 kind函数算出ch的类型k。(2)算法2-1大致流程如下:当k等于什么的时候把什么入栈;当k等于什么的时候且栈不为空的时候出栈,如果栈为空,打印错误消息,如果都不是,则读取文件的下一个字符再次进入循环。由上看出,人栈应是类型k为1,而出栈应该是类型k为2。在(4)下面出栈时,并没有用到栈的内容。在此就有些人认为栈中的内容没什么用了,随便压个ch,而且两个写的都是ch。其实从逻辑上就可以理解这种解答,如果压的是同样的数据,又是在同一位置出栈,算法大可置用一个push、pop就可以了。所以应该继续看后面的内容,以寻找正确的答案。当看到"row<-pop();col<-pop();”时,所有的疑惑就迎刃而解了,应把row和col压入栈。由于是先弹出row后弹出col,按栈的后进先出的规则,可知压入栈的是col,再压row。
问答题
【问题2】
请从下面的选项中选择相应的判断逻辑填补【算法2-1】中的“判断条件1”至“判断条件3”。注意,若“判断条件2”的逻辑判断结果为假,就无需对“判断条件3”进行判断。
(a)字符是括号
(b)字符是左括号
(c)字符是右括号
(d)栈空
(e)栈不空
(f)栈顶元素表示的是与当前字符匹配的左括号
(R)栈顶元素表示的是与当前字符匹配的右括号
【正确答案】
【答案解析】判断条件1:b 判断条件2:e 判断条件3:f [解析] 因为后面有"pop();row<-pop();col<-pop();”,所以空(5)应填col,(6)应填row。又因为判断条件1为真时需要人栈,所以判断条件1应是判断字符是不是左括号,是就人栈,所以判断条件选 b。判断条件2和3是相关联的,当2和3都为真时,要进行出栈操作,因此要判断栈是否为空。由此可以得到待判断条件2和3中,有一个必定是用来判断栈是否为空的。可以用栈顶元素来确定当前括号是否和栈中压人括号是同一类型的。前提是左括号类型已经人栈了,且在栈底,如果(7)压入的是k,即吻合。所以(7)应填k,这样判断括号是否匹配的条件就可以确定了,如果当前ch是右括号且当前栈顶的左括号类型与ch匹配,则匹配成功。应把“栈不空”作为判断条件2,“栈顶元素表示的是与当前字符匹配的左括号”作为判断条件3。这样判断条件2填e,判断条件3填f。