括号匹配课程设计报告

1．实验题目括号匹配的检验；2．需求分析本演示程序用VC++6.0编写，完成圆括号、方括号和大括号，其嵌套的顺序随意，即（（）[ ]）或{（[ ] [ ]）}等为正确格式，[[ ）]或（（（）均为不正确的格式。

①输入形式：直接输入一串括号；②输出形式：直接输出输入的括号串是否匹配的结果；③程序所能达到的功能：可以多次输入括号串并判断其是否匹配；④测试数据：输入（[ ]（）），结果“匹配”输入 [（ [）]，结果“此串括号匹配不合法”3．概要设计1）为了实现上述程序功能，需要定义栈的抽象数据类型：class Stack{数据对象：kh={ai|ai∈count,i=0,1,2,…,n,n≥0}数据关系：基本操作：push(char b)操作结果：把一个数据压进栈pop()操作结果：把一个数据弹出栈pp(char c[])初始条件：栈已存在操作结果：将栈中的元素进行匹配jc()初始条件：栈已存在操作结果：检查栈是否为空若空，返回0；若不空，返回1.clear()操作结果：清空栈2）本程序包含7个函数：①主函数main()②栈的构造函数Stack()③压栈操作函数push(char b)④弹栈操作函数pop()⑤匹配元素函数pp(char c[])⑥检查栈操作函数jc()⑦清空栈操作函数clear()各函数间关系如下：4．详细设计#include<iostream>#include<string>using namespace std;const int maxstack=100;//-------------------------------------------------------------------class Stack{//栈类public:Stack(){count=-1;};//初始化计数conutvoid push(char b);//压栈char pop();//弹栈void pp(char c[]);//匹配括号int jc();//检查是否为空栈void clear(){count=-1;}private:int count;//计数char a[maxstack];//存储};void Stack::push(char b)//压栈函数{if(count>=maxstack);else{count++;a[count]=b;}}char Stack::pop()//弹栈函数{if(count<0);else{return a[count--];}return 0;}int Stack::jc()//检查函数{if(count<0)return 0;return 1;}void Stack::pp(char c[])//匹配函数{int i=0,s=1,t;t=strlen(c);//测试输入的字符串长度if(c[0]==')'||c[0]==']'||c[0]=='}'||t%2==1)//判断是否为奇个括号或第一个为左括号{cout<<"此串括号匹配不合法"<<"\n"<<endl;}else //判断{while(c[i]!='\0'){if(c[i]=='('||c[i]=='['||c[i]=='{'){push(c[i]);}else{if(c[i]==')'){if(pop()!='('){s=0;break;}}if(c[i]==']'){if(pop()!='['){s=0;break;}}if(c[i]=='}'){if(pop()!='{'){s=0;break;}}}i++;}if(s==1){ if(!jc())cout<<"匹配"<<"\n"<<endl;else cout<<"此串括号匹配不合法"<<"\n"<<endl;}if(s==0)cout<<"此串括号匹配不合法"<<"\n"<<endl;}}//-------------------------------------------------------------------int main(){char a[maxstack];//数组Stack kh;//栈对象char h;cout<<"**************************"<<endl;cout<<"*** 括号匹配测试程序 ***"<<endl;cout<<"**************************"<<endl<<endl;do{cout<<"请输入您的选择: 1.运行程序; 2.结束。

深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：堆栈应用括号匹配实验学院：计算机与软件学院专业：未分指导教师：杨芳报告人：姜家祥学号：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}-1：左右括号配对次序不正确{[(1+2]*3)-1}-2：右括号多于左括号(1+2)*3)-1}-3：左括号多于右括号{[(1+2)*3-1]6、输出样本-1-2-3（二）数制转换1、问题描述对于任意十进制数转换为k进制，包括整数部分和小数部分转换。

《数据结构》实验报告二实验内容：括号匹配学号：姓名：一、上机实验的问题和要求（需求分析）：[ 题目] 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或[（[ ] [ ]）] 等为正确格式，[（]）或（（（]均为不正确的格式。

读入含圆括号和方括号的符号序列，输出“匹配”或“此串括号匹配不合法”。

