数据结构实验 表达式括号匹配配对判断问题概览

一、实验目的本次实验旨在通过编写程序实现括号匹配功能，加深对栈数据结构原理的理解和应用。

通过实验，掌握栈的基本操作，如入栈、出栈、判断栈空等，并学会利用栈解决括号匹配问题。

二、实验原理1. 栈是一种后进先出（LIFO）的线性数据结构，它只允许在栈顶进行插入和删除操作。

2. 括号匹配问题是指在一个字符串中，判断左右括号是否成对出现，且对应匹配。

3. 在解决括号匹配问题时，可以使用栈来存储遇到的左括号，并在遇到右括号时进行匹配。

如果栈为空或括号不匹配，则判断为无效括号。

如果栈为空，表示括号匹配正确，否则表示不匹配。

三、实验内容1. 定义栈结构体，包括栈的最大容量、栈顶指针、栈底指针、栈元素数组等。

2. 编写栈的基本操作函数，如初始化、入栈、出栈、判断栈空等。

3. 编写括号匹配函数，利用栈实现括号匹配功能。

4. 编写主函数，接收用户输入的字符串，调用括号匹配函数进行判断，并输出结果。

四、实验步骤1. 定义栈结构体和栈的基本操作函数。

```c#define MAX_SIZE 100typedef struct {char data[MAX_SIZE];int top;} Stack;void InitStack(Stack s) {s->top = -1;}int IsEmpty(Stack s) {return s->top == -1;}void Push(Stack s, char x) {if (s->top == MAX_SIZE - 1) { return;}s->data[++s->top] = x;}char Pop(Stack s) {if (s->top == -1) {return '\0';}return s->data[s->top--];}```2. 编写括号匹配函数。

```cint BracketMatch(char str) {Stack s;InitStack(&s);while (str) {if (str == '(' || str == '[' || str == '{') {Push(&s, str);} else if (str == ')' || str == ']' || str == '}') {if (IsEmpty(&s)) {return 0; // 不匹配}char c = Pop(&s);if ((c == '(' && str != ')') || (c == '[' && str != ']') || (c == '{' && str != '}')) {return 0; // 不匹配}}str++;}return IsEmpty(&s); // 栈为空，匹配成功}```3. 编写主函数。

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

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

二、程序设计的基本思想，原理和算法描述：本程序是在实现栈的基本操作的基础上实现其基本应用，即括号匹配问题，重点利用其“先进后出”的特性三、调试和运行程序过程中产生的问题及采取的措施：（略）四、源程序及注释[ 源程序] 程序名： 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（表明括号不匹配）。

数据结构计算器实验报告数据结构计算器实验报告引言：数据结构是计算机科学中非常重要的一门课程，它研究了数据的组织、存储和管理方式，以及对数据进行操作和处理的算法和技术。

在本次实验中，我们设计了一个基于数据结构的计算器，旨在通过实践应用数据结构的知识，提高我们的编程能力和算法思维。

一、设计思路我们的计算器主要有两个功能：进行四则运算和进行括号匹配。

为了实现这两个功能，我们选择了栈这一数据结构。

栈是一种具有后进先出（LIFO）特点的数据结构，非常适合用来处理括号匹配和运算符的优先级。

二、括号匹配算法在进行四则运算之前，我们首先需要对输入的表达式进行括号匹配的检查。

我们使用了一个栈来实现这一功能。

算法的基本思路是，遍历表达式中的每个字符，当遇到左括号时，将其入栈；当遇到右括号时，将栈顶元素出栈，并判断出栈的元素是否与当前右括号匹配。

如果匹配，则继续遍历下一个字符；如果不匹配，则说明表达式存在括号不匹配的错误。

三、四则运算算法当表达式通过了括号匹配的检查后，我们就可以进行四则运算了。

我们使用两个栈来实现这一功能，一个栈用来存储操作数，另一个栈用来存储运算符。

算法的基本思路是，遍历表达式中的每个字符，当遇到数字时，将其入操作数栈；当遇到运算符时，将其入运算符栈，并根据运算符的优先级进行相应的操作。

四、运算符优先级为了正确计算表达式的值，我们需要定义运算符的优先级。

