/*
表达式中的括号是否匹配
*/
bool CLinkSta::IsMatch(DataType* str)
{
if( NULL == str ) return false;
while( m_node )
{
PopLinkStack();
}
CLinkNode* stack1 = NULL;
CLinkNode* stack2 = NULL;
CLinkNode* pNode1 = NULL;
CLinkNode* pNode2 = NULL;
DataType* cTemp = str;
while( *cTemp )
{
if( *cTemp == '(' || *cTemp == '[' || *cTemp == '{' )
{
pNode1 = new CLinkNode;
pNode1->m_Ch = *cTemp;
pNode1->next = stack1;
stack1 = pNode1;
}
else if( *cTemp == ')' || *cTemp == ']' || *cTemp == '}' )
{
pNode2 = new CLinkNode;
pNode2->m_Ch = *cTemp;
pNode2->next = stack2;
stack2 = pNode2;
}
++cTemp;
}
int nCnt = 0;
while( stack1 && stack2 )
{
stack1 = stack1->next;
stack2 = stack2->next;
}
while( stack1 && stack2 )
{
CLinkNode* pTemp1 = stack1;
CLinkNode* pTemp2 = stack2;
stack1 = stack1->next;
stack2 = stack2->next;
DataType ch = pTemp1->m_Ch;
switch( ch )
{
case ')':
ch = '(';
break;
case ']':
ch = '[';
break;
case '}':
ch = '{';
break;
}
if( ch != pTemp2->m_Ch )
{
++nCnt;
break;
}
delete pTemp1;
delete pTemp2;
}
if( !nCnt && !stack1 && !stack2 )
{
return true;
}
else
{
while( stack1 )
{
CLinkNode* pTemp1 = stack1;
stack1 = stack1->next;
delete pTemp1;
}
while( stack2 )
{
CLinkNode* pTemp2 = stack2;
stack2 = stack2->next;
delete pTemp2;
}
while( *str )
{
if( *str == '(' || *str == '[' || *str == '{' )
{
PushLinkStack(*str);
}
else if( *str == ')' || *str == ']' || *str == '}' )
{
if( !m_node )
{
return false;
}
else
{
DataType ch = *str;
switch( ch )
{
case ')':
ch = '(';
break;
case ']':
ch = '[';
break;
case '}':
ch = '{';
break;
}
if( ch != PopLinkStack() )
{
return false;
}
}
}
++str;
}
if( !m_node )
{
return true;
}
}
return false;
}
分享到:
相关推荐
### 数据结构实验:括号匹配检验——链栈实现 #### 实验目的与意义 本实验旨在通过具体的编程实践,帮助学生深入理解并掌握数据结构中的链表和栈这两种基本的数据结构,同时学会如何利用栈来解决实际问题之一:...
这里我们使用的是链栈的实现方式。链栈是一种动态分配内存的数据结构,每个节点都指向下一个节点。我们定义了一个结构体`StackNode`,其中包含了一个元素`data`和一个指向下一个节点的指针`next`。 ```c typedef ...
数据结构,C++实现基于链栈的简单算术表达式求值,本项目的目标是实现一个简单的算术表达式求解器,它能够处理基本的加、减、乘、除运算,并使用链栈数据结构进行求值。设计内容:对带括号的任意算术表达式求值。设计...
链栈是一种特殊的线性数据...通过理解这些基本概念和操作,你可以创建自己的链栈实现,处理各种数据结构问题,如表达式求值、括号匹配等。链栈作为基础数据结构,对于理解和掌握更复杂的算法和数据结构有着重要的作用。
数据结构经典题——链栈括号匹配、判断是否对称串
大连理工大学数据结构上机
本节我们将探讨如何利用C++的面向对象特性,通过自定义类来实现一个基本的栈。我们将涵盖以下几个方面: 1. **栈的基本概念**: 栈是一种线性数据结构,它只允许在一端进行插入和删除操作,这一端被称为栈顶。在...
3. **括号匹配**:验证字符串中的括号是否正确配对,可以使用两个链栈分别存储左括号和右括号。 4. **函数调用栈**:在高级编程语言中,系统用链栈管理函数调用,保存和恢复上下文信息。 链栈由于其动态扩展的特性...
通过链栈,我们可以有效地执行后进先出(LIFO)操作,如表达式求值、括号匹配等。理解链栈的工作原理和实现对于学习数据结构和算法至关重要,特别是在理解和优化计算机程序的内存使用和性能时。
算术表达式的括号匹配合法性判断。(表达式中包括的括号类型有圆括号()、方括号[]以及花括号{}) c.简单算术表达式求值。(表达式里包含运算数、+、-、*、/四类运算符及小括号()) 2.适用人群: 数据结构与算法...
1. 用顺序栈或链栈(自己选择)来检测括号是否匹配。 2. 令所给的式子中出现()[ ]{ }这几种括号形式。 3. 所给的参考代码是用C实现的,要求(1)用C++实现;(2)改进教材P95程序3.7,可以判断所给的式子出现()[ ]...
栈(Stack)作为一种特殊的数据结构,遵循“后进先出”(LIFO,Last In First Out)的原则,常被用于解决许多算法问题,如括号匹配、递归等。本文将详细介绍如何在C++中实现一个链栈,并探讨其基本操作。 首先,...
(1)能够判断表达式中的括号是否匹配,测试的表达式中括号不匹配,可以重新输入。 (2)能够处理多位整数以及浮点数。 (3)具体测试数据自定义。 【实现提示】 设置运算符栈和运算数栈辅助分析算符优先关系;在...
2、输入任意一串由括号(、)、[、]、{、}组成的括号序列,判断括号是否匹配。 文件包含源代码和实验报告,环境为vs2019,实验报告中含有实验目的,实验分析,实验源代码,实验运行结果,注释较多,对基础小白较友好...
链栈是栈的一种实现方式,它通过链式存储结构来实现栈的功能。 ### 栈的概念与操作 栈是一种只能在一端进行插入和删除的线性表,通常称为栈顶。主要操作有: 1. **压栈(Push)**:将元素添加到栈顶。 2. **弹栈...
本主题将深入探讨两种栈实现方式:链栈和顺序栈,以及它们在实际编程中的应用。 链栈是一种动态数据结构,其元素(节点)通过指针链接在一起。每个节点包含一个数据元素和指向下一个节点的指针。链栈的主要操作包括...
4. 栈的应用1(可使用顺序栈或链栈完成):实现括号匹配 测试如下表达式:”{[()](())}” 及”{[()]]}” 5. 栈的应用2(可使用顺序栈或链栈完成):实现中缀表达式计算器,提示将表达式后缀表示并存储于一个数组中...
括号匹配问题就是一个典型的例子,链栈可以通过检查和处理括号的开闭对来判断一个表达式的括号是否正确匹配。 总的来说,链栈作为一种灵活的数据结构,具有高效的操作特性,尤其在需要频繁插入和删除元素的场景下,...
链栈是一种基于链式结构实现的栈数据结构...通过C++实现链栈,可以方便地应用于各种算法和问题解决中,如表达式求值、括号匹配等。理解链栈的工作原理和实现方法,对于提升编程能力尤其是算法设计和分析能力大有裨益。
本文将详细介绍栈的三种常见实现方式:链栈、静态栈,并提供C/C++的实现代码,非常适合算法与数据结构的初学者学习。 ### 链栈 链栈是通过链表来实现的栈,每个节点包含一个数据元素和指向下一个节点的指针。链栈...