二、程序设计的基本思想，原理和算法描述：本程序是在实现栈的基本操作的基础上实现其基本应用，即括号匹配问题，重点利用其“先进后出”的特性三、调试和运行程序过程中产生的问题及采取的措施：（略）四、源程序及注释[ 源程序] 程序名： 4.cpp#include "stdio.h"#include "malloc.h"#include "process.h"#define stack_int_size 8#define stackincrement 10#define overflow -2#define error 0#define ok 1typedef int status;typedef char selemtype;typedef struct{ selemtype * base;selemtype * top;int stacksize;}sqstack;status initstack(sqstack &s){//构造一个空栈ss.base=(selemtype *)malloc(stack_int_size * sizeof(selemtype));if(!s.base)exit(overflow);s.top=s.base;s.stacksize=stack_int_size;return ok;}//initstackstatus emptystack(sqstack s){if(s.top==s.base)return ok;else return error;}status push(sqstack &s,selemtype e){//插入元素e为新的栈顶元素int stacksize;if(s.top-s.base>=s.stacksize){s.base=(selemtype *)realloc(s.base, (s.stacksize+stackincrement )* sizeof(selemtype));if(!s.base)exit (overflow);s.top=s.base+s.stacksize;s.stacksize+=stackincrement;}*s.top++=e;return ok;}//pushstatus pop(sqstack &s,selemtype &e){//若栈不为空，则删除s的栈顶元素，用e返回其值if(s.top==s.base)return error;e=* --s.top;return ok;}//popint kuohao(char m[]){ //若括号匹配则返回1，否则返回0；sqstack s;int i=0;char x;initstack(s);while(m[i]!='#'){ if(m[i]=='('||m[i]=='[')push(s,m[i]);if(m[i]==')'||m[i]==']'){ if(emptystack(s))return 0;else{pop(s,x);if((x=='('&&m[i]==']')||(x=='['&&m[i]==')'))return 0; } }i++;}if(emptystack(s))return 1;else return 0;}void main (){ char e[7]={'(','(','(',']',')',']','#'};int p;p=kuohao(e);printf("说明：若括号匹配的话，输出结果为1，反之则为0.\n");printf("判断结果为：%d\n",p); }五、运行结果如输入的括号序列为：'(','(','(',']',')',']','#'运行结果：0（表明括号不匹配）。

编写一个括号匹配的检验的程序实习报告在计算机科学领域，括号匹配是一个常见的问题。

括号匹配指的是在一个字符串中，所有的括号都必须正确地成对出现。

如果所有的括号都能正确地匹配，那么该字符串是合法的；否则，该字符串是非法的。

在本次程序实习中，我设计并实现了一个括号匹配的检验程序。

首先，我对括号匹配的问题进行了深入的研究和分析。

我发现，括号匹配问题可以通过使用栈来解决。

栈是一种遵循后进先出原则的数据结构，在括号匹配问题中非常适用。

我使用了一个栈来存储左括号，并在遍历字符串时进行匹配操作。

接下来，我实现了一个简单而高效的括号匹配检验程序。

该程序可以接收一个字符串作为输入，并判断该字符串中的括号是否匹配。

我使用了编程语言（例如C++或Python）来实现该程序，具体的实现细节如下：1. 首先，我创建了一个空栈，用来存储左括号。

2. 然后，我遍历输入的字符串，逐个检查每个字符。

3. 如果当前字符是左括号（例如'('、'{'或'['），则将其推入栈中。

4. 如果当前字符是右括号（例如')'、'}'或']'），则检查栈是否为空。

如果栈为空，则字符串中的右括号没有相应的左括号，该字符串是非法的；如果栈不为空，则将栈顶的左括号弹出并与当前的右括号进行匹配。

如果两个括号不匹配，那么该字符串是非法的。

5. 最后，当遍历完整个字符串后，检查栈是否为空。

如果栈为空，则说明所有的左括号都有相应的右括号，该字符串是合法的；如果栈不为空，则说明字符串中存在未匹配的左括号，该字符串是非法的。

通过实现这个括号匹配的检验程序，我学到了许多关于栈的知识和算法设计的技巧。

此外，我也加深了对括号匹配问题的理解和掌握。

通过编写和调试这个程序，我提高了自己的编程能力和解决问题的能力。

总的来说，本次括号匹配的检验程序实习让我深入了解了括号匹配问题，并通过实际动手编写代码来解决这个问题。

实验表达式括号匹配配对判断问题姓名：班级：学号：实验时间：1.问题描述一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。

