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

很巧的是,之前这两者我都有说过,虽然当时没有深刻的认识,只是很新鲜的看到了之后写了两篇日志罢了,没想到终有一天,我还是和他们俩见面了,而且是合体版。

栈:关于栈的进出
括号匹配:C 一个程序查找基本语法错误

当然,这两篇和数据结构完全没有关系,大致上是科普中的科普了。

我们来看看这次的题目:

表达式中可能出现花括号{}、方括号[]、园括号(),从键盘输入一个表达式,检查左右括号配对情况,并输出结果。
例子:{[(…)(…)]…(…)}配对
而{[(…)(…)]…[(]…)}不配对

那么接下来,开始思考怎么写,其实主函数的想法很简单,只花了一会儿就想到了,通过把左括号压入栈,读取到右括号的时候出栈,合作愉快,相安无事。

果然难点还是在核心的数据结构部分,现在我们要思考的,一是如何实现,二是如何更好的实现。

老师的课件中,这次的资料并不算详细,但有了上一次的经验也就好上手了很多。

(这次有三个版本,两个顺序一个链式)

这次先用顺序栈来写了,虽然我觉得链栈更好,但一是被坑去写了这个,二是确实也需要尝试一下,于是:

#define STACK_INIT_LENGTH 10

typedef char ElemType;

/* 定义顺序栈 */
struct stack {
    ElemType *buf;
    size_t elem_size;       // 单个元素大小
    size_t elem_count;      // 有多少个元素
    size_t buf_count;       // 缓冲区大小
};

/* 初始化栈 */
void InitStack(struct stack * s, size_t elem_size)
{
    s->elem_count = 0;
    s->elem_size = elem_size;
    s->buf_count = STACK_INIT_LENGTH;
    s->buf = (ElemType *)malloc(s->buf_count * elem_size);
}

可以来看看第一个版本的初始化,大致是把size,buttom的地址记住,然后往里塞就是了,这个数据结构原本可能是更好的,只是被我改怂了。

/* 存入栈内 */
void Push(struct stack *s, ElemType elem)
{
    CheckStackSize(s);
    ElemType *p = s->buf;
    size_t elem_count = s->elem_count;
    s->elem_count++;

    p[elem_count] = elem;
}

/* 从栈内弹出 */
void Pop(struct stack *s, size_t count)
{
    if (s->elem_count >= count)
    {
        s->elem_count = s->elem_count - count;     // 现在的元素个数
    }
    else
    {
        s->elem_count = 0;
    }
}

Push函数大致涉及了指针的使用,把指针写成数组的形式,完全可以嘛,其实就是好看那么一点(比p+i的形式好看多了吧),Pop针对这一点,没想到什么合适的写法,于是就直接从elem_count中-1完成任务,之所以这么处理,是因为这样遍历的时候无法接触到它,虽然内存中还存在,但它已经不属于这个组织了,从某种意义上来说,算是Pop了,但是这样不好:1.无法自由变动大小(减小不能,只会不断增加大小) 2.并没有free掉。

因此当时我就意识到,顺序栈,尤其是这种形式的顺序栈,是相当有局限性的,能力有限,还是用链栈好。

当然,因为还没折腾够(没有尝试过课件上的方法,我尝试了顺序栈2):

#define STACK_INIT_LENGTH 10

typedef char ElemType;

typedef struct Stack {
    ElemType *base;         // 栈底
    ElemType *top;          // 栈顶位置
    size_t stackSize;      // 开辟内存空间的大小
} Stack;

void InitStack(struct Stack *s)
{
    s->base = (ElemType *)malloc(STACK_INIT_LENGTH * sizeof(ElemType));
    s->top = s->base;
    s->stackSize = STACK_INIT_LENGTH;
}

这一套很标准的就是top-base,stackSize表示最大能容纳的元素的个数

之后一些函数,内容层面上而言大同小异,唯一不同的是,我们如何获取现在的元素个数来进行对比:指针的减法。

top-base相减的结果是元素的个数。(嗯还特地去复习了一下指针来着)

这样,我们就能通过指针来进行一系列的操作了,和上一个版本并无什么不同。(其实有些区别,在版本2中把栈改成队列将会让人感觉so easy)

