括号匹配实验报告

1．实验题目 括号匹配的检验 [问题描述] 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或[（[ ] [ ]）]等为正确格式，[（ ）]或（（（）均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 当计算机接受了第 1 个括号以后，他期待着与其匹配的第 8 个括号的出现，然而等来的却是第 2 个括号，此时第 1 个括号“[”只能暂时靠边，而迫切等待与第 2 个括号相匹配的 第7 个括号“]”的出现，类似的，因只等来了第 3 个括号“[”，此时，其期待的紧迫程度较第 2 个括号更紧迫，则第 2 个括号只能靠边，让位于第 3 个括号，显然第 3 个括号的期待紧迫程度高于第 2 个括号，而第 2 个括号的期待紧迫程度高于第 1 个括号；在接受了第 4 个括号之后，第 3 个括号的期待得到了满足，消解之后，第 2 个括号的期待匹配就成了最急迫的任务了，…… ，依次类推。可见这个处理过程正好和栈的特点相吻合。 2．需求分析 (1) 输入的形式和输入值的范围：从键盘上以字符串的形式输入括号序列。 (2) 输出的形式：括号匹配或是括号不匹配。 (3) 程序所能达到的功能：检验括号是否匹配。 (4) 测试 数 据 ：输入（[ ]（）），结 果 “匹配” 输入 [（（ ）]，结 果 “此串括号匹配不合法” 3．概要 设计 （1）typedef struct{ } 定 义 栈结 构 体 Status CreatStack(SqStack &S) 初 始 条 件 ：栈指 针 已 存 在 操 作 结 果 ：定 义 空 栈并 分配存 储 空 间 ，成功返 回 ok Status StackEmpty(SqStack S) 初 始 条 件 ：栈已 存 在 操 作 结 果 ：判 断 是否为空 ，是返 回 ok Status Push(SqStack &S,Elem e) 初 始 条 件 ：栈已 存 在，e 已 知 操 作 结 果 ：将 e 压 入栈中，成功返 回 ok Status Pop(SqStack &S,Elem &e) 初 始 条 件 ：栈非 空 ，栈顶 元 素 等于 e 操 作 结 果 ：栈顶 元 素 出栈 Status Bracket(SqStack &S,char *str) 初 始 条 件 ：空 栈已 存 在，括号串非 空 操 作 结 果 ：输出括号串是否匹配 void main() 操 作 结 果 ：在屏 幕 上显示 操 作 菜 单 (2)函 数 关 系 Main(){...