新手问题 Ruby Programming 第 11 章练习第 9 题不会,请教高手指点

yltian · 2013年11月25日 · 最后由 stevep 回复于 2013年11月28日 · 6077 次阅读

(9)一个数组存放了(,),{,}4 种元素,请定义一个 balanced?方法,检查这个数组的括号是否对称,所谓的括号是否对称是指:

  • (的数量与)相同。
  • {的数量与}相同。
  • ()的对应关系和{}没有交叉。

我能想到的方法是:一个圆括号栈,一个花括号栈,把数组的符号一个一个压到相应的栈,遇到相对的一对括号就一对整个 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 我看到正则表达式就头疼。

#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

#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
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册