括号匹配课程设计报告VIP

1 题目 括号匹配检验题目 括号匹配检验 一 问题描述一 问题描述 假设一个算术表达式可以包含 3 种括号 圆括号 和 方括号 和 和花括号 和 且这三种括号可按照任意次序嵌套使用 如 设计一个程序 判别所给定表达式中所 含括号是否匹配 二 二 要求 要求 1 将算术表达式保存在带头结点的单链表中 2 在 1 中建立的单链表上实现括号匹配问题的求解 三 三 解决问题思路 解决问题思路 1 首先建立带头结点的单链表 单链表的数据域存储字符数据 指针域为 结点型指针 设立字符型数组先将算术表达式输入到数组当中 通过插 入节点函数将数组中字符全部插入到单链中 1 中 2 建立单链表 2 通过 switch case 语句将单链表 1 中的括号字符全部插入 到单链表 2 中 3 调用括号匹配函数将 单链表 2 的头节点调入函数当中 设立标志位 has 当 has 取 1 时 说明找到一组匹配括号 当 has 取 0 时 当前一组 括号不匹配 设立 temp 指向当前所要判断节点 将 temp 所指节点的值 与 temp next 节点的值相比较 利用匹配括号 ASCII 值相差 1 或 2 相 同则相差 0 或不相同差值不为 1 2 或 0 当 temp 与 temp next 的差 值为 1 或 2 时 说明找到一组匹配括号 Temp temp next 进行新的 判断 当 temp 与 temp next 的差值不为 1 或 2 时 将 temp 赋为 temp next 进行新一轮的判断 若 temp next next 与 temp next next next 匹配时 此时将 temp next next 与 temp next next next 全部值为空值 且 temp next 未找到匹配字符时将 temp 重新赋 为 temp next 进行新的判断 4 最后 若单链表 p 为空则则说明表达式中括号匹配 若 p 不为空 则说 2 明算术表达式中括号不匹配 四 四 运行环境 运行环境 1 编辑主要环境为 microsoft visualC 6 0 2 调试运行环境为 Turbo C2 0 五 五 源代码及注释 源代码及注释 括号匹配源程序代码及注释括号匹配源程序代码及注释 kuohaopipei c include 头文件 include include define LEN 80 typedef struct list char node 数据域 struct list next 指针域 list linklist 节点类型 void initlist linklist 函数声明 int isempty linklist int creatlist node linklist char Textlist linklist void main 主函数 char test LEN int i list a b linklist p q 设立 P 为 list 结点指针 p 使 P 指向头结点 a initlist p 使 p 为第一个节点 printf Pliease input the expression n scanf 80s test for i 0 i LEN i creatlist node q test i 将数组中算术表达式存入单链 表 q 中 for i 0 inext switch q node case case case 3 case case case creatlist node p q node 将 q 中括号插入单链表 p 中 break default continue 若节点中字符不为括号则进入下一次循 环 Testlist p 调用判断括号匹配函数 用 P 链表作为实 参 if isempty p 判断 P 是否为空 p 为空则表达 式中括号匹配 printf True n printf the kuo hao in expression is pipei n else P 不为空 则表达式中 括号不匹配 printf False n printf the kuo hao in expression is not pipei n void initlist linklist aplist 构造头结点函数 struct list next aplist next NULL aplist node 0 int isempty linklist aplist 判断头结点是否为空函数 linklist next return aplist next NULL 1 0 头结点不为空侧返回 0 int creatlist node linklist aplist char a 插入字符节点函数 建立 list 型 anode 节点 将 字符 a 插入 linklist bplist aplist anode 设立 bplist 作为中间变量用于添加节点 while bplist next 4 bplist bplist next anode linklist malloc sizeof list 构造一个 list 型节点并分配空间 if anode exit 1 anode node a anode next NULL bplist next anode return 0 int Testlist linklist aplist 判断算术表达式中括号是否匹配函数 linklist temp 设立 list 型节点 temp 作为临时变量 int has 1 作为标志 当一对括号匹配时 则 has 置 为 0 否则置为 1 if isempty aplist P 为空则返回 0 return 0 while has linklist next 设立 next 为 linklist 型变量 用于指向 新的节点 has 0 temp aplist 使 temp 指向第一个节点 while temp next 若第 2 个节点不为空 进入 while 循 环 if temp next next 若第 3 个节点不为空 继续判断 if temp next next node temp next node 1 temp next next node temp next node 2 若第 3 个节点字符值减去第 2 个节点字符值为 1 或 2 则条件成立进入 if 语句 temp next temp next next next 将节点 1 赋值为节 点 3 has 1 标志 has 重置为 1 else temp temp next 若第 3 个节点字符值减去第 2 个节点字 符值为 0 则将 temp 置为下一个节点 else temp temp next 若第三个节点为空则将 temp 置为下一个节 点 if has 判断 has 的值若为 1 则退出内 while 循环 5 break return 0 当 has 值为 0 时则