给出一个表达式
s，此表达式包括数字，字母以及方括号。在方括号前的数字表示方括号内容的重复次数(括号内的内容可以是字符串或另一个表达式)，请将这个表达式展开成一个字符串。
样例
S =
abc3[a]返回abcaaa
S =3[abc]返回abcabcabc
S =4[ac]dy返回acacacacdy
S =3[2[ad]3[pf]]xyz
返回adadpfpfpfadadpfpfpfadadpfpfpfxyz
挑战
你可以不通过递归的方式完成展开吗？
代码
方法1. 非递归 + Stack 从最右边的一组括号开始展开
思路
在从左到右扫描字符串时，当前字符要分4种情况：
- 数字，可以不止一位，计算出完整数字
- 左括号，碰到左括号将当前 number 压入栈存起来，因为括号内也可能有数字，所以要将 number 先清零，然后用来存括号内的数字
- 右括号，碰到右括号表示某一完整括号的结束，要将其中内容展开，然后重新压入栈，所以非递归解法是从最右边的一组括号开始展开的
- 普通字符，直接压入栈中
// 栈中只压人字符和数字
public class Solution {
/**
* @param s an expression includes numbers, letters and brackets
* @return a string
*/
public String expressionExpand(String s) {
Stack<Object> stack = new Stack<>();
int number = 0;
for (char c : s.toCharArray()) {
// 判断字符是否是数字
if (Character.isDigit(c)) {
// 注意 c 不能加''
number = number * 10 + c - '0';
} else if (c == '[') {
// 将 number 强制转换成 Integer 类型压入栈，同时 number 归 0
stack.push(Integer.valueOf(number));
number = 0;
// 每遇到一个右括号就把当前需要扩展的字符串扩展完压入栈
} else if (c == ']') {
String newStr = popStack(stack);
Integer count = (Integer) stack.pop();
// java 自动拆箱将 count 由 Integer 转为int
for (int i = 0; i < count; i++) {
stack.push(newStr);
}
// 字符情况
} else {
// String.valueOf(c) 将 c 强制转换成字符串类型
stack.push(String.valueOf(c));
}
}
return popStack(stack);
}
// popstack 将压入 stack 栈中的字符串以原来顺序输出，注意不包括数字
// 之前压入到栈中的顺序是反的，用 buffer 栈把顺序还原
private String popStack(Stack<Object> stack) {
Stack<String> buffer = new Stack<>();
// stack.peek() 查看栈顶元素而不移除它
// stack 非空且栈顶元素是 String 类型
// 把遇到 number 之前的栈顶所有字符全部压入 buffer 栈
while (!stack.isEmpty() && (stack.peek() instanceof String)) {
buffer.push((String) stack.pop());
}
// StringBuilder动态字符串
StringBuilder sb = new StringBuilder();
// 将压入 buffer 中的字符全部添加到动态字符串 sb 中
while (!buffer.isEmpty()) {
sb.append(buffer.pop());
}
// String 是不可变对象,而 StringBuilder 可变
return sb.toString();
}
}
关于String和StringBuilder区别：
http://www.cnblogs.com/dolphin0520/p/3778589.html
方法2. 递归
思路
递归和非递归一样，需要对当前字符做4种情况的分析，但在4种情况的基础上要额外判断当前字符是否属于当前递归最外围，是否应该参与展开运算；还是处于当前递归最内层，只是单纯把它记录下来，用于下一轮递归
/* 思路：
* 1.split成几个部分
* 2.每一部分分别recursion
* 3.concat
* 递归嵌套太深可能会出现系统栈溢出
* 自己定义栈就不会出现这种问题
* 内存Mermory ：
* 1.Heap Mermory：new int[100], new TreeNode()
* 2.Stack:
* 样例：在一个函数中新建一个结点
* ListNode node = new ListNode(0);
* ListNode(0)存在heap mermory中
* reference存在stack中
*/
public class Solution {
/**
* @param s an expression includes numbers, letters and brackets
* @return a string
*/
public String expressionExpand(String s) {
int number = 0;
// paren 是用来记录读到当前的 c 时,有多少还未配对的左括号
int paren = 0;
String subString = "";
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '[') {
/* paren > 0证明当前字符 c 已经在一个括号里了,
* 需要把 c 用 subString 记录下来,方便递归调用
*/
if (paren > 0) {
/* 在原有的 subString 基础上添加新的字符,生成新的 subString
* 字符串
*/
subString = subString + c;
}
paren++;
} else if (c == ']') {
paren--;
// paren == 0说明到了当前递归层最外围的括号,括号内部要递归
// 同一层内部按照从左往右顺序展开
if (paren == 0) {
// push number * substring to sb
// 调用递归
String expandedString = expressionExpand(subString);
for (int i = 0; i < number; i++) {
sb.append(expandedString);
}
number = 0;
// 同一层递归可能有多组括号，所以subString要清0
subString = "";
// 未到最外围括号，单纯记录右括号
} else {
subString = subString + c;
}
} else if (c >= '0' && c <= '9') {
/* 在本轮递归中数字一定不能在括号中,括号中的数字只是单纯
* 记录下来,括号外的才可以进行字符串多倍扩展
*/
if (paren == 0) {
number = number * 10 + c - '0';
} else {
subString = subString + c;
}
// c 既不是数字也不是括号,只是字符
} else {
// 所有括号之后最结尾的字符
if (paren == 0) {
/* valueOf() 方法用于返回给定参数的原生 Number
* 对象值，参数可以是原生数据类型, String等
*/
sb.append(String.valueOf(c));
// 括号中的字符
} else {
subString = subString + c;
}
}
}
return sb.toString();
}
}