值得注意的是:
这里使用了一个realloc函数,因此催生了:Why not realloc and so on...
总之就偷懒而言,realloc依然相当好,但从某种意义上而言,他也等同于malloc + memcpy + free(效率似乎更高)

三连贯的话:

void list_set_size(struct list *l, size_t size)
{
    void *new_buf;

    if (size == l->buf_count) {
        return;
    }
    new_buf = (void *)malloc(size * l->elem_size);
    memcpy(new_buf, l->buf, size < l-> buf_count ? size : l->buf_count * l->elem_size);
    free(l->buf);
    l->buf = new_buf;
    l->buf_count = size;
}

其次,我们再次注意这里:

void CheckStackSize(struct Stack *s)
{
    if (s->stackSize == s->top - s->base)
    {
        SetStackSize(s, s->stackSize * 2);
    }
}

我们再次分离了几个功能,这样让其含义变得更清晰,检查,http://www.2zzt.com/,Like that.

剩下的,不再多做介绍,功能什么的,看代码,看函数名,就知道了。

那么接下来的就是链栈了,你会发现,和上一课有什么区别吗!——没有,不仅没有,反而更简单了不少,我不用再考虑排序,删去哪个元素这种问题,而是更加的简单粗暴。

这次主要是尝试着自己再写一次链表,依托函数作用,而不是依靠课件,争取早日随心所欲,当然有些失败。

/**
 * 元素出栈
 * @param LinkStack s
 * @return ElemType elem 返回出栈节点的data
 */
ElemType Pop(LinkStack s)
{
    struct Node *node = s, *p;
    ElemType elem;
    int i = 0;
    int position = ElemCount(s);

    if (!position)
    {
        return -1;  // 保护机制 如果栈为空
    }

    while (node->next && i < position - 1)
    {
        node = node->next;
        i++;
    }
    p = node->next;
    node->next = p->next;
    elem = p->data;
    free(p);
    return elem;
}

其他并无惊奇,有的干脆连函数名我都没变,Pop函数无非也就是功能的删减版,让人觉得费了些心思,其实是在玩一个名叫hacked的游戏时,发现他的Push函数会返回出栈的那个元素值,感觉还是个不错的功能,回忆了一下大致都有这个功能的,于是就加了个return ,有了return ,那自然要考虑空栈也得返回,于是就推了个-1进去。


OK这里扯完了,终于我们可以扯扯我们的main函数了。

这次我们多用了两个头文件:

#include <string.h>
#include <time.h>

之后会有介绍。

inputModecommandMode标记,true or false,我很喜欢玩这套,毕竟好判断嘛。

后来想了想,学着vi这种玩样儿用命令来保存之类的感觉也不错,然后嫌装逼值不够,加了个错误日志。

通过lineNum记录行数,breakLine标记错误的行数方便之后的输出。

主要是输出文件和时间这两点,新玩样儿,翻了书之后果断写之,没想到没啥意外,顿时让我感到很高兴:

    FILE *program_data, *error_log;
    program_data = fopen("program_data.log", "a+");
    error_log = fopen("error_log.log", "a+");

    fprintf(program_data, "=====");

定义文件指针,打开文件(读写模式为写入不覆盖而是追加在最后,如果没有文件则创建)

putc(elem, program_data);

基本等同于putchar(),不过这个是输出在文本中的。

    fclose(program_data);
    fclose(error_log);

一切完毕,关闭文件吧。

然后是时间:

    time_t t;   // 定义一个时间变量
    t = time(NULL); // 获取时间
    char *time, *p;
    time = ctime(&t);
    p = time;

ctime函数会生成一个带换行的时间戳,导致输出不得不选择:

    while (p && *p != '\n')
    {
        putc(*p, program_data);
        putc(*p, error_log);
        p++;
    }

类似于这种方式。

这次清屏还使用了一个system("cls"),早有耳闻,现在一试,就这个Feel倍儿爽。

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

植入部分

如果您觉得文章不错,可以通过赞助支持我。

如果您不希望打赏,也可以通过关闭广告屏蔽插件的形式帮助网站运作。

标签: 成品, 源码, 知识, 语法, 题目

添加新评论