写一程序，判断任一算术表达式中所含括号是否正确配对。

2.数据结构设计匹配判别发生在右括号出现时，且被匹配的左括号应是距离右括号最近被输入的，二不是最先被输入的括号，即“先入后匹配”。

因此用栈来解决。

#define stacksize 100 //定义栈的空间大小structstack{ //定义栈的结构体char strstack[stacksize];//定义栈的存储格式为字符型int top; //定义栈的栈顶变量};void InitStack(stack &s){//定义一个新栈s，初始化栈顶为-1s.top = -1;}3.算法设计（1）入栈的算法char Push(stack &s, char a){ //入栈操作，将字符a入栈sif(s.top == stacksize - 1) //当栈顶为栈的空间大小-1，栈满return 0;s.top ++;//入栈操作一次，栈顶+1s.strstack[s.top] = a;//此时，栈顶元素为字符areturn 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;//栈为空时返回值为1elsereturn 0;//栈不为空时返回值为0}（4）判断是否匹配的算法。

如果右括号，进栈，取下个字符；如果是左括号，出栈，取下个字符；最后判断栈是否为空。

编写一个括号匹配的检验的程序1．实验题目编写一个括号匹配的检验的程序2．需求分析本演示程序用C++编写，完成圆括号、方括号和大括号（选作）的匹配检验，即当输入一串括号后能够判断出此串括号匹配是否合法。

①输入形式和输入范围：括号以字符串形式输入，只输入圆括号、方括号和大括号三种括号，三种括号可以随意嵌套。

②输出形式及功能：当输入任意一串括号后，都会做出判断，输出输入的括号串是否合法。

③测试数据：输入（[ ]（）），结果“匹配”输入 [（] ），结果“此串括号匹配不合法”3．概要设计1）为了实现上述程序功能，需要定义压栈数据类型：stack<char> openings{数据对象：（symbol∈“（”，“）”，“[”，“]”，“{”，“}”）数据关系：“（”==“）”，“[”==“]”，“{”“}”基本操作：while (is_matched &&(symbol=cin.get())!='\n')操作结果：对括号进行压栈比较，判断下一步是压栈还是弹栈配对。

基本操作：is_matched（）操作结果：判断括号是否匹配，在屏幕打印出。

}2）本程序包含3个函数：①主函数main()②压栈弹栈函数symbol=cin.get()③括号匹配比较函数is_matched（）各函数间关系如下：mainsymbol=cin.getis_matched4．详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。

对主程序和其他模块也都需要写出伪码算法。

