我能想到的方法是：一个圆括号栈，一个花括号栈，把数组的符号一个一个压到相应的栈，遇到相对的一对括号就一对整个 pop，最后两个栈都为空就是 true

开始没理解你说的不能交叉的意思，是不是 ( { ) } 这种不符合，如果是，那就我的方法错了

如果上面的交叉不符合的话，其实使用一个栈，每个符号都压到这个栈，遇到相对的一对括号就一对整个 pop，最后栈为空就是 true

@yanguango 栈的想法挺巧妙的，但有个疑问？比如｛（｛（｝）｝）可以分出｛｛｝｝和（（））的。但它们原本是交叉的

哦，感觉放一个栈里应该是对的，我试试，谢谢！

一个栈我觉得是可以的

def balanced? astring
  tmp = []
  left = ["(", "{"]
  right = [")", "}"]
  astring.chars.each do |c|
    if left.include? c
      tmp.push c
    elsif right.include? c
      if left.index(tmp.last)==right.index(c)
        tmp.pop 
      else
        return false
      end
    end
  end
  return tmp.empty?
end

p balanced? "{({()})}"

用一个栈肯定可以。突然想到一个不用栈的。。

def balanced?(string)
  return false unless string.count('{') == string.count('}') &&
                      string.count('(') == string.count(')')
  !(string.index('{)') || string.index('(}'))
end

不过感觉这样单行太长了，不知道怎么样换行合适。。