一般来说，乘法和除法的优先级高于加法和减法。

为了实现这一功能，我们可以使用一个优先级表来存储运算符的优先级。

在进行运算时，我们可以通过比较栈顶运算符和当前运算符的优先级来决定是否进行运算。

五、实验结果经过我们的努力，我们成功地实现了一个基于数据结构的计算器。

我们对该计算器进行了多组测试，包括括号匹配、四则运算等不同情况。

在所有的测试中，我们的计算器都能正确地输出结果，并且在处理大规模表达式时也能保持较好的性能。

六、总结与展望通过本次实验，我们深入理解了数据结构的应用和算法的设计。

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

三、设计与编码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、运⾏结果（输⼊及输出，可以截取运⾏窗体的界⾯）五、实验⼼得。

数据结构实验（括号配对问题）⼀、实验题⽬设计算法判断⼀个算数表达式的圆括号是否正确配对。

⼆、问题分析这道题⽤到的是栈的知识，这个程序要求我们知道如何对⼀个字符串进⾏存储，判断算数表达式是否配对正确的关键是对表达式进⾏扫描，熟悉圆括号的进出栈操作。

三、概要设计1)为了实现上述程序功能，需要：[1]建⽴⼀个顺序栈；[2]键盘输⼊⼀个表达式，并对其进⾏扫描；[3]当扫描到“（”就进⾏⼊栈操作，遇到“）”就将栈顶元素出栈，扫描到其他元素不进⾏任何操作；[4]扫描完表达式，判断栈是否为空。

若为空，则匹配正确，反之错误。

2)本程序包含的函数：[1]主函数main()[2]void Bracket()四、详细设计1)定义顺序栈类型Typedefstruct{Char stack[StackMaxSize];Int top;}Stack;2） [1]⾸先将定义⼀个栈S置成空栈，InitStack(S)；[2]然后在main()⾥定义字符串str[100],并将其输⼊gets(str)；[3]接着利⽤while（str[i]!=’\0’）语句对字符串进⾏扫描[4]如果遇到“（“就执⾏push(S,’(‘)操作，遇到”)“就进⾏删除栈顶元素操作；[5]最后判断栈是否为空，StackEmpty(S)。

五、调试分析在⼀开始的试验中，在判断括号是否判断正确的if语句中if(!flag1&&flag2),这样得到的结果就不正确了，如图：解决⽅法：将判断括号配对是否正确的if语句中if(!flag1&&flag2)改为if（！flag2）这样只要判断flag2标志的栈是否为空，从⽽得到括号是否配对正确。

六、测试结果：1）测试数据：4+（4+5），））（（，）+（），）+（）+（2）测试结果截图：七、附录（源代码）#includevoid Bracket(char *str);void main()//主函数{char str[100];//定义⼀个字符串printf("please input:");gets(str);Bracket(str);}#define StackMaxSize 100 typedefstruct{//定义⼀个顺序栈类型char stack[StackMaxSize]; int top;}Stack;Stack *InitStack(Stack *S)//置空栈{S->top=-1;return S;}intStackEmpty(Stack *S)//判栈空{return S->top==-1;}char Pop(Stack *S,char *a)//顺序栈取栈顶元素{*a=S->top;if(S->top<=StackMaxSize-1&&S->top>=0) return(S->stack[S->top]);elseprintf("error");}void Push(Stack *S,charstr){//顺序栈⼊栈if(S->toptop>=-1){ S->top++;S->stack[S->top]=str;}elseprintf("error");}void Bracket(char *str){Stack S1,*S=&S1char a;inti=0,flag1=0,flag2;InitStack(S);while(str[i]!='\0'){switch(str[i]){case '(':Push(S,'(');break;case ')':Pop(S,&a);if(a!='('){flag1=1;break;//出现不匹配，⽴即结束循环}default:break;}if(flag1)break;i++;}flag2=StackEmpty(S);//flag2判断堆栈是否为空if(!flag2) printf("括号匹配正确\n");elseprintf("括号匹配不正确\n");}。

合肥学院计算机科学与技术系课程设计报告2008~2009学年第二学期2009年5月题目：表达式的括号匹配检验问题。

