关于字符串操作的一个小例子递归实现荣码一生

字符串在.NET中项目中非常常用。关于String的介绍就不多说了。

背景：今天和同事讨论一个问题，去除括号的问题。

问题描述：一段字符串，去除字符串中小括号中的内容，小括号可能有嵌套情况。

解决思路：1、先去除最内层的小括号；2、进行完第一步之后得到新的字符串，再执行第一步。3、直到最后没有括号。

代码：

测试示例：

输出结果：应该输出“110kV1#母分开关由运行改热备用”

结果确实输出了“110kV1#母分开关由运行改热备用”

总结：1、使用了String的IndexOf、LastIndexOf、SubString、Replace等函数；

2、运用了递归调用。

今天看《代码大全》，找到一个解决本问题的一个方法。

思路：因为“（”和“）”是成对出现的，所以可以利用这一特点。

代码：

使用Delete函数输出为：“110kV1#母分开关由运行改热备用”

应该输出：“110kV1#母分开关由运行改热备用，1111”.

对Delete就行修改，名字改为IsLegal，IsLegal函数用于判断字符串中的“（”和“）”是否成对出现，即是否是合法的字符串：代码如下

思路：与上面看代码大全的思路一样。

代码：

最开始时示意图：

总结：采用今天的方法，代码会稍微多了几行，但是递归调用的次数明显减少。对自己写过的代码不断优化，重构是一件幸福的事。如果以后发现更好的办法，我会在加在本博客后面的。

代码修改：主要修改DeleteTwo方法。代码如下：

对GetIndex方法的修改主要是为了防止，输入不合法的情况。当‘（’和‘）’不匹配时，提示报错。红色部分就是添加的代码。

需要对递归进行优化，尾递归优化在于使堆栈可以不用保存上一次的返回地址/状态值，从而把递归函数当成一个普通的函数调用。

递归实际上是依赖上次的值，去求下次的值。 如果我们能把上次的值保存起来，在下次调用时传入，而不直接引用函数返回的值。 从而使堆栈释放，也就达到了尾递归优化的目的。

在算法中引入StringBuilder储存上次函数的值，从而使堆栈不用保存上一次返回的地址/状态值，达到优化的目的。代码如下：