（1）括号输入while (is_matched &&(symbol=cin.get())!='\n')（2）括号匹配检验is_matched=(5．调试分析（1）由于本程序是通过书本上伪代码改编而来，所以编写时比较简单，程序语把不匹配时的空栈这一点去掉，经过验证我的设计正确，解决了问题，实现了括号匹配的检验程序。

实验三实验报告括号匹配的检验实验题⽬：括号匹配的检验⼀、实验⽬的加深理解栈的定义和特性；掌握栈的存储结构与实现⼆、实验内容：任意输⼊⼀个由若⼲个圆括号、⽅括号和花括号组成字符串，设计⼀个算法判断该串中的括号是否配对。

三、设计与编码1、基本思想基本思想：最内层(最迟出现)的左刮号必须与最内层(最早出现)的同类右刮号配对，它最急切地期待着配对。

配对之后, 期待得以消解。

因此为左刮号设置⼀个栈，置于栈顶的左刮号期待配对的急切程度最⾼。

实例：[ ( [ ] { } ) ]、( [ { } ] )、{ [ ] } )、( { [ ] }、( { [ ] ] )2、编码#include#includeconst int StackSize=100;class SeqStack{public:SeqStack(){top=-1;}~SeqStack(){}void Push(char s);char Pop();void Peidui(char s[StackSize]);private:char data[StackSize];int top;};void SeqStack::Push(char s){if(top==StackSize-1) throw"上溢";top++;data[top]=s;char SeqStack::Pop(){if(top==-1)throw"下溢";else{char a;a=data[top--];return a;}}void SeqStack::Peidui(char *s){int i=0,l=strlen(s);char t;for(i=0;i{if(s[i]=='{'||s[i]=='['||s[i]=='(')Push(s[i]);else{if(top==-1){cout<<"右括号多了,不匹配"<return;}else{t=data[top];if(t=='{'&&s[i]=='}'||t=='['&&s[i]==']'||t=='('&&s[i]==')') {Pop();}elsebreak;}}if(top==-1&&s[i]=='\0')cout <<"配对成功"<elseif(top!=-1&&s[i]=='\0')cout<<"左括号多了,不匹配"<elsecout<<"左右类型不匹配"<}void main(){char str[10];cout<<"请输⼊括号；"<cin>>str;SeqStack S;S.Peidui(str);}四、调试与运⾏1、调试时遇到的主要问题及解决2、运⾏结果（输⼊及输出，可以截取运⾏窗体的界⾯）五、实验⼼得。

括号匹配问题栈c语言实验报告
一、实验目的
(1)掌握用C语言调试程序的基本方法。

(2)掌握栈的基本定义及其存储实现。

(3)掌握栈的常见算法的程序实现。

(4)掌握栈在实际问题背景下的灵活应用。

二、实验内容
算术表达式中右括号和左括号匹配的次序正好符合后到括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借用一个堆栈来进行判断。

具体方法：
⑴顺序扫描算术表达式（表现为一个字符串）；
⑵当遇到三种类型的左括号时，让该括号进栈；
⑶当遇到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，
⑷若匹配则退栈，转（1）继续进行判断；
⑸若不匹配，则左右括号配对次序不正确，结束。

⑹若字符串当前为某一类型的右括号而堆栈为空，则右括号多于左括号，结束。

⑺若字符串扫描结束而堆栈非空，则左括号多于右括号，结束。

⑻若字符串扫描结束而堆栈为空，则左右括号匹配正确，结束。

三、实验要求
(1)程序要添加适当的注释，程序的书写要采用缩进格式。

(2)程序要具备一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。

(3)程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

(4)根据实验报告模板详细书写实验报告（程序调试成功的，需将运行结果截图附在实验报告里面；实验报告以pdf格式或者.doc格式/.docx格式上传）。

(5)将源程序(.c或者.cpp)压缩为一个文件（如果自定义了读、写文件则一起压缩）上传，扩展名为：.rar或.zip。

四、实验环境
Windows 10，Microsoft Visual C++2010 Express。

括号匹配检测实验报告本实验旨在设计和实现一个括号匹配检测算法，检测给定字符串中的括号是否正确匹配。

实验原理：括号匹配检测是一种常见的算法问题。

其基本原理是利用栈（Stack）数据结构进行括号的匹配。

当遇到左括号时，将其入栈；当遇到右括号时，判断栈顶元素是否与其对应的左括号相匹配，若匹配则将栈顶元素出栈，继续检测下一个字符；若不匹配，则说明括号不正确匹配，返回匹配失败；最后，若栈为空，则说明所有括号都正确匹配，返回匹配成功。

实验步骤：1. 设计栈数据结构及括号匹配检测算法。

2. 实现算法代码。

3. 设计测试用例，包括正确匹配和不正确匹配的字符串。

4. 运行测试用例，检测算法的正确性和效率。

5. 分析实验结果并撰写实验报告。

实验代码：以下是一个用Python语言实现的括号匹配检测算法示例代码：pythonclass Stack:def __init__(self):self.stack = []def is_empty(self):return len(self.stack) == 0def push(self, element):self.stack.append(element)def pop(self):if not self.is_empty():return self.stack.pop()else:return Nonedef peek(self):if not self.is_empty():return self.stack[-1]else:return Nonedef bracket_match(string):stack = Stack() # 创建栈对象brackets = {'(': ')', '[': ']', '{': '}'}for char in string:if char in brackets: # 左括号入栈stack.push(char)elif char in brackets.values(): # 右括号与栈顶元素匹配if stack.is_empty():return Falseif brackets[stack.peek()] == char:stack.pop()else:return Falsereturn stack.is_empty()# 测试用例test_cases = ["()", "{[]}", "[{()}]", "(}", "{[}]"]for test_case in test_cases:if bracket_match(test_case):print(test_case, "匹配成功")else:print(test_case, "匹配失败")实验结果：运行测试用例，可以得到以下结果：- "()" 匹配成功- "{[]}" 匹配成功- "[{()}]" 匹配成功- "(}" 匹配失败- "{[}]" 匹配失败实验讨论：根据实验结果，我们可以看到算法能够正确地检测出括号的匹配情况。