试验完成如下要求：假设在表达式中允许有三种括号：圆括号、方括号和花括号，其嵌套的顺序是随意。

要求设计测试数据，如果在表达式中括号使用正确，输出结果为“此表达式中括号匹配合法”，否则输出结果为“此表达式中括号匹配不合法”，#为表达式的起始和结束标志。

在初始和结束时，栈为空。

一、问题分析和任务定义此程序需要完成如下要求：表达式中允许有三种括号：圆括号、方括号和花括号，嵌套顺序随意。

要求设计测试数据，判断表达式中括号使用是否正确，如果正确，输出结果为“此表达式中括号匹配合法”，否则输出结果为“此表达式中括号匹配不合法”，表达式的输出格式为：“#表达式#”。

实现本程序需要解决的几个问题：1、用什么数据结构。

2、怎样实现判断括号是匹配的。

3、括号匹配与不匹配有几种情况。

4、输出与输入数据的形式。

本程序的难点在于怎么样判断括号是否匹配。

按任务书中的提示，首先，建立一个栈，用来存储读入的括号。

若是左括号，则做为一个新的更急迫的期待压入栈，若是右括号，则和当前栈顶的括号比较，若匹配，则输出此表达式中括号匹配合法，若不匹配，则输出此表达式中括号匹配不合法。

括号分为大括号，小括号，中括号，每个括号比较的方法是一样的。

如输入为#(3+2)#:输入#，输入（，“输入3+2，输入“）”，是右括，是左括号，入栈号“（”出栈，与“）”比较，匹配，栈空图1 具体实例演示括号匹配过程由于本程序要求表达式的输入形式是#表达式#，#是表达式的起始与结束的标志，所以判断表达式遍历完的条件是读到第二个#号。

总的来说本题目是一个以栈为数据结构，设计一个求有关于表达式中括号匹配的问题的程序。

数据类型应为字符型，需要自定义栈的结构体，初始栈，入栈，出栈，判断栈空的操作。

本程序用的是顺序栈，用地址连续的存储空间依次存储栈中的元素，并记录当前栈顶数据元素的位置，这样的栈称为顺序栈。

括号的匹配1. 需求和规格说明（1）实现括号的是否匹配的判定。

（2）实现匹配错误的提示。

（3）实现栈内容的动态显示。

2．设计2.1．设计思想（1）对于括号匹配的判定，首先输入字符串到缓冲区。

逐个字符读取字串，遇到的是左括号则入栈，若是右括号，则出栈。

出栈的左括号如果和右括号匹配，则一对括号匹配成功；否则，这对括号匹配失败，并给出错误提示。

（2）分析括号匹配错误出现的情况，主要有三种：左括号数大于右括号数，左括号与右括号不匹配，右括号数大于左括号数。

根据栈的存储情况就能判定出这三种情况，并且实时的将信息放映到可视化控件上。

（3）对于匹配过程和栈内容的动态显示，可以用listbox 控件实时的显示和更新。

窗口上有两个listbox 控件，第一个动态显示push 和pop 动作以及提示错误信息；第二个listbox 则动态模拟栈内的存储情况。

2.2．设计表示（1）存储结构Node 节点template <class element>class Node{public:element ele;Node *pre; // 前驱指针Node *next; //后继指针Node(){pre=NULL; next=NULL;}Node(element e){ele=e;pre=NULL;next=NULL;}Node * MakeNode(element e)//传入参数返回一个节点指实现参数的封装针，{Node<element> *temp=new Node(e); return temp;}};MyListStack 链栈template <class element> class MyListStack{public:Node<element> *base;Node<element> *top;int index;MyListStack() //初始化链表{base=new Node<element>(); top=base;index=0;}void push(element n) //push{Node<element> *temp=new Node<element>(n); top->next=temp;temp->pre=top;top=temp; index++;}void pop(element & out) //pop{ out=top->ele; top=top->pre; delete top->next; top->next=NULL; index--;}BOOL isEmpty(); //返回栈是否为空{if(index) return FALSE;else return TRUE;}virtual ~MyListStack() //析构链栈，释放空间{Node<element> *p=base; Node<element> *q=p->next;while(p->next!=NULL){ delete p; p=q; q=p->next;} delete p;}};(2)涉及的操作void CKuohaopipeiDlg::OnButtonClear() // 清空窗口控件。

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

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

其基本原理是利用栈（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, "匹配失败")实验结果：运行测试用例，可以得到以下结果：- "()" 匹配成功- "{[]}" 匹配成功- "[{()}]" 匹配成功- "(}" 匹配失败- "{[}]" 匹配失败实验讨论：根据实验结果，我们可以看到算法能够正确地检测出括号的匹配情况。

