C 今天我们来聊聊栈与括号配对
很巧的是,之前这两者我都有说过,虽然当时没有深刻的认识,只是很新鲜的看到了之后写了两篇日志罢了,没想到终有一天,我还是和他们俩见面了,而且是合体版。
栈:关于栈的进出 括号匹配:C 一个程序查找基本语法错误
当然,这两篇和数据结构完全没有关系,大致上是科普中的科普了。
我们来看看这次的题目:
表达式中可能出现花括号{}、方括号[]、园括号(),从键盘输入一个表达式,检查左右括号配对情况,并输出结果。 例子:{[(…)(…)]…(…)}配对 而{[(…)(…)]…[(]…)}不配对
那么接下来,开始思考怎么写,其实主函数的想法很简单,只花了一会儿就想到了,通过把左括号压入栈,读取到右括号的时候出栈,合作愉快,相安无事。
果然难点还是在核心的数据结构部分,现在我们要思考的,一是如何实现,二是如何更好的实现。
老师的课件中,这次的资料并不算详细,但有了上一次的经验也就好上手了很多。
(这次有三个版本,两个顺序一个链式)
这次先用顺序栈来写了,虽然我觉得链栈更好,但一是被坑去写了这个,二是确实也需要尝试一下,于是:
1#define STACK_INIT_LENGTH 10
2
3typedef char ElemType;
4
5/* 定义顺序栈 */
6struct stack {
7 ElemType *buf;
8 size_t elem_size; // 单个元素大小
9 size_t elem_count; // 有多少个元素
10 size_t buf_count; // 缓冲区大小
11};
12
13/* 初始化栈 */
14void InitStack(struct stack * s, size_t elem_size)
15{
16 s->elem_count = 0;
17 s->elem_size = elem_size;
18 s->buf_count = STACK_INIT_LENGTH;
19 s->buf = (ElemType *)malloc(s->buf_count * elem_size);
20}
21
可以来看看第一个版本的初始化,大致是把size,buttom的地址记住,然后往里塞就是了,这个数据结构原本可能是更好的,只是被我改怂了。
1/* 存入栈内 */
2void Push(struct stack *s, ElemType elem)
3{
4 CheckStackSize(s);
5 ElemType *p = s->buf;
6 size_t elem_count = s->elem_count;
7 s->elem_count++;
8
9 p[elem_count] = elem;
10}
11
12/* 从栈内弹出 */
13void Pop(struct stack *s, size_t count)
14{
15 if (s->elem_count >= count)
16 {
17 s->elem_count = s->elem_count - count; // 现在的元素个数
18 }
19 else
20 {
21 s->elem_count = 0;
22 }
23}
24
Push函数大致涉及了指针的使用,把指针写成数组的形式,完全可以嘛,其实就是好看那么一点(比p+i的形式好看多了吧),Pop针对这一点,没想到什么合适的写法,于是就直接从elem_count中-1完成任务,之所以这么处理,是因为这样遍历的时候无法接触到它,虽然内存中还存在,但它已经不属于这个组织了,从某种意义上来说,算是Pop了,但是这样不好:1.无法自由变动大小(减小不能,只会不断增加大小) 2.并没有free掉。
因此当时我就意识到,顺序栈,尤其是这种形式的顺序栈,是相当有局限性的,能力有限,还是用链栈好。
当然,因为还没折腾够(没有尝试过课件上的方法,我尝试了顺序栈2):
1#define STACK_INIT_LENGTH 10
2
3typedef char ElemType;
4
5typedef struct Stack {
6 ElemType *base; // 栈底
7 ElemType *top; // 栈顶位置
8 size_t stackSize; // 开辟内存空间的大小
9} Stack;
10
11void InitStack(struct Stack *s)
12{
13 s->base = (ElemType *)malloc(STACK_INIT_LENGTH * sizeof(ElemType));
14 s->top = s->base;
15 s->stackSize = STACK_INIT_LENGTH;
16}
17
这一套很标准的就是top-base,stackSize表示最大能容纳的元素的个数。
之后一些函数,内容层面上而言大同小异,唯一不同的是,我们如何获取现在的元素个数来进行对比:指针的减法。
top-base相减的结果是元素的个数。(嗯还特地去复习了一下指针来着)
这样,我们就能通过指针来进行一系列的操作了,和上一个版本并无什么不同。(其实有些区别,在版本2中把栈改成队列将会让人感觉so easy)
值得注意的是:
这里使用了一个realloc
函数,因此催生了:Why not realloc and so on...
总之就偷懒而言,realloc
依然相当好,但从某种意义上而言,他也等同于malloc + memcpy + free
(效率似乎更高)
三连贯的话:
1void list_set_size(struct list *l, size_t size)
2{
3 void *new_buf;
4
5 if (size == l->buf_count) {
6 return;
7 }
8 new_buf = (void *)malloc(size * l->elem_size);
9 memcpy(new_buf, l->buf, size < l-> buf_count ? size : l->buf_count * l->elem_size);
10 free(l->buf);
11 l->buf = new_buf;
12 l->buf_count = size;
13}
14
其次,我们再次注意这里:
1void CheckStackSize(struct Stack *s)
2{
3 if (s->stackSize == s->top - s->base)
4 {
5 SetStackSize(s, s->stackSize * 2);
6 }
7}
8
我们再次分离了几个功能,这样让其含义变得更清晰,检查,http://www.2zzt.com/,Like that.
剩下的,不再多做介绍,功能什么的,看代码,看函数名,就知道了。
那么接下来的就是链栈了,你会发现,和上一课有什么区别吗!——没有,不仅没有,反而更简单了不少,我不用再考虑排序,删去哪个元素这种问题,而是更加的简单粗暴。
这次主要是尝试着自己再写一次链表,依托函数作用,而不是依靠课件,争取早日随心所欲,当然有些失败。
1/**
2 * 元素出栈
3 * @param LinkStack s
4 * @return ElemType elem 返回出栈节点的data
5 */
6ElemType Pop(LinkStack s)
7{
8 struct Node *node = s, *p;
9 ElemType elem;
10 int i = 0;
11 int position = ElemCount(s);
12
13 if (!position)
14 {
15 return -1; // 保护机制 如果栈为空
16 }
17
18 while (node->next && i < position - 1)
19 {
20 node = node->next;
21 i++;
22 }
23 p = node->next;
24 node->next = p->next;
25 elem = p->data;
26 free(p);
27 return elem;
28}
29
其他并无惊奇,有的干脆连函数名我都没变,Pop函数无非也就是功能的删减版,让人觉得费了些心思,其实是在玩一个名叫hacked的游戏时,发现他的Push函数会返回出栈的那个元素值,感觉还是个不错的功能,回忆了一下大致都有这个功能的,于是就加了个return ,有了return ,那自然要考虑空栈也得返回,于是就推了个-1进去。
OK这里扯完了,终于我们可以扯扯我们的main函数了。
这次我们多用了两个头文件:
1#include <string.h>
2#include <time.h>
3
之后会有介绍。
inputMode
和commandMode
标记,true or false,我很喜欢玩这套,毕竟好判断嘛。
后来想了想,学着vi这种玩样儿用命令来保存之类的感觉也不错,然后嫌装逼值不够,加了个错误日志。
通过lineNum记录行数,breakLine标记错误的行数方便之后的输出。
主要是输出文件和时间这两点,新玩样儿,翻了书之后果断写之,没想到没啥意外,顿时让我感到很高兴:
1 FILE *program_data, *error_log;
2 program_data = fopen("program_data.log", "a+");
3 error_log = fopen("error_log.log", "a+");
4
5 fprintf(program_data, "=====");
6
定义文件指针,打开文件(读写模式为写入不覆盖而是追加在最后,如果没有文件则创建)
1putc(elem, program_data);
2
基本等同于putchar()
,不过这个是输出在文本中的。
1 fclose(program_data);
2 fclose(error_log);
3
一切完毕,关闭文件吧。
然后是时间:
1 time_t t; // 定义一个时间变量
2 t = time(NULL); // 获取时间
3 char *time, *p;
4 time = ctime(&t);
5 p = time;
6
ctime
函数会生成一个带换行的时间戳,导致输出不得不选择:
1 while (p && *p != '\n')
2 {
3 putc(*p, program_data);
4 putc(*p, error_log);
5 p++;
6 }
7
类似于这种方式。
这次清屏还使用了一个system("cls")
,早有耳闻,现在一试,就这个Feel倍儿爽。
总之,这次并无惊奇,上一次的缩减罢了。
评论 (0)