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>
之后会有介绍。
inputMode
和commandMode
标记,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倍儿爽。
总之,这次并无惊奇,上一次的缩减罢了。
植入部分
如果您觉得文章不错,可以通过赞助支持我。
如果您不希望打赏,也可以通过关闭广告屏蔽插件的形式帮助网站运作。