括号匹配实验报告实验报告课程名称：数据结构班级：实验成绩：实验名称：栈、队列、字符串和数组学号：批阅教师签字：实验编号：实验⼆姓名：实验⽇期：指导教师：组号：实验时间：⼀、实验⽬的（1）掌握栈、队列、串和数组的抽象数据类型的特征。

（2）掌握栈、队列、串和数组的抽象数据类型在计算机中的实现⽅法。

（3）学会使⽤栈、队列来解决⼀些实际的应⽤问题。

⼆、实验内容与实验步骤（1）实验内容：假设表达式中除了变量名、常量和运算符外，还可以允许两种括号：圆括号和中括号，其嵌套的次序随意，编写程序检验输⼊的表达式中括号的的顺序是否合法。

（2）描述抽象数据类型或设计的函数描述，说明为什么要使⽤这种抽象数据类型，并说明解决设想。

抽象数据类型或函数描述：⾸先定义了⼀个结构体并且声明为栈类型，在其中定义了空间基地址的指针、栈顶指针以及栈存储空间的⼤⼩。

之后设计了Creat _Stack的函数，⽤此函数来创建⼀个空栈，这样可以使⽤堆栈来实现括号匹配的功能，⼜设计了⼀个名为Stack_Full的函数了来判断栈是否已满，若栈未满才可继续之后的压栈功能，如果堆栈已满，则需要使⽤realloc来动态分配空间，扩⼤栈的存储空间。

我还设计了⼀个名为empty的函数，⽤它来判断堆栈是否为空，堆栈为空或不为空时分别返回0或1。

之后设计了名为push和pop的函数来实现括号的⼊栈和出栈，之后设计了名为Match的函数，来判断括号是否匹配，设计了名为clean的函数来清空堆栈，这样可以连续判断不同的多项式的括号是否匹配。

解决设想：对于本题，⾸先我使⽤了栈结构，利⽤栈中数据“先进后出”的特点来实现对括号是否匹配的检验。

实现过程基本如下：从左到右依次扫描多项式，如果遇到左括号便将左括号⼊栈，在所有左括号⼊栈之后便可以扫描到右括号，如果扫描到的右括号和栈顶的左括号可以匹配时，将左括号出栈，以此类推，最后判断栈是否为空，若为空，则括号匹配，否则括号不匹配。

第1篇实验名称：括号匹配检测实验目的：1. 理解括号匹配的基本原理。

2. 掌握使用栈进行括号匹配检测的方法。

3. 通过编程实现括号匹配检测功能。

实验时间：2023年X月X日实验地点：实验室实验器材：1. 计算机2. 编程软件（如Python、Java等）3. 文档编辑器实验内容：一、实验原理括号匹配检测是计算机科学中的一个基础问题，它涉及到字符串中括号的正确配对。

常见的括号包括圆括号()、方括号[]和花括号{}。

一个有效的括号序列是指，序列中的每个左括号都有一个对应的右括号，并且括号内的内容可以嵌套。

括号匹配检测通常使用栈（Stack）这一数据结构来实现。

栈是一种后进先出（Last In First Out，LIFO）的数据结构，适用于括号匹配检测的原因是括号的匹配顺序与它们出现的顺序相反。

二、实验步骤1. 设计算法：确定使用栈进行括号匹配检测的算法步骤。

2. 编写代码：根据算法步骤，编写实现括号匹配检测功能的代码。

3. 测试代码：使用不同的测试用例对代码进行测试，确保其正确性。

4. 分析结果：对测试结果进行分析，评估代码的性能和正确性。

