数据结构之栈的实施----C程序的括号配对检查
发布时间:2021-11-23 15:03:56 所属栏目:教程 来源:互联网
导读:已经对栈的应用有了一定的了解了,并且感觉到数据结构实在是很强大,它几乎可以解决我们生活中的大部分问题。 关于栈的基本常识,这里不做过多的解释,总之,其核心就是先进后出(FILO) 联想到这种模式我们就可以很容易的知道,栈可以有如下几种应用: 1、
已经对栈的应用有了一定的了解了,并且感觉到数据结构实在是很强大,它几乎可以解决我们生活中的大部分问题。 关于栈的基本常识,这里不做过多的解释,总之,其核心就是先进后出(FILO) 联想到这种模式我们就可以很容易的知道,栈可以有如下几种应用: 1、进制之间的转换 2、C程序的括号配对检查 3、迷宫求解问题 4、算术表达式求值 5、递归函数 ...... 这里,我将以一个括号配对检查的程序为例,讲述栈的应用。。。(之一) 起初看到这个题目是在K&R的书上看见的,当时看这个题时,简直是找不到东南西北,就算看了答案也是模棱两可的, 现在时隔半年,当我学到栈的时候,我才对这个程序有了一个新的角度去理解,感觉着用栈去解决这个程序在思想上 很容易理解,但是效率上还不清楚,毕竟能力还没达到可以提高程序运行效率的地步。 『首先,我们得了解实现这个程序的基本思想: 1、我们从一个C程序文本中查找括号(包括{},(),[],<>),当我们检测到其中之一时,就将它push到栈中,如果栈里的 top元素和它配对了(如:"{和}","(和)","[和]","<和>"。"}和{"不能算),就把它和top元素依次pop出来,当文本检查完 ,到了EOF时,如果栈为空,则说明括号配对了,反之,则说明此C程序括号的配对有问题 2、然后,我们还需要解决一个问题,要是有双引号和注释符怎么办?很简单,我们在检查文本时,把它们当作特殊情 况处理,如果遇到了双引号和注释符,并且它们都配对了,则把它们之间的所有内容忽略掉就OK了』 有了上述思想,我想这个程序应该就很容易实现了,我把它分为了如下几个步骤: 1、实现一个C程序文本的获取功能,可以通过实现获取一行字符的功能来实现获取一段文本的功能 (1)我们可以写一个名叫getline的函数,它的功能是从用户的输入中提取一行存入到一个字符串(char *line)中,并 以'n'+' |