简单消除内嵌括号的方法

【出自BD面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

给定一个如下格式的字符串：（1，（2，3），（4，（5，6），7）），括号内的元素可以是数字，也可以是另一个括号，实现一个算法消除嵌套的括号，例如把上面的表达式变成（1，2，3，4，5，6，7），如果表达式有误，则报错。

分析与解答：

从问题描述可以看出，这道题要求实现两个功能：一个是判断表达式是否正确，另一个是消除表达式中嵌套的括号。对于判定表达式是否正确这个问题，可以从如下几个方面来入手：首先，表达式中只有数字、逗号和括号这几种字符，如果有其他的字符出现，则是非法表达式；其次，判断括号是否匹配，如果碰到‘（’，则把括号的计数器的值加上1；如果碰到‘）’，那么判断此时计数器的值，如果计数器的值大于1，则把计数器的值减去1，否则为非法表达式，当遍历完表达式后，括号计数器的值为0，则说明括号是配对出现的，否则括号不配对，表达式为非法表达式。对于消除括号这个问题，可以通过申请一个额外的存储空间，在遍历原字符串的时候把除了括号以外的字符保存到新申请的额外的存储空间中，这样就可以去掉嵌套的括号了。需要特别注意的是，字符串首尾的括号还需要保存。实现代码如下：(www.xing528.com)

程序的运行结果如下：

（1，（2，3），（4，（5，6），7））去除嵌套括号后为：（1，2，3，4，5，6，7）

算法性能分析：

这种方法对字符串进行了一次遍历，因此时间复杂度为O（N）（其中，N为字符串的长度）。此外，这种方法申请了额外的N+1个存储空间，因此空间复杂度也为O（N）。