三、实验代码以下是一个使用Python实现的括号匹配检测的示例代码：```pythondef is_balanced(s):stack = []bracket_map = {')': '(', ']': '[', '}': '{'}for char in s:if char in bracket_map.values():stack.append(char)elif char in bracket_map.keys():if not stack or bracket_map[char] != stack.pop(): return Falsereturn not stack测试用例test_cases = ["((()))", True"([{}])", True"({[}])", False"((())", False"()[]{}", True"([)]", False"(({[]}))", True"" True]for case in test_cases:print(f"Input: {case}, Output: {is_balanced(case)}")```四、实验结果与分析通过上述代码，我们对一系列测试用例进行了括号匹配检测。

●实验内容：利用栈的基本操作，写一个C程序实现检测表达式“@{（a+b）*[c-d]+e}+f”中的括号是否匹配。

●实验目的：掌握栈的操作●提交内容：C语言源代码：#include <stdio.h>#include <string.h>#define MaxSize 100typedef char ElemType;typedef struct{ElemType data[MaxSize];int top;}SeqStack;int InitStack(SeqStack *s){s->top=-1;return 1;}int Push(SeqStack *s,ElemType x){if (s->top == MaxSize -1 ){printf("栈已满,不能入栈.\n");return 0;}else{s->top++;s->data[s->top] = x;}return 1;}int Pop(SeqStack *s,ElemType *x) {if (s->top == -1){printf("栈为空,不能出栈.\n");return 0;}else{*x=s->data[s->top];s->top--;}return 1;}int GetTop(SeqStack *s,ElemType *x) {if (s->top == -1){printf("栈为空,不能取值.\n");return 0;}else{*x=s->data[s->top];}return 1;}int IsEmpty(SeqStack *s) {if(s->top==-1)return 1;return 0;}int Check(char str[],int len) {int i;int a=1,b=0;ElemType x;SeqStack s;InitStack(&s);for(i=0;i<len;i++){if(str[i]=='{'){if(IsEmpty(&s)){if(Push(&s,str[i])!=1){a=0;break;}}else{if(GetTop(&s,&x)!=1){a=0;break;}if(x=='{' || x=='[' || x== '('){a=0;break;}else{if(Push(&s,str[i])!=1){a=0;break;}}}}else if(str[i]=='['){if(IsEmpty(&s)){if(Push(&s,str[i])!=1){a=0;break;}}else{if(GetTop(&s,&x)!=1){a=0;break;}if(x=='[' || x== '('){a=0;break;}else{if(Push(&s,str[i])!=1){a=0;break;}}}}else if(str[i]=='('){if(Push(&s,str[i])!=1){a=0;break;}b=1;}else if(str[i]==')'){if(Pop(&s,&x)!=1){a=0;break;}if(x!='('){a=0;break;}}else if(str[i]==']'){if(Pop(&s,&x)!=1){a=0;break;}if(x!='['){a=0;break;}if(b==0){a=0;break;}}else if(str[i]=='}'){if(Pop(&s,&x)!=1){a=0;break;}if(x!='{'){a=0;break;}if(b==0){a=0;break;}}elsecontinue;}if(!IsEmpty(&s))a=0;return a;}int main(){char str[MaxSize];int i,len;printf("输入字符串:\n");gets(str);len=strlen(str);if(Check(str,len)==0)printf("匹配合法\n");elseprintf("匹配不合法\n");。

《数据结构与算法》课程设计报告题目：括号匹配检验四．算法思想利用栈来判断括号是否匹配时，遇到左括号就进栈，遇到右括号则左括号出栈，代表这对括号匹配，如果右括号进栈时，栈为空，则说明缺少左括号，若表达式扫描完栈为空，则说明表达式的括号匹配，否则说明表达式缺少左括号。

