新手问题 Ruby Programming 第 11 章练习第 9 题不会，请教高手指点
（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
arr.join =~ /\A( \(\g<1>*\) | \{\g<1>*\} )*\z/x
(一开始没考虑到 '()()' 的情形，由 #9 楼 指正改好了)
#!/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().
用 kleen star 的写法：
X = E*
E = '(' E* ')' | '{' E* '}'
把 E 当成第一个括号组 (\g<1>) 来动态引用
'(' \g<1>* ')' | '{' \g<1>* '}'
再把 escape 和 anchor 补上就是那个正则了
#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 就可以。
手写的：
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
#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' #=> 不匹配
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'
刚学 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
所以
欲学 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