【说明】
算法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