五．算法设计程序流程图算法用到的抽象数据类型定义：1．ADT Stack{数据对象：D={a i|a i∈ElemSet,i=1,2，…，n, n≥0}数据关系：R1={<a i-1,a i>|a i-1,a i∈D,i=2, …,n}约定a n端为栈顶，a1端为栈底。

基本操作：（1）I nitStack(&S)；操作结果：构造一个空栈S。

（2）S tackEmpty(S)；初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TURE，否则FALUSE。

（3）S tackFull(S)；初始条件：栈S已存在。

操作结果：若栈S为满，则返回TURE,否则FALUSE.（4）G etTop(S,&e)；初始条件：栈S已存在且非空。

操作结果：用e返回S的栈顶元素。

（5）P ush(&S,e)；初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

（6）P op(&S,&e)；初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。

}ADT Stack∙算法中函数编号及功能要求：1.voidInitStack(SeqStack*S)：初始化，构造一个空栈S2.IsEmpty(SeqStack *S)：判断栈S为空栈时返回值为真，反之为假3.IsFull(SeqStack *S)：判断栈S为满栈时返回值为真，反之为假4.Push(SeqStack *S,StackElementType x)：插入元素x为新的栈顶元素5.Pop(SeqStack *S,StackElementType *x)：将栈S的栈顶元素弹出，放到x所指的存储空间中6.GetTop(SeqStack *S,StackElementType *x)：将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变7.Match(char ch,char str)：进行括号的匹配8.BracketMatch(char *str)： str[]中为输入的字符串，利用堆栈技术来检查该字符串中的括号是否匹配∙函数之间的调用关系（子程序编号见上）：主函数调用函数8函数8调用函数1、2、4、5、6、7六．C语言实现的程序清单/*******括号匹配的检验********/#define TRUE 1#define FALSE 0#define Stack_Size 50#define StackElementType char#include "stdio.h"/*顺序栈*/typedef struct{StackElementType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/int top; /*用来存放栈顶元素的下标，top为-1表示空栈*/}SeqStack;/*初始化*/void InitStack(SeqStack *S){/*构造一个空栈S*/S->top = -1;}/*判栈空*/int IsEmpty(SeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/{return(S->top==-1?TRUE:FALSE);}/*判栈满*/int IsFull(SeqStack *S) /*判断栈S为满栈时返回值为真，反之为假*/{return(S->top==Stack_Size-1?TRUE:FALSE);}int Push(SeqStack *S,StackElementType x){if(S->top==Stack_Size-1)return(FALSE); /*栈已满*/S->top++;S->elem[S->top] = x;return(TRUE);}int Pop(SeqStack *S,StackElementType *x){/* 将栈S的栈顶元素弹出，放到x所指的存储空间中*/if(S->top == -1) /*栈为空*/return(FALSE);else{*x = S->elem[S->top];S->top--; /* 修改栈顶指针*/return(TRUE);}}/*取栈顶元素。

实验表达式括号匹配配对判断问题1，问题的描述假设一个算法表达式中包括圆括号，方括号两种，设计判别表达式中括号是否正确匹配的算法。

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

因此用栈来解决。

struct Node{int top;char data[stacksize];};Node node;void InitStack( ) // 初始化栈{node.top=-1;}（2）一是表达式的串；二是栈。

串可以采用顺序表表示。

所以采用顺序栈，站元素类型为字符型。

sqstack(int n){ base=newT[m];if(base=NULL){cout<<“创栈失败”；exit（1）；}stacksize=m;top=-1;}}3,算法设计（1）进栈的算法设计voidPush(charx){if(node.top==stacksize-1);node.top++;node.data[node.top]=x;}（2）出栈的算法设计void Pop(char &x){if(node.top==-1);x=node.data[node.top--];}（3）判断是否匹配的算发。

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

3．1因为其中包含几种括号，所以用采用switch语句for(i=0;*(p+i)!='\0'&&count!=0;i++){switch (*(p+i)){case '(' :Push(*(p+i)) ;break ;case '[' :Push(*(p+i) ) ;break ;case ')' :{Pop(e) ;if ( e!='(' )count=0 ;};break ;case ']' :{Pop(e) ;if ( e!='[' )count=0 ;}; break ;default:break;}}3．2利用进出栈判断括号是否匹配if ( !StackEmpty () || count==0 ) //条件为:栈不空，而且有出现括号不匹配的情况{cout<<"括号无法匹配！"<<endl;cout<<"你想要继续吗？(y/n)"<<endl;cin>>s;if(s=='y'||s=='Y')goto input;else if(s=='n'||s=='N')cout<<"退出程序!"<<endl;return 0;}else{cout<<"括号能够匹配!"<<endl;cout<<"你想要继续吗？(y/n)"<<endl;cin>>s;if(s=='y'||s=='Y')goto input;else if(s=='n'||s=='N')cout<<"退出程序!"<<endl;return 0;}4．测试与运行（1）显示菜单，如下图：（2）运行结果如下图：5．调试的收获通过这次实验好的感觉到自己还有不足之处，一个程序高那么久才搞定，以后要多加练习。

