【交流贴】使用SQL模拟循环链表与堆栈进行括号匹配

Question

    使用SQL模拟循环链表与堆栈进行括号匹配，在实际应用中或许没有什么太大的用处，发此贴仅仅觉得该功能可以实现。大家姑且看之，如果觉得无用，可以一笑了之。
    详情参见博客：
    http://blog.csdn.net/HEROWANG/archive/2009/07/04/4321071.aspx
/***********************************          作者：trieagle(让你望见影子的墙）         日期：2009.6.20         注：  转载请保留此信息************************************/    问题：设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：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）括号匹配：当栈为空，并且读取链表结束。  用C语言实现起来比较简单，参见：我的另一个博客：   http://blog.csdn.net/HEROWANG/archive/2009/06/20/4285326.aspx。在这里使用SQL来模拟循环链表和堆栈。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   
/*模拟栈并进行判断*/  
declare @nextNode int,@c char  
select top 1 @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 @c=name ,@nextnode=next from @ntb where id=@nextnode   
end   
if exists(select 1 from @stb)   
   print'左括号不匹配'  
else  
  if exists(select 1 from @ntb)   
      print '右括号不匹配'  
  else  
      print '匹配'  
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
/*模拟栈并进行判断*/
declare @nextNode int,@c char
select top 1 @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 @c=name ,@nextnode=next from @ntb where id=@nextnode
end
if exists(select 1 from @stb)
   print'左括号不匹配'
else
  if exists(select 1 from @ntb)
      print '右括号不匹配'
  else
      print '匹配'
  
结果：右括号不匹配  

Answer 1

    使用链表的思路其实就是一个简单的BOM。
    另，在使用堆栈进行判断的时候，使用游标来读取表中的内容更简单一点，但是在这里为了更好的体现链表的特点，所以使用的是next来获取下一个字符。

Answer 2

汗。我刚写的。以前我是发过一个括号匹配的帖子，想让写一个用sql模拟循环链表和栈的，结果没人写。
帖子地址：http://topic.csdn.net/u/20090620/17/bffdc5aa-d3dc-4001-bd98-6ad1ececc5bd.html 
如果真的和其他人的雷同了，就把我的这个跟撤了吧

Answer 3

幸福就是  www.770539.com

Answer 4

早上才发现，帖子中代码贴重复了，另外日期应该是2009.7.4。版主如果不忙的话，帮忙改一下，还有下面要补充的内容。以http://blog.csdn.net/HEROWANG/archive/2009/07/04/4321071.aspx 
上的内容为准。谢谢

Answer 5

感谢，貌似在后面进行括号判断的条件有点问题，修正一下。再帮忙给看一下？declare @s varchar(8000),@next int  
set @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 @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)  
        select * from @stb   
      end     
   if @c=')'  
   begin   
         if exists(select 1 from @stb)   
            begin   
               delete from @stb    
               where id=(select max(id) from @stb)   
               select * from @stb
            end   
         else  
            break  
      end   
    select @id=id,@c=name ,@nextnode=next from @ntb where id=@nextnode   
    print @c+''+cast(@nextnode as varchar)
end   
if exists(select 1 from @stb)   
   print'左括号不匹配'  
else  
  if exists(select 1 from @ntb where id>@id )   
      print '右括号不匹配'  
  else  
      print '匹配'  

Answer 6

写了一个另类的方法～～ declare @s varchar(8000),@id int
set @s=')((()as(d(s())))'
set @id = 1
declare @tb table(id int ,name varchar(10))
while(@s is not null)
begin   
   insert into @tb values(@id,left(@s,1))   
   select @s=stuff(@s,1,1,''),@id=@id+1   
end 
 
delete a from @tb a 
where not exists
(
select 1 from (select '(' as name union select ')')b
where a.name = b.name 
)declare @maxid int
declare @minid int
select @maxid = max(id) from @tb where name = '('
select @maxid
select  @minid = min(id) from @tb a where exists(select  min(abs(@maxid - id)) from @tb where name = ')' and a.id = id and id > @maxid) and a.id >@maxid
select @minidwhile(@maxid>0 and @minid >0)
begin
   delete from @tb where id in(@maxid,@minid)
   select @maxid = max(id) from @tb where name = '('
   select  @minid = min(id) from @tb a where exists(select  min(abs(@maxid - id)) from @tb where name = ')' and a.id = id and id > @maxid) and a.id >@maxid
endselect * from @tbset @s = ''
select @s = @s +','+ name from @tb
select stuff(@s,1,1,'') as [不匹配的括号]

Answer 7

老师的写法还没考虑左括号和右括号 先后顺序的问题～～  用set @s=')((()as(d(s())))'
老师的结果是匹配的

Answer 8

其实如果要判断括号匹配不匹配是比较简单的，但想要用sql模拟一下循环链表与堆栈（关键是这块，而不是简单的判断括号匹配问题）。
26楼
/*模拟栈并进行判断*/  
declare @nextNode int,@c char ,@id int 
select top 1 @c=name,@nextnode=next from @ntb order by id   
少了个东西：
select top 1 @id=id,@c=name,@nextnode=next from @ntb order by id