括号匹配检验
括号匹配检验
利用栈编写满足下列要求的括号匹配检验程序：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(]或([())或(()])均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配对。
Input
第一行：输入一个包含圆括号或方括号、不超过80个字符的表达式串。
Output
第一行：若输入表达式括号匹配，输出"matching"; 若不匹配，输出具体信息:"isn't matched pairs", 或"lack of left parenthesis"或"lack of right parenthesis"
typedef char SElemType;
#include"malloc.h"
#include"stdio.h"
#include"math.h"
#include"process.h" // exit()
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，
如OK等
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈
Status InitStack(SqStack &S)
{ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
S.top=S.base;
if(!S.base) return ERROR;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{if(S.base==S.top) return TRUE;
else return FALSE;
}
Status Push(SqStack &S,SElemType e)
{ if(S.top-S.base>=S.stacksize) {
S.base=(SElemType
*)realloc(S.base,(STACK_INIT_SIZE+S.stacksize)*sizeof(SElemType)); if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+STACK_INIT_SIZE;}
*S.top=e;
S.top++;
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{ if(S.base==S.top) return ERROR;
e=*--S.top;
return OK;
}
void check()
{ // 对于输入的任意一个字符串，检验括号是否配对
SqStack s;
SElemType ch[80],*p,e;
if(InitStack(s)) // 初始化栈成功
{
//printf("请输入表达式\n");
scanf("%s",ch);
p=ch;
while(*p) // 没到串尾
switch(*p)
{
case '(':
case '[':Push(s,*p);p++;
break; // 左括号入栈，且p++
case ')':
case ']':if(!StackEmpty(s)) // 栈不空
{
Pop(s,e); // 弹出栈顶元素
if(*p==')'&&e!='('||*p==']'&&e!='[')
// 弹出的栈顶元素与*p不配对
{
printf("isn't matched pairs\n");
exit(ERROR);
}
else
{
p++;
break; // 跳出switch语句
}
}
else // 栈空
{
printf("lack of left parenthesis\n");
exit(ERROR);
}
default: p++; // 其它字符不处理，指针向后移
}
if(StackEmpty(s)) // 字符串结束时栈空
printf("matching\n");
else
printf("lack of right parenthesis\n");
}
}
void main() {
check(); }
数据结构课程设计---括号匹配
目录 1 问题描述 (2) 1.1题目 (2) 1.2问题 (2) 1.3要求 (2) 2 设计 (2) 2.1存储结构设计 (2) 2.2主要算法设计 (3) 2.3测试用例及测试结果 (6) 3 调试报告 (9) 4 对设计和编码的讨论和分析 (20) 4.1设计 (20) 4.2对编码的讨论 (21) 5 总结和体会 (22) 附录一 (24) 本科生课程设计成绩评定表................... 错误！未定义书签。
数据结构课程设计 ——判别括号配对 1问题描述 1.1题目： 判别括号配对 1.2问题： 一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。 1.3要求： （1）表达式从键盘输入。 （2）利用栈求解此问题。 （3）测试用例自己设计。 2设计 2.1存储结构设计 题目要求利用栈来求解此问题，因此选择顺序栈作为存储结构，具体表示如下： #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10
char *base; char *top; int stacksize; }SqStack; 2.2主要算法设计 2.2.1算法思想 (1)文字描述 从键盘输入一个表达式； 逐个扫描表达式中的字符； 当遇到左括号时，将左括号入栈； 继续扫描，将此后遇到的第一个右括号与栈顶元素比较，若匹配，则栈顶元素出栈；否则，继续扫描； 当整个表达式扫描完以后，判断栈内是否还有元素，若有，则括号不匹配； 若栈为空，则括号配对成功； 在括号配对不成功的情况下，利用栈顶栈底元素的差值，可以对左右括号数进行比较。（2）流程图表示
堆栈应用
1引言 本课程主要是对栈的一些基本操作以及栈的应用进行设计的，栈是操作受限的线性表，先进后出，可称为限定性的数据结构]1[。栈的基本操作包括栈的初始化，进栈操作、出栈操作、取栈顶元素、判读栈是否为空、判断栈是否满以及对栈的置空，通过这些基本操作的组合来实现进制转换、括号匹配、文本输入。 2问题分析 2.1进制转换 将一个十进制的数转换为另一进制，基于数的组成原理位权与进制，转换时让十进制数除以该进制，得到的便是最低位上的数，用得到的商再除以该进制则得到次低位上的数，依次循环下去直到得到的商为0；进制转换完毕，可以看出我们得到首先的是最低位，而数据的书写形式是从高位到低位，所以选择栈的存储结构先进后出，得到的余数顺序进栈，等到结束再顺序出栈输出，这时就是我们先要的结果。 2.2括号匹配 括号匹配是对于一组括号的判断，当输入一个左括号时，它就会等待与之相应的右括号出现，如果等来的却是另一个左括号，那么这时最迫切等待的是刚输入的那个左括号，它会等待与之相应的右括号出现。如果等来了与之相应的右括号，那么它得到了匹配，现在迫切等待的是它之前的左括号，可以看出先进去的左括号迫切需要的程度没后来进去的左括号强，后来者居上，我们选择栈的存储结构，先来的括号进栈，栈顶元素是需要程度最强的，得到了匹配则退栈。 2.3文本输入 文本输入是对于文章来说的，而输入文本时时常会出错，当输入特定的字符时我们会删除该行最后的文字，当错误太多时我们会整行删除，输入特定字符时换行。可以看出这些操作都是在文本的最后执行，所以我们也选择栈存储结构，输入一个字符进栈，输入特定的字符1让栈顶元素出栈，输入特定字符2，则将栈清空。如果栈满，则将文本输出，并且置空，接受下一行的文本，直到输入结束。 由于三种功能用到栈的类型一样，所以我们定义一个类型栈就可以了，栈的定义，如下： typedef char status; typedef struct { status *base; status *top; int stacksize; }sqstack;
C++栈实现括号匹配
//本程序以经亲测，在VS2008中复制即可实现。 // Stack_made_by_zrz.cpp : 定义控制台应用程序的入口点。 //括号匹配问题。利用栈来解决一个字符串之中使用的括号是否匹配的问题。 /* 在表达式中，相同类型的括号（包括：（）、[ ]、{}）是成对出现的，并且当括号在表达式中嵌套时，不允许出现交叉现象。 检验括号匹配的方法，就是对给定的字符串依次检验：若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配； 是其他字符，不检验。检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的。 */ #include"stdafx.h" #include
实验二 堆栈和队列基本操作的编程实现
实验二堆栈和队列基本操作的编程实现 【实验目的】 堆栈和队列基本操作的编程实现 要求： 堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 内容： 把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。 利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。 【思考问题】 1.栈的顺序存储和链表存储的差异？ 2.还会有数据移动吗？为什么？ 3.栈的主要特点是什么？队列呢？ 4.栈的主要功能是什么？队列呢？ 5.为什么会有环状队列？ 【参考代码】 （一）利用顺序栈实现十进制整数转换转换成r进制 1、算法思想 将十进制数N转换为r进制的数，其转换方法利用辗转相除法，以N=3456，r=8为例转换方法如下： N N / 8 （整除）N % 8（求余） 3456 432 0 低 432 54 0 54 6 6 6 0 6 高 所以：（3456）10 =（6600）8 我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。 算法思想如下：当N>0时重复1，2 ①若N≠0，则将N % r 压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。 ②用N / r 代替N 2、转换子程序
用栈实现括号匹配的检验 修改
用栈实现括号匹配的检验修改(2008-11-14 19:06:31) 标签：c语言编程turbo c2.0环境实现栈括号匹配it 分类：C语言编程例子数据结构C 语言版 括号匹配问题是编译程序时经常遇到的问题，用以检测语法是否有错。 本文前些天写的用栈实现括号匹配的检验的代码中，其中用了更少变量的代码二有些错误，使得结果总是match，经过修改，现将正确的代码写出，如下 #include
堆栈应用括号匹配实验
深圳大学实验报告 课程名称：数据结构实验与课程设计 实验项目名称：堆栈应用括号匹配实验 学院：计算机与软件学院 专业：未分 指导教师：杨芳 报告人：姜家祥学号：2013150387 班级：08 实验时间：2013-10-9 实验报告提交时间：2014-10-10 教务处制
一、实验目的 掌握堆栈的基本原理 掌握堆栈的存储结构 掌握堆栈的进栈、弹栈、判断栈空的实现方法 掌握应用堆栈实现括号匹配的原理和实现方法 二、实验要求 熟悉C++语言编程 熟练使用C++语言实现堆栈的进栈Push、插入Pop、判断栈空等操作 熟练使用堆栈实现括号匹配算法 三、实验内容 本次实验有两项内容： （一）堆栈应用括号匹配 1、问题描述 一个算术表达式中包括圆括号、方括号和花括号三种形式的括号 编程实现判别表达式中括号是否正确匹配的算法 2、算法 顺序扫描算术表达式 若算术表达式扫描完成，此时如果栈空，则正确返回(0)；如果栈未空，说明左括号多于右括号，返回(-3) 从算术表达式中取出一个字符，如果是左括号(‘(‘或‘[‘或‘{‘)，则让该括号进栈(PUSH) 如果是右括号(‘)‘或‘]‘或‘}‘)： ⑵ 、如果栈为空，则说明右括号多于左括号，返回(-2) ⑵、如果栈不为空，则从栈顶弹出(POP)一个括号：若括号匹配，则转1继续进行判断；否则，说明左右括号配对次序不正确，返回(-1) 3、输入 第一行：样本个数，假设为n。 第二到n+1行，每一行是一个样本（算术表达式串），共n个测试样本。 4、输入样本 4 {[(1+2)*3]-1} {[(1+2]*3)-1} (1+2)*3)-1} {[(1+2)*3-1] 5、输出 共有n行，每一行是一个测试结果，有四种结果： 0：左右括号匹配正确{[(1+2)*3]-1}
括号匹配检验
括号匹配检验，是假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即( [ ] ( ) )或[ ( [ ] )]等为正确的格式，[ ( ] )或( [ ( ))或( ( ) ] )均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”概念来描述。整个处理过程与栈的特点相吻合。因此此程序利用链表的头插法特点来完成。 #include "stdlib.h" #include "stdio.h" typedef struct Stack { char ch; struct Stack *next; }Stack,*StackList; char checkinput() /*检查输入数据的合理性*/ { char c; while(1) { printf("input the bracket:"); scanf("%c",&c); getchar(); if(c=='('||c==')'||c=='['||c==']') /*程序的有效性检测*/ break; else { printf("you input wrong! please input again!\n"); continue; } } return c; } int InitStack() /*创建栈的实例*/ { StackList L,s,t; char c; int i=0,n=0; L=(Stack*)malloc(sizeof(Stack));/*创建链表*/ L->next=NULL; while(1)
c=checkinput(); switch(c) { case '(': case '[': s=(Stack*)malloc(sizeof(Stack)); s->ch=c; s->next=L->next; /*头插法实现“栈”的功能*/ L->next=s; i=++n; /*n用来记录压入栈里的凡是左括号的数目*/ break; case ')': case ']': if(i==0) return 0; /*i用来判断第一次输入的括号是否为右括号，是则退出程序*/ t=L->next; if(t->ch+1==c) /*检查是否为'('和')'，用他们的ACSII码值来检测*/ { L->next=t->next; /*匹配则删除栈顶元素*/ n--; printf("此项%c括号匹配！\n",t->ch); free(t); } else if(t->ch+2==c) /*检查是否为'['和']'*/ { L->next=t->next; /*匹配则删除栈顶元素*/ n--; printf("此项%c括号匹配！\n",t->ch); free(t); } else return 0; /*此语句判断输入两个括号后不匹配的结果,如'['和'）'*/ break; } if(n==0) return 1; }
利用顺序栈实现括号匹配 c语言
#include
数据结构实验报告(栈_括号匹配) (1)
数据结构课程设计报告 设计题目：括号匹配 院系计算机学院 年级11 级 学生刘云飞 学号E01114295 指导教师王爱平 起止时间9-7/9-14
课程设计目的 1.熟悉并写出栈的逻辑结构表示 2.实现栈的存储表示 3.实现栈的操作 内容 括号匹配 课程设计要求 1.在实验报告中写出栈的ADT表示； 2.在实验报告中给出数据类型定义和核心算法和程序； 3.在实验报告中罗列实验过程中出现的问题和解决的方法； 4.打包上交调试后的完整程序，提交实验报告； 5.实验之前写出实验报告的大概框架，实验过程中填写完整。 6.实验时携带需要上机调试的程序； 7.实验评分：实验之前预习占20%，实验报告书写情况占50%，运行情况30%。概要设计 1．栈的ADT表示 ADT Stack{ 数据对象：D={ai|ai∈ ElemSet,i=1，2，…，n,n>=0} 数据关系：R1={
括号匹配问题源代码(C语言)
括号匹配问题就是给定任意判别式，然后检验括号的配对出现的情况。 可见输入的表达式有四种可能性：右括号配对次序不正确、右括号多于左括号、左括号多于右括号、左右括号匹配正确。可以先检测表达式中的字符，若是左括号就入栈，如果是右括号就出栈一个元素与其配对，配对成功则继续访问下一个字符，否则退出。出现非括号字符则跳过。程序流程图如下：
程序代码如下： #include
C语言之符号匹配
5)：利用栈编写满足下列要求的括号匹配检验程序：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（[]（））或[（[][]）]等为正确的格式，[（]或（[（））或（（）]）均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配对。本题给出部分check()函数，要求将check()函数补充完整，并完成整个程序。 typedef char SElemType; #include"malloc.h" #include"stdio.h" #include"math.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈 Status InitStack(SqStack &S) { S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) { return ERROR; } S.top = S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) { if(S.top == S.base) return TRUE; else return FALSE; } Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize)
数据结构课程设计---括号匹配
目录 1.1 题目.................................................... 2............... 1.2 问题.................................................... 2............... 2 设计...................................................... 2 ............... 2.1 存储结构设计............................................ 2 ............. 4 对设计和编码的讨论和分析................................. 2..1. 4.1 设计................................................... 2..1.. 4.2 对编码的讨论........................................... 2..1. 5 总结和体会.............................................. 2..3 ........... 附录一 ................................................... 2..4 ............. 本科生课程设计成绩评定表.......................................... 错...误... !未定义书签 1 问题描述 .................................................................................................... 2 ............. 1.3 要求......................................................................................................... 2 .............. 2.2 主要算法设计........................................................................................... 3 ........... 2.3 测试用例及测试结果............................................................................... 6 ......... 3 调试报告 .................................................................................................... 9 .............
括号匹配问题
实验报士 括 号匹配问 题
一、实验目的： 1、熟练掌握数据结构基本知识； 2、通过括号匹配的实验，了解栈的表示和栈的基本操作，掌握栈“后进先出”的特性并能够应用这一特性。 二、实验工具：C-Free 三、实验内容： 设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如 ([( }]) 或({([][ ( ) ] ) } )等均为正确格式，而({[] )、{[()] 或([]} 等均 不正确。在算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配将栈顶的左括号出栈，否则属于不合法情况。另外，如果输入序列已读完，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的同类型的左括号，均属不合法情况。当输入序列和栈同时为空时，说明所有括号完全匹配。 四、实验过程： #include
括号匹配的检查 课程设计
衡阳师范学院 《C语言数据结构》 课 程 设 计 报 告 题目：括号匹配的检验 班级： 1 1 0 1 学号： 作者姓名： 指导教师： 2012年11月
目录 1设计题目与要求 (3) 1.1实验目的 (3) 1.2问题描述 (3) 1.3设计要求 (3) 2总体设计思想及相关知识 (3) 2.1总体设计思想 (3) 2.2开发环境与工具 (4) 3功能设计 (4) 3.1 抽象数据类型的定义 (4) 3.2 栈的基本运算 (4) 3.3栈的基本操作的实现 (4) 3.4模块流程图 (6) 4源程序代码 (6) 5测试及结果 (9) 6总结 (11) 7小组成员任务分配 (11) 参考文献 (12)
1．设计题目与要求 1.1实验目的 通过对括号匹配的检验的程序设计编写，深入了解和掌握栈的使用，了解栈先进后出的特点，掌握栈的表示和实现。 1.2问题描述 假设表达式中允许包括两种括号:圆括号和方括号，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(])或(()]）均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号序列：[ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号只能暂时靠边，而迫切等待与第二个括号相匹配的，第七个括号的出现，类似的，因等来的第三个括号，其期待的匹配程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配成了当前最急迫的任务了，······，依次类推。可见，这个处理过程恰与栈的特点相吻合。 1.3设计要求 读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。2．总体设计思想及相关知识 2.1总体设计思想 最内层（最迟出现）的左括号必须与最内层（最早出现）的同类右括号匹配，它最期待着急迫的配对。配对之后，期待得以消除。因此为左括号设置一个栈，置于栈顶的左括号期待配对的急切程度最高。另外，在算法的开始和结束时，栈都应该是空的。例如：[()[]]、 ([{}]) 、{([]]}
2栈的应用上机实验要求
?设计要求 首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 主控菜单设计要求：程序运行后，显示一个标题“判断表达式括号匹配”，标题下方给出4个菜单项的内容和输入提示： 1．输入表达式 2．输出表达式 3．判断表达式的括号是否匹配并计算表达式的值 4．退出 请选择1—4： ?功能要求 完成各菜单的功能，能正确判断表达式的括号匹配（括号限圆括弧和方括弧两种）， 若匹配，利用算符优先法计算表达式的值。 计算表达式值的3个相关函数（后面已给出，可以直接粘贴到程序中使用）: I n(c)---- //判断c是否为运算符 Precede(θ1, θ2) ----//判断两运算符θ1, θ2的优先关系 Operate(a, θ, b)---- //做四则运算a theta b，返回运算结果 ?实现要求 1)可用VC++的引用或c语言用指针实现各功能的调用 2)必须用栈实现括号匹配和表达式计算 ?实验提交要求 1)画流程图 2)实现功能的全部程序 3)说明程序设计过程中的难点、解决办法及编程小结或体会。 4)实验及报告必须于2015.4.29提交 Status In(SElemType c) //判断c是否为运算符 { switch(c) { case'+': case'-': case'*': case'/': case'(': case')': case'#': return TRUE; default: return FALSE; } }
char Precede(SElemType t1, SElemType t2) //判断两符号的优先关系{ SElemType f; switch(t2) { case'+': case'-': if(t1=='('||t1=='#') f='<'; else f='>'; break; case'*': case'/': if(t1=='*'||t1=='/'||t1==')') f='>'; else f='<'; break; case'(': if(t1==')') { printf("括号不匹配\n"); exit(OVERFLOW); } else f='<'; break; case')': switch(t1) { case'(': f='='; break; case'#': printf("缺乏左括号\n"); exit(OVERFLOW); default: f='>'; } break; case'#': switch(t1) { case'#': f='='; break; case'(': printf("缺乏右括号\n");
括号匹配(数据结构实验报告)
课程名称: 《数据结构》课程设计课程设计题目: 括号匹配 姓名:*** 院系:计算机科学与技术学院 专业:计算机科学与技术 年级:** 学号:******* 指导教师:*** 2015 年 09月 10 日
目录 1 课程设计的目的 (1) 2 需求分析 (3) 3 课程设计报告内容 (3) 3.1概要设计 (3) 3.2详细设计 (3) 3.3调试分析 (5) 4 总结 (7) 5 程序清单 (8) 6 参考文献 (7)
1.课程设计的目的 (1) 熟练使用C 语言编写程序，解决实际问题; (2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2.需求分析 本程序文件主要的功能是判断括号的匹配问题。 程序的执行是从事先输入好数据的文档中读取，然后对所读取的数据进行括号匹配行的判断。最后输出判断的结果。 程序函数主要有void InitStack(Stack *S)、ElemType GetTop(Stack S,ElemType *e)、void push(Stack *S,ElemType e)、ElemType pop(Stack *S,ElemType *e)、int Judge(ElemType a[])。InitStack函数是用来初始化栈；GetTop函数是用来获取栈顶元素；push是用来把元素压栈、pop函数是用来把元素弹出栈、Judge函数是用来判断括号是否匹配。 3 括号匹配的设计 3.1概要设计 算法分析： 首先设置好一个栈，然后从文件中读入数据，在读入的数据时，从文件中读取的字符串存入到函数定义好的字符数组中。然后把该数组作为函数参数。当每读入一个‘（’或者是‘[’，就把这个元素压栈，若是读入的元素是‘]’或者是‘）’，就调用GetTop函数，来获取栈顶元素，如果获取的栈顶元素和该次读入的元素匹配而且栈不空的话，就说明该元素是匹配的，继续比较下一次的元素；如果获取的栈顶元素和该次读入的元素不匹配的话，就说明该元素是不匹配的，直接结束运行。当所有的‘）’或者是‘]’全部比较完成之后，栈仍然不空，说明栈中还剩有‘[’或者‘(’，括号不匹配。 3.2详细设计 void InitStack(Stack *S)//建造一个栈 { S->base = (ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType)); if(!*S->base) printf("error"); S ->top = S ->base;//将栈设置为空栈 S->stacksize = STACK_INIT_SIZE;//将栈的空间大小设置为STACK_INIT_SIZE } 建栈的操作首先将栈指针s->指向新开辟的内存空间。然后将栈顶指针s->top等于s->base。将栈置成空栈。 ElemType GetTop(Stack S,ElemType *e)//获取栈顶元素 { if(S.top!=S.base) { *e=*(S.top-1); return *e; }
《C数据结构》括号匹配实验报告
括号匹配 实验目的： 使用堆栈的存储结构实现括号匹配，即“（”与“）”必须成对出现、“[”与“]”必须成对出现 实验思路： 1、写出堆栈的相关操作函数，如： 创建【int InitStack( SqStack *S )】、 压入【int Push(SqStack *S,int e)】、 弹出【int Pop(SqStack *S,int *e)】、 销毁【void DestroyStack(SqStack *S)】、 判断是否为空【int StackEmpty(SqStack *S)】等。 2、堆栈的各操作函数完成后编写功能函数——括号匹配函数【int match(char *str)】。 3、括号匹配函数之后编写主函数，使用上述函数实现括号匹配的功能 核心代码： 1、括号匹配函数： int match(char *str){ int i,e; SqStack S; InitStack(&S); for(i=0;;i++){ if(str[i]=='\0')break; if(str[i]=='('||str[i]=='['){ Push(&S,str[i]); }; if(str[i]==')'){ Pop(&S,&e); if(e=='('){ continue; }else{ Push(&S,e); } } if(str[i]==']'){ Pop(&S,&e); if(e=='['){ continue; }else{ Push(&S,e); } }
} if(StackEmpty(&S)){ printf("恭喜您，括号匹配成功,多项式格式合法！\n"); }else{ printf("警告：多项式格式不合法！\n"); } DestroyStack(&S); return 1; } 2、主函数： int main(){ char str[100]; printf("请输入一个表达式："); scanf("%s",&str); match(str); system("pause"); return 1; } 功能演示： 1、输入：（3+45）*[32-5]/[2-5] 输出：恭喜您，括号匹配成功,多项式格式合法！
实验 表达式括号匹配配对判断问题
实验表达式括号匹配配对判断问题 姓名：贾柯柯班级：计162 学号：1613023052 实验时间：2017.10.28 1.问题描述 一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。 2.数据结构设计 匹配判别发生在右括号出现时，且被匹配的左括号应是距离右括号最近被输入的，二不是最先被输入的括号，即“先入后匹配”。因此用栈来解决。 #define stacksize 100 //定义栈的空间大小 struct stack{ //定义栈的结构体 char strstack[stacksize];//定义栈的存储格式为字符型 int top; //定义栈的栈顶变量 }; void InitStack(stack &s) {//定义一个新栈s，初始化栈顶为-1 s.top = -1; } 3.算法设计 （1）入栈的算法 char Push(stack &s, char a) { //入栈操作，将字符a入栈s if(s.top == stacksize - 1) //当栈顶为栈的空间大小-1，栈满 return 0; s.top ++;//入栈操作一次，栈顶+1 s.strstack[s.top] = a;//此时，栈顶元素为字符a return a; } 2）出栈的算法设计 char Pop(stack &s ) { //出栈操作 if(s.top == -1) //当栈顶为-1时，栈空 return 0; char a = s.strstack[s.top];//将栈顶元素赋予字符a，并返回字符a，完成出栈操作 s.top--; return a; } （3）判断栈是否为空的函数 int Empty(stack &s,int re) { //定义判断栈是否为空的函数 if(s.top==-1) return 1;//栈为空时返回值为1
课程设计报告——括号匹配问题
课程设计报告——括号匹配问题
————————————————————————————————作者：————————————————————————————————日期: ?
1. 设计目的 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构,并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。学生通过上机实习,验证自己设计的算法的正确性。学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改。 3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。 4、训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。 5、培养根据选题需要选择学习书籍,查阅文献资料的自学能力。 2．设计内容 2.1 系统名称 括号匹配问题:括号匹配问题就是给定任意判别式，然后检验括号的配对出现的情况。 2.2要求 假设一个算术表达式中可包含三种括号：圆括号、中括号、花括号且这三种括号可按任意次序嵌套使用。试利用栈的运算，编写判别给定式中所含括号是否正确配对出现的算法。 任意运用一种计算机语言，分析问题，写出具体程序，要求能够在对应的系统中实现该问题的，实验通过计算机来完成。 独立完成,可通过查阅资料来解决自己不会的问题，提高自己查阅文献的能力级独立思考的能力。
3.程序设计步骤 ３.１ 程序流程分析图 图３-1 程序流程图 3.2 主要的数据结构类型 typed ｅｆ ｓt ｒuc ｔ ｛ ? int ｔｏp; ch ａr S ｚｓｔａck[Max Ｓiz ｅ]; }Text; 开给定判断 检验 左右入找栈 配对删除不配对，则栈空 栈不 结
括号匹配的检验
湖南工学院 计算机与信息科学系 课程设计报告 2010—2010学年第一学期 课程名称——数据结构 设计题目——括号匹配的检验 姓名—— 专业班级—2 学号—— 2010 年12 月31 日
目录 1 设计任务书……………………………… 1.1 题目与要求……………………………………………… 1.2 设计中涉及的知识点…………………………………… 2 功能设计………………………………… 2.1抽象数据类型的定义……………………………………… 2.2 模块流程图……………………………………………… 3 程序代码设计与说明…………………… 3.1 子程序设计与其功能…………………………………… 3.2 主函数设计与其功能…………………………………… 4 程序设计总结…………………………… 4.1 程序调试情况…………………………………………… 4.2 个人经验及体会………………………………………… 5 用户使用说明……………………………6测试结果………………………………… 7 附录（源程序）…………………………
1 设计任务书 1.1 题目与要求 [问题描述] 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或[（[ ] [ ]）]等为正确格式，[（]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用 “期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： [([][])] 12345678 当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个 括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，……，依次类推。可见这个处理过程正好和栈的特点相吻合。 [基本要求] 读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。 1.2 设计中涉及的知识点 编译预处理（文件包含）、选择结构、循环结构、堆栈、函数 2 功能设计 2.1抽象数据类型的定义 包括堆栈的定义