实验二括号匹配1.需求和规格说明判断输入的表达式中的括号（包含大括号、中括号、小括号）是否匹配。

程序用MFC实现。

2.设计2.1．设计思想主要通过栈来实现。

先接受用户输入的表达式，过滤掉除括号以外的字符，通过栈匹配。

当是左边括号时，进行压栈。

当是右边括号时，是否与栈顶元素匹配（相应的左括号）。

如果匹配，则出栈，并继续进行下一轮匹配。

如果不匹配，则销毁栈，返回不匹配信息。

2.2．设计表示(1)存储结构typedef struct{char *base;char *top;int stacksize;}SqCharStack;(2)涉及的操作int InitCharStack(SqCharStack &S) //初始化栈。

int DestroyCharStack(SqCharStack &S) //销毁栈。

int CharGetTop(SqCharStack S, char &e) //获取栈顶元素。

int CharPush(SqCharStack &S, char e) //压栈。

int CharPop(SqCharStack &S, char &e) //出栈。

int CTest2Dlg::Correct(const char *express) //括号匹配核心处//理函数。

2.3．实现注释(1)参数说明：InitCharStack(SqCharStack &S)函数参数是要初始化的栈。

通过动态方式分配存储空间。

DestroyCharStack(SqCharStack &S)函数参数是要销毁的栈。

释放动态分配的空间。

CharGetTop(SqCharStack S, char &e)函数第一个参数为被获取的值的栈，第二个参数接受获取的栈顶元素的值。

CharPush(SqCharStack &S, char e)函数第一个参数为栈，第二个参数接受出栈元素的值。

1.问题描述假设一个算法表达式中包括圆括号,方括号两种，设计判别表达式中括号是否正确匹配的算法。

2.源程序#include<iostream>//#include<process>using namespace std;typedef char T;//template<class T> //1处//struct Node//{// T *base;// int top;// int stacksize;//};//template<class T>class Sqstack{private:T *base;int top;int stacksize;public:Sqstack(int m);~Sqstack(){}void Push(T x);T Pop();void Index(char *s,int n);};template<class T>Sqstack<T>::Sqstack(int m){base=new T[m];if(base==NULL){cout<<"栈创建失败，退出！"<<endl;exit(1);}stacksize=m;top=-1;}template<class T>void Sqstack<T>::Push(T x){if(top==stacksize-1)throw"栈满，无法入栈";top++;base[top]=x;}template<class T>T Sqstack<T>::Pop(){T x;if(top==-1)throw"栈空，不能出栈";x=base[top--];return x;}template<class T>void Sqstack<T>::Index(char *s,int n){for(int i=0;i<n;i++){if(s[i]=='('||s[i]=='[') Push(s[i]);if(s[i]==')'){if(base[top]=='(') Pop();else{if(top==-1) {cout<<"不匹配:多右括号)";exit(1);}else {cout<<"不匹配:[与)匹配错";exit(1);}}}if(s[i]==']'){if(base[top]=='[') Pop();else{if(top==-1) {cout<<"不匹配:多右括号]";exit(1);}else {cout<<"不匹配:(与]匹配错";exit(1);}}}}if(top==-1) cout<<"匹配";else{if(base[top]=='(') cout<<"不匹配:多左括号(";if(base[top]=='[') cout<<"不匹配:多左括号[";}}int main(void){Sqstack<T> L(20);int n;char s[20];cout<<"输入一个表达式：";cin>>s;n=strlen(s);L.Index(s,n);return 0;}3. 测试与运行。

