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倍儿爽。

总之，这次并无惊奇，上一次的缩减罢了。

CodeSky 代码之空

C 今天我们来聊聊栈与括号配对

评论 (0)