20.有效括号
2019-05-10 本文已影响0人
New_Learner
检测括号对 (),{},[]是否有效。
思路:利用堆栈。遇到左括号压入堆栈,遇到右括号从堆栈弹出并比较。注意(),{},[]在键值上是不连续的。。。小括号是相差1,大括号和中括号都是相差2,不过既然已经假定了输入都是括号。返回错误的情况有,1.括号不匹配;2.堆栈有剩多的左括号;3.堆栈已经用完了,却又出现了右括号。

错误思路:之前我在一个博客中看到一个面试官的说法。对(){}[]分别编码-1,+1,-2,+2,-3,+3。通过计算总和,并保持始终不小于0来保证括号的有效性。然而这个说法是完全错误的,它们之间必然存在最大公约数,这导致了括号之间居然存在隐式的等价关系???如-1 -1 2 居然也是一个有效的括号组?