目录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对编码的讨论 (20)5 总结和体会 (22)附录一 (23)本科生课程设计成绩评定表.................... 错误!未定义书签。

数据结构课程设计——判别括号配对1问题描述1.1题目:判别括号配对1。

2问题：一个算术表达式含圆括号、中括号、花括号，且它们可任意嵌套使用。

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

1.3要求：(1）表达式从键盘输入。

（2)利用栈求解此问题。

(3）测试用例自己设计。

2设计2.1存储结构设计题目要求利用栈来求解此问题，因此选择顺序栈作为存储结构，具体表示如下：＃define STACK_INIT_SIZE 100＃define STACKINCREMENT 10char *base；char ＊top；int stacksize；}SqStack；2.2主要算法设计2.2.1算法思想(1)文字描述从键盘输入一个表达式；逐个扫描表达式中的字符;当遇到左括号时,将左括号入栈；继续扫描，将此后遇到的第一个右括号与栈顶元素比较，若匹配，则栈顶元素出栈；否则，继续扫描；当整个表达式扫描完以后,判断栈内是否还有元素，若有，则括号不匹配；若栈为空，则括号配对成功；在括号配对不成功的情况下，利用栈顶栈底元素的差值，可以对左右括号数进行比较。

（2)流程图表示2.2.2算法void CharIsCorrect（char a［]){SqStack S;char e；int n,c;InitStack(S）;//建立一个空栈n=strlen（a)；//求表达式长度int d=0,b=0;for（int i=0;i〈n;i++)｛if(（a［i］=='（')||(a［i］==’［')｜|(a［i］=='｛’）)Push(S，a[i]）;else{c=StackEmpty(S）；if (（c==1）&＆((a[i］==’)')|｜(a[i］==']')|｜(a[i］==’}’))）//栈为空且当前扫描的字符为右括号时，右括号多于左括号++b；else{e=GetTop（S)；if ((（a[i］==’)')＆&（e==’(’))｜｜(（a[i］==’]'）＆&（e==’[’））｜｜(（a[i]=='｝’)&&（e=='｛’）))//括号匹配时满足的条件e=Pop(S）;else if （（a［i］=='）’)||(a［i]=='］'）｜|（a[i］==’}')）++d;｝｝｝//扫描字符串，左括号进栈，右括号出栈if（StackEmpty（S)==1&&(b==0)＆&(d==0)）cout<〈”左右括号配对正确"<<endl;//栈为空时，括号匹配else cout<<"左右括号不匹配且左括号与右括号个数差为”<〈S.top-S。

实验特殊线性表一、表达式括号匹配配对判断问题1.问题描述假设一个算法表达式中包括圆括号、方括号两种，设计判别表达式中括号是否正确匹配的算法。

2.数据结构设计栈采用顺序栈，栈元素类型为字符型。

T *base;//栈底指针int top;//栈顶int stacksize;//栈容量3.算法设计（1）创建顺序栈SqStack<char> s(20);建立容量为20、元素类型为char的空栈，用于存放括号（2）依次扫描表达式，如果发现左括号就入栈for (int i = 0; i < strlen(Exp); i++) {if (Exp[i] == '(' || Exp[i] == '[' || Exp[i] == '{')s.Push(Exp[i]);（3）用swtich匹配,如果匹配到右括号则出栈，消去一个左括号，出栈一个括号，取下一个字符。

如果不匹配，则根据情况给出匹配失败原因：如果栈空则是多右括号，如果栈不空则是配对错误。

try{e = s.GetTop();}catch (char *err ){cout << "不匹配：多右括号"<<Exp[i] << endl;}cin.get(pause);if (s.GetTop() = = '[') s.Pop();elsecout << "不匹配：" << s.GetTop() << "与]匹配错";break;（4）如果栈空，则表达式匹配，否则不匹配多左括号if (s.StackEmpty() == 1)cout << "匹配";else cout << "不匹配：多左括号" << s.GetTop();4.运行与测试输入多组数据，测试结果如下：5.调试记录及收获实验中发现有时输入任何表达式均会输出匹配，经检查调试，需要在英文模式下输入表达式，使用英文字符的括号。