首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 数据库 > SQL Server >

【交流贴】使用sql模拟循环链表与堆栈进行括号匹配,该怎么解决

2012-03-17 
【交流贴】使用sql模拟循环链表与堆栈进行括号匹配以前发过一个,发现错误太多,自己很汗颜。经过若干人的指正

【交流贴】使用sql模拟循环链表与堆栈进行括号匹配
以前发过一个,发现错误太多,自己很汗颜。经过若干人的指正后,对原程序进行修改。重新发布,希望大家来拍砖。
觉得没用,可以一笑了之。
/*********************************** 
  作者:trieagle(让你望见影子的墙)
  日期:2009.7.4
  注: 转载请保留此信息
************************************/

  问题:设计一个算法,判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中,每个结点有两个域:ch和link,其中ch域为字符类型。

  如果单纯从用程序的角度来说,难度应该不大。我的看法:当遇到(号,那么计数器加1,当遇到右括号的时候,计数器减1. 
结果及判断条件: 
  1、匹配:计数器为0,字符串读取结束 
  2、(不匹配:有多余的(导致不匹配,计数器不为0 
  3、)不匹配,有多余的)导致不匹配,计数器为0,但是字符串中遇到)。 

另外还有其他方法:

  参见:http://topic.csdn.net/u/20090620/17/bffdc5aa-d3dc-4001-bd98-6ad1ececc5bd.html 10楼。

  但是在这里要求使用链表和堆栈。

1、思路:根据括号的特点( ( ) ),进行匹配的时候,第一个做括号最后一个匹配,最后一个左括号与第一个右括号相匹配,恰好可以使用栈来进行存储。

2、方法:先把表达式放在链表中,然后读取链表,当遇见左括号时,把“(”入栈,遇见

  “)”时进行出栈,直到栈空或者链表结束。

3、在进行检测括号是否匹配的时候,需要考虑到各种情况:

  1)、匹配。 例如:(())

  2)、左括号不匹配。例如: (()

  3)、右括号不匹配。例如: ())

4、判断上述几种情况的方式:

  1)左括号不匹配:当链表读取结束的时候,检测栈为不为空。

  2)右括号不匹配:当栈为空,而链表中还存在“)”。

  3)括号匹配:当栈为空,并且读取链表结束。

  http://blog.csdn.net/HEROWANG/archive/2009/06/20/4285326.aspx。
  在这里使用SQL来模拟循环链表和堆栈。使用链表的思路其实就是一个简单的BOM。另,在使用堆栈进行判断的时候,使用游标来读取表中的内容更简单一点,但是在这里为了更好的体现链表的特点,所以使用的是next来获取下一个字符。
 

SQL code
declare @s varchar(8000),@next int     set @s=')((()as(d(s())))'     declare @ntb table(id int ,name varchar(10),next int)      declare @stb table(id int identity(1,1),name varchar(10))      set @next=1      /*模拟循环链表*/     while (@s is not null)      begin         insert into @ntb values(@next,left(@s,1),@next+1)         select @s=stuff(@s,1,1,''),@next=@next+1      end      update @ntb      set next=1      where id=@next-1      select * from @ntb   /*模拟栈并进行判断*/     declare @nextNode int,@c char ,@id int    select top 1 @id=id,@c=name,@nextnode=next from @ntb order by id      while @nextnode<>(select min(id) from @ntb)      begin           if @c='('              begin               insert into @stb values(@c)           end           if @c=')'        begin               if exists(select 1 from @stb)                  begin                     delete from @stb                      where id=(select max(id) from @stb)                  end               else                 break           end          select @id=id,@c=name ,@nextnode=next from @ntb where id=@nextnode      end      if exists(select 1 from @stb)         print'左括号不匹配'     else       if exists(select 1 from @ntb where id>@id )            print '右括号不匹配'       else           print '匹配'     结果:   右括号不匹配  

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/HEROWANG/archive/2009/07/04/4321071.aspx


 

[解决办法]
sf
[解决办法]
再学习
[解决办法]
学习.
[解决办法]
SF
[解决办法]
先頂,明天看~~
[解决办法]
学习啊
[解决办法]
学习
[解决办法]
.
------解决方案--------------------


bd
[解决办法]
像)(这种的应该也算不匹配的吧!
[解决办法]
学习。。。。。
[解决办法]
mark 后学习,
[解决办法]
好文
[解决办法]
if @c='(' 
else if @c=')'
[解决办法]
人力资源管理培训咨询项目遇到同样问题

学习
[解决办法]
既然是讨论,不妨说说拙见。
楼主显然没有充分利用SQL的特性。遍历在SQL的世界是内置的。
1. create table X( id, bra,n),id为自增长字段;
2. 将输入字符串的所有“(”和“)”从左到右依次插入表X中;
3. 对于“(”来说,n表示后面的“)”数与所有“(”数的差加1,0表示正确;
4. 对于“)”来说,n表示前面的“(”数与所有“)”数的差减-1,0表示正确;
5. 最后不仅可以输出是否匹配,还能输出第几个括号不匹配。

热点排行