下载文档原格式
正则表达式：⼩括号、中括号、⼤括号的区别⼀、⼩括号()、中括号[]、⼤括号的区别 1>. ⼩括号()：匹配⼩括号内的字符串，可以是⼀个，也可以是多个，常跟“|”（或）符号搭配使⽤，是多选结构的 ⽰例1：string name = "way2014"; regex：(way|zgw) result：结果是可以匹配出way的，因为是多选结构，⼩括号是匹配字符串的 ⽰例2：string text = "123456789"; regex：(0-9) result：结果是什么都匹配不到的，它只匹配字符串"0-9"⽽不是匹配数字, [0-9]这个字符组才是匹配0-9的数字 2>.中括号[]：匹配字符组内的字符，⽐如咱们常⽤的[0-9a-zA-Z.*?!]等，在[]内的字符都是字符，不是元字符，⽐如“0-9”、“a-z”这中间的“-”就是连接符号，表⽰范围的元字符，如果写成[-!?*(]这样的话，就是普通字符 ⽰例1： string text = "1234567890"; regex：[0-9] result：结果是可以匹配出字符串text内的任意数字了，像上边的【或符号“|”在字符组内就是⼀个普通字符】 ⽰例2：string text = "a|e|s|v"; regex：[a|e|s] result：结果就是匹配字符a、e、|三个字符，这个跟(a|e|s)有区别的，区别就是(a|e|s)匹配的是a、e、s三个字符的随意⼀个，三个中的任意⼀个，这是的|是元字符 3>.⼤括号{}：匹配次数，匹配在它之前表达式匹配出来的元素出现的次数，{n}出现n次、{n,}匹配最少出现n次、{n,m}匹配最少出现n次，最多出现m次⼀句话辅助记忆：括号越⼤数据越抽象。
测试开发工程师算法题一、前言本题目旨在为测试开发工程师提供一个检验算法能力和提升专业技能的挑战机会。
这些问题涉及到了多种编程语言和数据结构，对于测试开发工程师来说，这些问题有助于提升他们的问题解决能力和编程技巧。
二、问题列表1.最长递增子序列：给定一个长度为n的整数数组，编写一个算法找出其中最长递增子序列的长度。
2.合并两个有序数组：给定两个已排序的整数数组，编写一个算法将它们合并为一个有序数组。
3.最长回文子串：给定一个字符串，编写一个算法找出其最长回文子串。
4.数组中的逆序对：给定一个整数数组，编写一个算法找出其中逆序对的数量。
5.快速排序：实现快速排序算法，并解决一些常见问题，如枢轴选择不当、递归深度过大等。
6.二分查找：实现一个二分查找算法，并处理一些常见问题，如数据已排序、数据无序但已部分排序等。
7.括号匹配：编写一个算法，判断给定的字符串中是否所有括号都匹配。
8.整数拆分：给定一个整数和一个目标值，编写一个算法将整数拆分成若干个部分，使得它们的和等于目标值。
三、解答与解析对于每个问题，我们将提供完整的代码和详细的解析，帮助测试开发工程师理解问题的解决方法和技术实现。
四、测试与评估为了检验测试开发工程师的解答正确性，我们将提供一些测试用例。
测试用例将覆盖所有问题的关键点，以确保答案的正确性和有效性。
评估将基于代码的正确性、效率和简洁性进行。
五、注意事项1.请使用您熟悉的编程语言进行解答。
2.请注意代码的可读性和可维护性，避免出现难以理解的代码和难以调试的问题。
3.请注意代码的运行效率，尽可能使用高效的数据结构和算法。
4.请在解答中包含必要的注释和文档，以便他人理解您的代码。
5.如有疑问，请及时与我们的工作人员联系，我们将尽力提供帮助。
六、结语我们希望这些问题和解答能够帮助测试开发工程师提升算法能力和专业技能。
同时，我们也欢迎各位测试开发工程师积极参与讨论和分享经验，共同进步。
《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。
A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。
（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。
（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。
A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。
（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。
A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。
矩子aoi算法矩子Aoi 算法是一种高效的中括号匹配算法，它在处理大规模文本数据中的中括号匹配问题时具有优异的性能表现。
矩子Aoi 算法是近年来比较新的算法，它采用了一些先进的技术，比如SA-IS 算法和后缀数组等，以实现更快的中括号匹配。
在本文中，我们将逐步回答与矩子Aoi 算法相关的问题，例如它的工作原理、实现细节、时间复杂度和应用场景等。
同时，我们会通过一些实例和代码来展示这些问题，以帮助读者更好地理解矩子Aoi 算法的核心思想和运行方式。
1. 矩子Aoi 算法的基本原理是什么？矩子Aoi 算法主要的基本原理就是通过后缀数组和SA-IS 算法来实现中括号匹配，它利用了后缀数组的快速查找能力和SA-IS 算法的高效的子字符串排序算法来实现中括号匹配。
具体来说，矩子Aoi 算法首先通过SA-IS 算法对给定文本进行后缀排序，并根据排名关系构建出后缀数组。
然后，矩子Aoi 算法构建出一个称为“匹配串”的字符串，匹配串中除了中括号，其他字符均用英文句点代替。
通过对匹配串进行后缀排序，构建出新的后缀数组，之后通过对后缀数组的查找功能，就可以快速地定位到中括号的位置，实现中括号的匹配。
2. 矩子Aoi 算法的工作流程是怎样的？矩子Aoi 算法的工作流程可以简单地分为以下几个步骤：1. 输入文本数据，并进行一些预处理工作，如去除空格、标点符号等。
2. 使用SA-IS 算法对文本进行后缀排序，并根据排名关系构建出后缀数组。
3. 构建匹配串，将匹配串中除了中括号，其他字符均用英文句点代替。
4. 使用SA-IS 算法对匹配串进行排序，构建出新的后缀数组。
5. 遍历后缀数组，查找匹配串中的中括号位置，并进行匹配。
6. 如果中括号匹配成功，则输出匹配结果；否则，输出匹配失败。
3. 矩子Aoi 算法的实现细节有哪些？矩子Aoi 算法的实现细节主要包括以下几个方面：1. 后缀排序算法：矩子Aoi 算法使用SA-IS 算法进行后缀排序和后缀数组构建，该算法是一种高效的子字符串排序算法，具有良好的时间复杂度。
栈与队列实现先进先出和后进先出的数据结构数据结构是计算机科学中一门重要的基础课程，其中栈（Stack）和队列（Queue）是常用的数据结构。
栈和队列都具有不同的特点和应用场景，能够满足先进先出（FIFO）和后进先出（LIFO）的要求。
一、栈的实现先进先出栈是一种线性数据结构，具有后进先出（LIFO）的特点。
在栈中，只能在栈的一端进行操作，称为栈顶。
栈的基本操作包括入栈（Push）和出栈（Pop）。
1. 入栈（Push）操作：当要向栈中添加元素时，将新元素放置在栈顶，并将栈顶指针向上移动一位。
该操作保证了后添加的元素会处于栈顶的位置。
2. 出栈（Pop）操作：当要从栈中移除元素时，将栈顶的元素弹出，并将栈顶指针向下移动一位。
该操作保证了最后添加的元素会最先被移除。
栈的实现可以使用数组或链表来存储元素。
使用数组实现时，需要指定栈的最大容量。
使用链表实现时，栈的容量可以动态扩展。
二、队列的实现先进先出队列是一种线性数据结构，具有先进先出（FIFO）的特点。
在队列中，元素从队尾入队，从队头出队。
队列的基本操作包括入队（Enqueue）和出队（Dequeue）。
1. 入队（Enqueue）操作：当要向队列中添加元素时，将新元素放置在队尾，并将队尾指针向后移动一位。
该操作保证了后添加的元素会处于队列的尾部。
2. 出队（Dequeue）操作：当要从队列中移除元素时，将队头的元素弹出，并将队头指针向后移动一位。
该操作保证了最早添加的元素会最先被移除。
队列的实现也可以使用数组或链表。
与栈不同的是，队列的实现更适合使用链表，因为链表可以实现在队头和队尾高效地执行插入和删除操作。
三、使用栈和队列实现先进先出和后进先出为了实现先进先出和后进先出的数据结构，可以使用一种特殊的数据结构：双端队列（Double-ended Queue），也称为双端栈（Deque）。
双端队列具有栈和队列的特点，既可以在队尾插入和删除元素，也可以在队头插入和删除元素。
《数据结构》学习指导说明：本指导以《数据结构》(C语言版)(严蔚敏等编著,清华大学出版社1997年出版，国家级优秀教材特等奖)和《数据结构题集》(严蔚敏等编著,清华大学出版社1999年出版)为教学主要参考书。
一、绪论1、学习目的：明确数据结构课程在本专业知识结构中的地位，作用。
课程的特点，教学的要求，方法。
明确数据结构所研究的问题以及有关基本概念。
初步掌握抽象数据类型的表示与实现，初步明确算法分析的作用与分析的重点，初步掌握算法分析的方法。
2、学习重点：数据的逻辑结构、存储结构及其算法，数据结构的有关概念，抽象数据类型及其表示与实现，算法，算法设计的要求，算法的时间复杂度和算法的空间复杂度。
3、学习难点：数据结构的有关概念，抽象数据类型的表示与实现；算法的时间复杂度分析。
4、课程内容与基本要求(一) 数据结构的引入(1) 三个世界：现实世界，信息世界，机器世界。
数据结构要解决的就是实现从现实世界到信息世界，再由信息世界到机器世界的转换，从而实现用计算机来解决问题的目的。
(2) 非数值问题(结合三个世界讲)：控制，管理，数据处理(3) 数值问题：数值计算(4)数据结构：从学科角度讲，数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及他们之间的关系和操作等等的学科。
(二) 课程的地位，性质，作用。
(1) 地位: 计算机专业的核心课程之一。
(2) 性质: 算法理论基础和软件设计的技术基础课。
(3) 作用: 程序设计的基础，编译程序，操作系统，数据库系统及软件系统和应用程序的基础(三) 数据结构的产生和发展(四) 课程的特点，学习的要求教材：《数据结构》(C语言版)严蔚敏等编著北京清华大学出版社1997年参考书：《数据结构》许卓群等编著北京高等教育出版社1987年数据结构实用教程》（C/C++描述）徐孝凯北京清华大学出版社1999年《数据结构题集》严蔚敏等编著北京清华大学出版社1999年《数据结构导学》苏光奎等编著北京清华大学出版社20XX年《数据结构》(C语言篇)－习题与解析李春葆编著北京清华大学出版社20XX年《数据结构》实验指导书唐开山自编讲义20XX年(五) 基本概念和术语数据数据元素数据对象(4)数据结构:按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储到计算机的存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构。
数据结构与算法习题册（课后部分参考答案）《数据结构与算法》课程组目录目录课后习题部分第一章绪论 (1)第二章线性表 (3)第三章栈和队列 (5)第四章串 (8)第五章数组和广义表 (10)第六章树和二叉树 (13)第七章图 (16)第九章查找 (20)第十章排序 (23)第一章绪论一. 填空题1. 从逻辑关系上讲，数据结构的类型主要分为集合、线性结构、树结构和图结构。
2. 数据的存储结构主要有顺序存储和链式存储两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素和数据元素之间的关系。
3. 算法具有五个特性，分别是有穷性、确定性、可行性、输入、输出。
4. 算法设计要求中的健壮性指的是算法在发生非法操作时可以作出处理的特性。
二. 选择题1. 顺序存储结构中数据元素之间的逻辑关系是由 C 表示的，链接存储结构中的数据元素之间的逻辑关系是由 D 表示的。
A 线性结构B 非线性结构C 存储位置D 指针2. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
则表示该遗产继承关系的最合适的数据结构应该是B 。
A 树B 图C 线性表D 集合3. 算法指的是 A 。
A 对特定问题求解步骤的一种描述，是指令的有限序列。
B 计算机程序C 解决问题的计算方法D 数据处理三. 简答题1. 分析以下各程序段，并用大O记号表示其执行时间。
(1) (2)i=1;k=0; i=1;k=0;While(i<n-1) do{ {k=k+10*i; k=k+10*i;i++; i++;} }while(i<=n)⑴基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。
⑵基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。
2. 设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。
软件学院学科基础课程实验报告册课程名称数据结构实验学期年至年第学期学生所在院（系）年级专业班级学生姓名学号指导教师实验最终成绩软件工程教研室制2010年3月实验报告须知1、学生按照“实训”课任课教师给出的题目和要求填写实验报告，填写应遵循实验报告样本格式。
2、完成的电子文档（文档、表格、演示文稿、操作过程截图等）按任课教师的要求发往指定的电子邮箱。
3、学生应该填写的内容包括：封面相关栏目、实验题目、时间、地点、实验目的、内容、过程和步骤、结果分析总结。
4、教师应该填写的内容包括：实验最终成绩、每次实验报告的成绩和对报告内容的评阅。
教师根据每学期该课程的实验教学要求，评定学生的实验成绩。
在课程结束后两周内将教学班的实验报告汇总交教学秘书存档。
5、未尽事宜，请参考该课程实验大纲和考试大纲。
实验报告（一）实验题目线性表的应用实验时间年月日实验地点实验成绩实验性质□应用性□设计性□综合性教师评阅：□实验目的明确；□操作步骤正确；□设计文稿（表格、程序、数据库、网页）符合要求；□保存路径正确；□实验结果正确；□实验分析总结全面；□实验报告规范；□其他：评阅教师签名：一、实验目的1 了解和掌握线性表的顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实现。
2 能够利用线性表结构对实际问题进行分析建模，利用计算机求解。
3 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
二、实验内容和要求1 利用程序设计语言分别实现顺序表和链表的抽象数据类型。
2 掌握程序分文件（头文件和实现文件）书写的方式。
3 分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。
三、实验过程与步骤（原始记录）四、实验结果（设计文档、文稿、数据表、媒体文件存放路径）五、实验分析总结实验报告（二）实验题目栈和队列的应用实验时间年月日实验地点实验成绩实验性质□应用性□设计性□综合性教师评阅：□实验目的明确；□操作步骤正确；□设计文稿（表格、程序、数据库、网页）符合要求；□保存路径正确；□实验结果正确；□实验分析总结全面；□实验报告规范；□其他：评阅教师签名：一、实验目的1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
头歌数据结构实训作业答案 篇一 一、题目 （一）线性表章节（简单难度） 数组操作 1. 已知一个整型数组`nums = 1, 3, 5, 7, 9`，编写一个函数来计算数组中所有元素的和。
（二）栈与队列章节（中等难度） 栈的应用 2. 给定一个只包含括号`'('`和`')'`的字符串`s`，判断字符串中的括号是否匹配。例如，`"(()())"`是匹配的，`"())("`是不匹配的。
（三）树章节（较难难度） 二叉树遍历 3. 给定一个二叉树的根节点`root`，实现先序遍历、中序遍历和后序遍历，并分别以数组形式返回遍历结果。二叉树节点定义如下：
```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ``` 二、答案 （一） ```python def sum_array(nums): sum = 0 for num in nums: sum += num return sum ``` （二） ```python def is_valid(s): stack = mapping = {')': '('} for c in s: if c in '(': stack.append(c) else: if not stack or stack.pop()!= mappingc: return False return not stack ``` （三） ```python def preorderTraversal(root): result = def helper(node): if node: result.append(node.val) helper(node.left) helper(node.right) helper(root) return result def inorderTraversal(root): result = def helper(node): if node: helper(node.left) result.append(node.val) helper(node.right) helper(root) return result def postorderTraversal(root): result = def helper(node): if node: helper(node.left) helper(node.right) result.append(node.val) helper(root) return result ``` 三、解析 （一）数组求和 解题思路 着眼点在于对数组中的每个元素进行累加操作。通过遍历数组中的每一个元素，将其累加到一个初始值为0的变量`sum`中。
算法与数据结构对程序效率的影响在计算机科学中，算法和数据结构是构建高效程序的关键要素。
优秀的算法和数据结构设计可以极大地提高程序的执行效率和运行速度，从而提升整体系统性能。
本文将从算法和数据结构的角度探讨它们对程序效率的影响。
一、算法对程序效率的影响算法是解决问题的一系列步骤和规则的描述，它直接决定了程序的运行时间和空间复杂度。
一个好的算法可以显著降低程序的时间和空间开销，进而提高程序的效率。
1. 时间复杂度算法的时间复杂度是对算法执行时间的度量。
它表示算法执行所需的时间与问题规模之间的关系。
常见的时间复杂度有常数阶（O(1)）、对数阶（O(log n)）、线性阶（O(n)）、平方阶（O(n^2)）等。
选择时间复杂度低的算法可以减少程序的执行时间，提高效率。
2. 空间复杂度算法的空间复杂度是对算法所需内存空间的度量。
它表示算法所需的额外空间与问题规模之间的关系。
常见的空间复杂度有常数阶（O(1)）、线性阶（O(n)）、对数阶（O(log n)）等。
选择空间复杂度低的算法可以节省内存空间，提高效率。
3. 算法设计技巧在算法设计过程中，采用一些常用的技巧和策略可以进一步提高算法的效率。
例如，分治法可以将问题分解为更小的子问题来解决；贪心算法可以在每一步选择中都做出当前最优的选择；动态规划可以通过记忆化搜索或者自底向上的方式解决重叠子问题。
二、数据结构对程序效率的影响数据结构是组织和存储数据的方式，它影响着程序在内存中的存储和访问效率。
选择合适的数据结构可以减少算法执行过程中的数据操作次数，提高程序的效率。
1. 数组数组是一种连续存储的数据结构，通过索引可以直接访问任意位置的元素。
数组的访问速度快，但插入和删除操作比较慢，需要移动其他元素。
适用于数据量不变、需要频繁访问元素的场景。
2. 链表链表是一种通过指针相连的数据结构，可以动态添加和删除元素。
链表的插入和删除速度快，但访问元素需要遍历指针链，效率较低。
数据结构....名词解释数据结构....名词解释1.数组（Array）数组是一种线性数据结构，它由一组相同类型的元素组成，这些元素在内存中是连续存储的。
数组可以通过索引来访问和操作其中的元素，索引从0开始。
数组的优点是能够快速访问任意位置的元素，缺点是在插入和删除操作时效率较低。
2.链表（Linked List）链表也是一种线性数据结构，它由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
链表的优点是插入和删除操作很高效，缺点是访问任意位置的元素时效率较低。
3.栈（Stack）栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。
栈的典型应用场景包括函数调用的过程、表达式求值和括号匹配等。
4.队列（Queue）队列是一种先进先出（FIFO）的数据结构，允许在队尾插入元素，在队头删除元素。
队列常用于任务调度、消息传递以及广度优先搜索等场景。
5.树（Tree）树是一种非线性数据结构，由节点和边组成。
每个节点可以有零个或多个子节点，其中没有父节点的节点称为根节点。
树的应用非常广泛，包括二叉树、二叉搜索树和平衡树等。
6.图（Graph）图是一种由节点和边组成的非线性数据结构，节点之间的连接关系称为边。
图可以表示各种实际问题，例如社交网络、电路等。
7.哈希表（Hash Table）哈希表是一种以键值对形式存储数据的数据结构。
通过哈希函数将键映射到哈希表中的一个位置，从而实现快速的插入、删除和查找操作。
8.堆（Heap）堆是一种完全二叉树的数据结构，它满足堆特性（最大堆或最小堆）。
在最大堆中，每个节点的值都大于等于其子节点。
在最小堆中，每个节点的值都小于等于其子节点。
堆常用于实现优先队列和堆排序算法。
9.图论（Graph Theory）图论研究图及其性质和关系的数学理论。
它涉及图的表示方法、遍历算法、最短路径算法、最小树算法等。
10.排序算法（Sorting Algorithms）排序算法用于将一组数据按照特定规则进行排序。
※数据结构综合实验报告
实验一 括号的匹配问题
一．实验目的：
（1） 熟练掌握数据结构的基本知识。
（2） 掌握线性结构中队列设计的基本思路、应用方法，以及存储于队列中
数据之间的逻辑关系与性质。
（3） 能够利用所学的基本知识和技能，解决简单的数据结构算法设计与
分析。
二．实验环境及软件
操作系统：Windows XP， 开发工具：VC++6.0
三．实验内容：
1.问题描述（功能要求）：
一个表达式中包括变量、常量、操作符、圆括号，圆括号可以嵌套,
编写程序判断表达式中的括号是否正确匹配。输入任意一个表达式，判断
其中括号是否匹配，匹配, 输出OK, 不匹配，输出NO。(表达式的长度小
于50)
四．具体算法设计详解：
1.创建一个空栈b,数据类型为字符型。
2.输入一个字符型数组a。
3.逐字符扫描输入的字符串a。
2.1 假如是‘(’ 则调用Push(x)函数，将其压入栈。
2.2 假如是‘)’,则将该值赋给同样是字符型的数组c，并令计
数器i+1，继续检测输入字符串的下一个字符。
4.假如输入字符串的字符都扫描完了。调用计数器i次的Pop（）函
数，每次调用另一个计数器k+1。当栈b为空时，停止调用函数Pop()。
5.比较计数器i和k的值。如果相等，则呈现匹配，输出OK。如过
i与k不等，则呈现不匹配，输出NO。
五．具体代码实现详细分析：
1.先定义一个存储点信息的结构体Node
struct Node
{
T data;
Node
};
2.再定义一个存储栈的数据及具体操作的类linkStack
class linkStack
{
public:
linkStack(){top=NULL;length=0;} //栈的构造函数
~linkStack(); //栈的析构函数
void Push(T x); //入栈函数
int Pop(); //出栈函数
int Empty(){if(top==NULL)return 0;else return 1;} //判断栈是否为空
private:
Node
int length; //栈的长度
};
3.各函数的分析
(1)数据入栈
void linkStack
{
Node
if(length>=50)cout<<"上溢"<
{
s=new Node
s->next=top;top=s;
length++;
}
}
（2）数据出栈
int linkStack
{
Node
if(top==NULL)return 0; //栈空，返回0
else
{ //反之，将栈顶元素出栈，栈长度length-1，
q=top; //并返回值1
top=top->next;
delete q;
length--;
return 1;
}
}
（3）主函数的设计
int main()
{
char a[50],c[50]; //定义两个长度为50的字符型数组
linkStack
int n,i=0,k=0; //定义两个计数器i和k，并初始为0
scanf("%s",a); //输入一个字符串
for(n=0;n<50;n++)
{
if(a[n]=='(')b.Push(a[n]); //如果是‘（’则入栈
else if(a[n]==')') //如果是‘）’则赋给数组c,计数器i++
{
c[i]=a[n];
i++;
}
}
for(n=0;n<=i;n++) //如果栈不为空，使栈中元素出栈，并且计数器k++
{
if(b.Pop()==1)k++;
else
break;
}
if(k==i)cout<<"OK"<
}
六．实验结果（接实验结果截屏）：
a.表达式括号不匹配 b.表达式括号匹配成功
七．附实验代码：
#include
#include
using namespace std;
template
struct Node
{
T data;
Node
};
template
class linkStack
{
public:
linkStack(){top=NULL;length=0;}
~linkStack();
void Push(T x);
int Pop();
int Empty(){if(top==NULL)return 0;else return 1;}
private:
Node
int length;
};
template
void linkStack
{
Node
if(length>=50)cout<<"上溢"<
{
s=new Node
s->next=top;top=s;
length++;
}
}
template
int linkStack
{
Node
if(top==NULL)return 0;
else
{
q=top;
top=top->next;
delete q;
length--;
return 1;
}
}
template
linkStack
{
Node
while(top)
{
p=top;
top=top->next;
delete p;
length--;
}
}
int main()
{
char a[50],c[50];
linkStack
int n,i=0,k=0;
scanf("%s",a);
for(n=0;n<50;n++)
{
if(a[n]=='(')b.Push(a[n]);
else if(a[n]==')')
{
c[i]=a[n];
i++;
}
}
for(n=0;n<=i;n++)
{
if(b.Pop()==1)k++;
else
break;
}
if(k==i)cout<<"OK"<
}
