【说明】
【算法4-1】的功能是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号而没有对应的左括号或者右括号，则给出相应的提示信息，如图1-18所示。
在【算法4-1】中，slack为一整数栈。算法中各函数的说明如表1-11所示。
表1-11 各函数的功能说明表
| 函 数 名 | 函数功能 |
| push(int i) | 将整数i压入栈stack中 |
| Pop() | stack的栈顶元素出栈 |
| Empty() | 判断stack栈是否为空。若为空，函数返回1，否则函数返回0 |
| Nextch() | 读取文本文件中的下一个字符，并返回该字符的ASCII值，将字符所在的行号及字符在行中的位置分别存储到变量row和col中，若遇到文件结束符，则将变量EOF置为true |
| Kind(charch) | 判断字符ch是左括号还是右括号，若是左括号，函数返回1：若是右括号，函数返回2；若两者都不是，函数返回0 |
【算法4-1】
将栈stack置空，置EOF为false
Ch＜-nextch()；
while(not EOF)
k←kind(ch)；
if (k == (1) )
push( (2) )；
push( (3) )；
else if( k == (4) )
if(not empty())
pop()；
pop()；)
else
显示错误信息(缺少对应左括号或右括号)：
显示行号row：显示列号col：)
End if
End if
Ch＜-nextch()；
end while
if(not empty())
显示错误信息(缺少对应左括号或右括号)：
While(not empty())
row＜-pop()；
col＜-pop()：
显示行号row：显示列号col；)
End while
End if
为了识别更多种类的括号，对【算法4-1】加以改进后得到【算法4-2】。【算法4-2】能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如表1-12所示。
表1-12 函数kind(charch)的参数及其对应的返回值
ch | ( | ) | [ | ] | 其他 | ||
返回值 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
将栈stack置空，置EOF为false
Ch＜-nextch()；
while(not EOF)
k＜- kind(ch)；
if(k ＞ 0)
if(判断条件1)
push( (5) )；
push( (6) )；
push( (7) )；
else if(判断条件2 and判断条件3)
pop()；
pop()；
pop()；
else
显示错误信息(缺少对应左括号或右括号)；
显示行号row；显示列号col；)
end if
end if
ch ＜- nextch()；)
end while
if(not empty())
显示错误信息(缺少对应左括号或右括号)；
While(not empty())
Pop()；
row ＜- pop()：
col ＜- pop()；
显示行号row；显示列号col；))
end while
end if
1. 【问题1】
请将【算法4-1】和【算法4-2】中，(1)～(7)空缺处的内容补充完整。
参考答案：(8)C或字符是左括号 (9)E或栈不空
(10)A或栈顶元素的是与当前字符匹配的左括号
解析：试题4[要点解析]
这是一道要求读者用创建Thread类的子类的方法实现多线程的编程题。本题的解答思路如下。
通常把限定只能在一端进行插入和删除操作的线性表称为栈，所以栈又称为运算受限的线性表。把可以进行插入和删除操作的一端称为栈顶(习惯用top指针指示)，而另一端称为栈底。当栈中不包含任何数据元素时，这个栈就为空栈。
由于栈具有“后进先出”的运算特点，因此在程序设计中应用十分广泛。例如进制转换、括号匹配的检验、表达式求值及迷宫求解等。
【算法4-1】的功能是检查文本文件中的圆括号是否匹配。若文件中存在圆括号而没有对应的左括号或者右括号，则给出图1-18所示的提示信息。从图1-18给出的信息可知，程序不但要求检查出是否有括号匹配错误，而且还需要给出具体的出错位置。通常，括号匹配的规则是把最近的左右括号配成一对，所以括号匹配最常用的方法是遇到左括号则入栈，遇到右括号则出栈。这样，出栈的左括号与当前的右括号是匹配的。
【算法4-1】分析：
1)栈置空，置EOF为FALSE，并从文件中读取第一个字符到ch，然后进入循环。循环体执行一次处理一个ch。进入循环，利用kind函数算出ch的类型k。
2)虽然【算法4-1】中有(1)～(4)空缺处，但其基本结构却很明显，大致流程如下。
当k等于什么的时候把什么入栈；
当k等于什么且栈不为空的时候，进行出栈操作。如果栈为空，则打印错误信息：如果都不是，则读文件的下一个字符再次进入循环。
根据以上所提到的算法可知，入栈操作应该发生在类型A为1(即ch为左括号)时，而出栈操作应该发生在类型A为2(即ch为右括号)时。因此(1)空缺处所填写的内容是“1”，(4)空缺处所填写的内容是“2”。
由于在(4)空缺处之后的出栈操作中，并没有用到栈的内容。因此可能有些读者理所当然地认为栈中的内容没有什么用，可以在(2)、(3)空缺处随便压个ch，即两个空缺处均填写“ch”。但换个角度思考，从逻辑上就可以推翻这种解答。如果(2)、(3)空缺处压的是同样的数据，又是在同一位置出栈，算法大可只用一个push、pop就可以了。
由语句“row＜-pop()；col＜-pop()；”可知，(2)、(3)空缺处应该把row和col压入堆栈。由于是先弹出FOW后弹出col，并且根据栈的“后进先出”规则可知，应先将col压入栈，再压入row。因此 (2)空缺处所填写的内容是“col”，(3)空缺处所填写的内容是“row”。
【算法4-2】分析：
同理，由【算法4-2】中的语句“row＜-pop根据栈的“后进先出”规则可知，()；col＜-pop()：”可知， (5)、(6)空缺处应该把row和col压入堆栈。应先将col压入栈，再压入row，即(5)空缺处所填写的内容是“col”，(6)空缺处所填写的内容是“row”。
由于判断条件1为真时，需要进行入栈操作，因此判断条们：1应是判断字符是不是左括号，如果是就入栈，即(8)空缺处应选择选项C的“字符是左括号”。
判断条件2和判断条件3是相关联的，当两个判断条件都为真时，要进行出栈操作，因此要判断栈是否为空。由此可以得出在判断条件2和判断条件3中，至少有一个必定是用来判断栈是否为空的。可以用判断栈顶元素来确定当前括号是否和栈中压入括号是同一类型的，但前提是左括号类型入了栈，而且要在栈顶。如果(7)空缺处压入的是k，则正好符合这一条件。所以(7)空缺处所填写的内容是“k”。
同时，判断括号是否匹配的条件也就可以确定了，如果当前ch是右括号且当前栈顶的左括号(只有左括号入了栈)类型与ch匹配，则匹配成功。根据试题说明中的提示信息：若“判断条件2”的逻辑判断结果为假，就无须对“判断条件3”进行判断，所以应把“栈不空”作为判断条件2，“栈顶元素表示的是与当前字符匹配的左括号”作为判断条件3，即(9)空缺处应选择选项E的“栈不空”，(10)空缺处应选择选项A的“栈顶元素表示的是与当前字符匹配的左括号”。