前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >基于栈和队列实现括号匹配算法

基于栈和队列实现括号匹配算法

作者头像
陈黎栋
发布2020-02-18 09:38:26
9640
发布2020-02-18 09:38:26
举报

1、主题

基于栈和队列实现括号匹配算法。

2、学习视频和资料

视频 http://study.163.com/course/courseLearn.htm?courseId=555010#/learn/video?lessonId=701019&courseId=555010

http://study.163.com/course/courseLearn.htm?courseId=555010#/learn/video?lessonId=702024&courseId=555010

3、实现

数组或列表实现栈和队列

4、应用

编程中的括号匹配、四则运算

队列

交互式程序中生产消费队列

5、知识体系

栈的基本操作

  1. 定义栈的元素
  2. 建立栈的信息:栈底、大小、栈顶标记
  3. 初始化栈的操作
  4. 销毁栈的操作
  5. 入栈操作(包括溢出判断,开辟新空间)
  6. 获取栈顶指针操作(出栈)
  7. 获取栈顶信息操作(出栈)
  8. 栈为空判断

用栈来检测表达式中的括号是否匹配

问题:(1)栈什么时候为空?标记法

a、栈底存储特殊标记

b、记录栈底的位置

(2)栈溢出怎么办?

a、开辟固定空间,设置一个计数值,如果达到上限,就申请新空间。

b、链式的,入一个就开辟一个空间。(效率低)

更多的时候使用栈时是连续的空间,而不是链式。

场景分析:

6、程序框架

typedef struct _member
{
    char ch;//单元内容
    int line;//行号
    int column;//列号
}node,*pnode;
 
typedef struct _stack_ds //记录栈的信息
{
    int size;//size of stack
    int memb;//number of members
    node ptr[0];//stack location 存放数据的位置
}stack_ds,*pstack_ds;
 
pstack_ds init_stack(int size)
{
    pstack_ds head = (pstack_ds)malloc(sizeof(stack_ds) + sizeof(node)*size);
    head->size = size;
    head->memb = 0;
    memset(head->ptr,'\0',sizeof(node)*size);
 
    return head;
}
 
void destroy_stack(pstack_ds head)
{
    free(head); //一次申请一次释放
}
 
void push_stack(pstack_ds head,char ch,int line,int column)
{
    if (head->memb == head->size)
    {
        //realloc stack memory, to do
    }
    head->ptr[head->memb].ch = ch;
    head->ptr[head->memb].line = line;
    head->ptr[head->memb].column = column;
 
    head->memb++;
}
 
pnode pop_stack(pstack_ds head)
{
    if(head->memb == 0)
        return null;
    else
    {
        head->memb--;
        return head.ptr + head->memb;
    }
}
 
char fetch_top_memb(pstack_ds head)
{
    if(head->memb == 0)
        return -1;
    else
        return head->ptr[head->memb - 1].ch;
}
 
/*判断栈是否空*/
int empty_stack(pstack_ds head)
{
    if (head->member <= 0)
    {
        return 1;
    }
    else
        return 0;
}
 
int main(int argc,char *argv[])
{
    if(argc < 2)
    {
        printf("pls usage %s filename\n",argv[0] );
        exit(EXIT_FAILURE);
    }
    FILE *fp = fopen(argv[1],"r");
    if (fp == NULL)
    {        
        perror("fopen");
        exit(EXIT_FAILURE);
    }
 
    fclose(fp);
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1、主题
  • 2、学习视频和资料
  • 4、应用
      • 队列
      • 5、知识体系
        • 栈的基本操作
          • 用栈来检测表达式中的括号是否匹配
          • 6、程序框架
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档