昨晚关电脑了才发现，这二个代码有漏洞， )(这样的会判定为true

#4 楼 @wcp1231 有点取巧，这个思路的话正则应该也行，哈哈，这个"()}(){()"算不算交叉，交叉和成对应该是两回事

#3 楼 @lufeihaidao 谢谢，不知道一般的编辑器找成对的括号是不是这么实现的？

#7 楼 @luikore 大神总是让人让人瞬间膜拜。

#5 楼 @yltian 我昨晚关电脑了才发现我这个方法有漏洞，)(这样的无法解决。。 本来我想的是没效率的用 sub 不断替换的，看了 #7 楼 @luikore 大神的方法才发现可以这样简洁，我试着把大神的代码改成了这样：

str = "{(){}((){})}()"
str =~ /\A( \(\g<1>*\) | \{\g<1>*\} )*\z/x

希望没有错误。。

你们都这么晚睡觉么。。？

其实用最简单的递归下降就行了，比如 E='('E')' | '{'E'}' | null

#10 楼 @rasefon 递归下降不明觉厉的样子，非常想学，先 mark 了，等我把基础熟悉了再深入研究啦。谢谢！

#10 楼 @rasefon 那还得写一个语法解析器状态机。

#12 楼 @linjunhalida 就 4 个字符串。。。

#!/usr/bin/env escript

balanced("", "") ->
  true;
balanced("("++T, Stack) ->
  balanced(T, "("++Stack);
balanced(")"++T, "("++Stack) ->
  balanced(T, Stack);
balanced("{"++T, Stack) ->
  balanced(T, "{"++Stack);
balanced("}"++T, "{"++Stack) ->
  balanced(T, Stack);
balanced(_, _) ->
  false.

balanced(S) ->
  balanced(S, "").

test() ->
  true = balanced(""),
  true = balanced("()"),
  true = balanced("(())"),
  true = balanced("{}"),
  true = balanced("{{}}"),

  true = balanced("({})"),
  true = balanced("{()}"),

  false = balanced("("),
  false = balanced(")"),
  false = balanced("(()"),
  false = balanced("())"),
  false = balanced("{"),
  false = balanced("}"),
  false = balanced("{{}"),
  false = balanced("{}}"),

  false = balanced("{(})"),

  true = balanced("({})(){()}"),

  ok.

main(_) ->
  test().

#14 楼 @bhuztez 用 erlang 来做就太 easy 了

用栈

#14 楼 @bhuztez "({})(){()}"可以么？

#10 楼 @rasefon

用 kleen star 的写法：

X = E*
E = '(' E* ')' | '{' E* '}'

把 E 当成第一个括号组 (\g<1>) 来动态引用

'(' \g<1>* ')' | '{' \g<1>* '}'

再把 escape 和 anchor 补上就是那个正则了

#18 楼 @luikore 我看到正则表达式就头疼。

#17 楼 @rasefon 可以阿

#20 楼 @bhuztez 看不太明白。。 像是直接用参数做模式匹配了。

#21 楼 @rasefon 不能更简单了

#19 楼 @rasefon CFG/PEG 等语法是正则语法的超集，欲写 parser, 必须先搞懂正则才行啊。

#23 楼 @luikore 正则一般都是用来做自动化 scanner 的，问题是这东西是鸡肋，词法完全可以手写。

#24 楼 @rasefon 手写的词法是不满足很多优化前提条件的，很可能自己做了一堆无用功

#25 楼 @luikore 什么方面的优化？

#23 楼 @luikore

欲写 parser, 必须先搞懂正则才行啊。

凭什么啊

#26 楼 @rasefon 都说很多了，例如缓存的先决条件，Hopcroft's State Minimization Algorithm, 切换 table driven 或者 control driven, 输出状态机图让你更容易去分析问题... PEG 一般不分离词法分析器而用类似正则的方式去表达终结符，手写的词法就得小心处理以满足 PEG 做缓存的条件。

再说 ruby 的正则引擎能力已经远超过传统意义上的正则表达式了，甚至强于 CFG/PEG. 例如 L=a{n}b{n}c{n}, n=1,2,3,... 是没法用 CFG 文法表达的，用 onigmo 的 lookahead 就可以。

#27 楼 @bhuztez 凭什么不啊

#28 楼 @luikore 正则在词法里只不过分析最底层的字符串，和优化有什么关系。。。

大神们的对白我已经完全听不懂了

手写的：

def expr aa
   ret = true

   if '(' == aa[$curr_iter] 
      $start_status = false
      $curr_iter += 1
      ret &&= expr aa
      return false unless ret
      if ')' == aa[$curr_iter]
         $curr_iter += 1
         ret &&= true
      else
         return false
      end
   elsif '{' == aa[$curr_iter]
      $start_status = false
      $curr_iter += 1
      ret &&= expr aa
      return false unless ret
      if '}' == aa[$curr_iter]
         $curr_iter += 1
         ret &&= true
      else
         return false
      end
   else
      return false if $start_status
   end

   ret
end

def balanced? aa
   $curr_iter = 0
   $start_status = true
   total_len = aa.size
   ret = true

   while $curr_iter < total_len
      ret = expr aa
      return false unless ret
      $start_status = true
   end

   true
end

tc = ["", "()", "{()}", "{}", "{{}}", "({})", "{()}", 
   "(", ")", "(()", "())", "{", "}", "{{}", "{}}", "{(})", "({})(){()}"]

tc.each do |item|
   puts balanced? item.split(//)
end

stack

#30 楼 @rasefon 我已经举了几个静态词法分析的例子啊...

对于动态词法分析，也就是规则是运行时获得的情况。正则引擎就比你手写的更简便，而且能做更多优化。不少正则引擎可以把连续的字节匹配变成 word/dword/qword 的匹配。onigmo 会按情况选择从前往后或者从后往前匹配，手写从后往前就会很怪也不好修改。

#34 楼 @luikore 我大概理解你的意思了，做 ide 需要。做后段优化几乎无用。

#28 楼 @luikore 为啥没法 CFG

#29 楼 @luikore 先学 Earley，再逐步降级成正则，不行啊 ...

前端解析说到底，就是基于两个闭包集合的预测分析，一个 first, 一个 follow，万变不离其宗。

#36 楼 @bhuztez 编译原理讲泵引理的那一章都会说这个例子 https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages#Usage_of_the_lemma

但是 Onigmo 可以 (利用 recursive rule 和 look ahead 两个特性)

R = /\A
  (?<x>a\g<x>*b){0}
  (?=\g<x>)a+(?<y>b\g<y>*c)
\z/x
R =~ 'aabbcc' #=> 匹配
R =~ 'aaabbbccc' #=> 匹配
R =~ 'abcc' #=> 不匹配
R =~ 'aabbc' #=> 不匹配

帖子已经从《Ruby Programming》毫无违和感的过渡到了《编译原理》。。。

#39 楼 @luikore

regex 和 parsing 其实是两个不同的东西的。parsing 是把一段文本转换成语法树，regex 是在一段文本中找到所有符合某种规则的字符串。只不过恰好他们都和 NFA/DFA 扯上关系了。

也就是说 tweak 一下 Earley parser 就可以了

如@luikore所说，不需要 tweak 也可以

我的编译原理还给老师了。。。

正则、状态机、向下递归地层的结构难道不用栈吗？不用栈能够造出正则解释器吗

#43 楼 @jimrokliu 正则文法即 3 型文法，可以和 NFA/DFA 互相等价转化，也即所谓状态机，状态机本身可以不用栈，可以是 2 维表，也可以是 switch/case 结构，甚至 if/else。自顶向下最简单的实现方式就是递归调用，或者可以预计算向前看 1 的表，也即 LL(1)。 构造正则解析器有很多方法，不用栈用图也行。

#41 楼 @bhuztez 和正则引擎一样，很多 parser generator 都有扩展去支持超过 CFG 表示能力的语法。regexp 和 parsing 当然不是一个东西，但 regexp 是 parsing 的手段之一。和 CFG notation, BNF notation 一样，正则表达式也是一种文法的描述语言。

BNF 其实语法限制较多，使用略不方便，所以现在人们更喜欢用有 kleen star 的 regular-expression-like BNF.

另外 BNF 其实可以表示 a{n}b{n}c{n}:

S = A Y
X C = S
A = 'a' | 'a' A
C = 'c' | 'c' C
X = 'ab' | 'a' X 'b'
Y = 'bc' | 'b' Y 'c'

#45 楼 @luikore BNF 能表示 你这个 BNF 表示直接能对应一个 Earley parser，那应该算 context free 才对吧 ...

可以

#46 楼 @bhuztez 不是，context-free 每个规则左边只能有 1 个记号。

#48 楼 @luikore BNF 左边也只能有一个记号才对啊...

#49 楼 @bhuztez 好吧我写的这个也是个扩展了能力的变种...

用堆栈

#44 楼 @rasefon 不错，这部分知识我了解还真不深。

刚学 ruby 练习一下

def balanced? string
  match_rule = {'}' => '{', ')' => '('}
  bracket_stack = []
  string.each do |c|
    bracket_stack.push(c) if ['{', '('].include? c
    brac = bracket_stack.pop if ['}', ')'].include? c
    unless brac == match_rule[c]
      puts "#{c} doesn't match!"
      return
    end
  end
  unless bracket_stack.length == 0 
    puts "some brackets left!"
    return
  else
    puts "yeah! right!"
  end
end

test1 = %w[ { } ( { } ) ( { } ) ]
test2 = %w[ { } ( { } ) ( { ) ]
test3 = %w[ { } ( { }  ( { } ) ]

balanced? test1
balanced? test2
balanced? test3

#50 楼 @luikore

所以

欲学 parser, 必须先搞懂正则才行啊. 欲学 interpreter, 必须先搞懂正则才行啊. 欲学 unification, 必须先搞懂正则才行啊. 欲学 backtracking, 必须先搞懂正则才行啊. 欲学 abstract interpretation, 必须先搞懂正则才行啊. ...

def balanced?(a)
    h = {'{' => '}', '(' => ')', '}' => '', ')' => ''}
    return false unless h[a.shift] == a.pop until a.empty? 
    true
end

看了之前的回复才发现没有考虑 {()()} 的情况，

def balanced?(a)
    h = {'{' => '}', '(' => ')'}
    b = []
    until a.empty?
        e = a.shift
        e == h[b.last] ? b.pop : b << e
    end
    b.empty?
end