数据结构之栈的应用----C程序的括号配对检查
数据结构之栈的应用----C程序的括号配对检查
已经对栈的应用有了一定的了解了，并且感觉到数据结构实在是很强大，它几乎可以解决我们生活中的大部分问题。
关于栈的基本常识，这里不做过多的解释，总之，其核心就是先进后出（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'+'\0'为每行结尾，返回这一行的字符数，不能将'\n'+'\0'计入其中；
（2）有了getline这个函数，我们对实现一段文本的提取就有了基础了，我们写这么一个名叫gettext的函数，只需每获取
一行之后就将这一行的首地址存入到一个字符串指针的形参中就可以了，形参为：char **text,int i一开始我的想法很简单，
在gettext函数里定义一个line的数组（char line[MAXLINE]），然后直接getline，然后text[i++] = line;就OK了，但是问题就
在这里产生了，如果每一次的line都通过这个赋值语句传给*text的每一个元素*text[0],*text[1]...*text[n]，那么text的每一行
都将与最新的line相关联，毕竟这是指针赋值给指针啊！！！而且，当这个gettext函数销毁时，line数组也随之销毁，text
里的每一行将会成为野指针所随机指向的一块内存，这是一个相当大的问题啊！！！解决这个问题的办法就是为每一line
申请一块动态内存空间，当然，必须得把line定义为指针了。
这个功能实现的关键几步：
/** 为line指针申请动态内存，防止被销毁**/
- char *line = (char *)malloc(sizeof(char)*MAXLINE);
/** 一个获取text的循环**/
- //malloc a string line
- while(1)
- {
- lineLen = getline(line,MAXLINE);
- text[i] = line;
- ++i;
- if(YES == hasEOF(line))
- break;
- line = (char *)malloc(sizeof(char)*MAXLINE);
- }
|
评论暂时关闭