题目
Given an expression s includes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression)．Please expand expression to be a string.
样例
s = abc3[a] return abcaaa
s = 3[abc] return abcabcabc
s = 4[ac]dy, return acacacacdy
s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz
### 解题思路
将字符串转换成字符数组，遍历数组，遇到数字的就number = number*10 + c - '0';
遇到'[',将number叫入栈，number清零，
遇到字母，加入栈
遇到']',将调用popStack函数，依据栈顶的数字，将数字后的一切字母重复加入栈，
最后，调用popStack,返回String类型
例如：5[10[ab]AC20[c]]
5 ;stack : ; number = 53 - 48
[ ;stack: 5;number = 0
1;stack: 5; number = 49-48
0;stack: 5; number = 110 + 48-48
[;stack: 5,10; number = 0
a;stack:5, 10; a, number = 0
b ;stack : 5,10, a, b;number = 0
];调用popStack();stack:5, ab,ab,ab,ab,ab,ab,ab,ab,ab,ab;number = 0
A; stack:5, ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A;number = 0
C; stack:5, ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A,C;number = 0
2；stack:5, ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A,C;number = 50-48
0；stack:5, ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A,C;number = 210 + 48-48
[; stack:5, ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A,C,20;number = 0
c;stack:5, ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A,C,20,c;number = 0
];调用popStack();stack:5, ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A,C,c,..,c(20个c);number = 0
];调用popStack();stack: (ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A,C,c,..,c(20个c))*5;
最后，调用popStack()，返回String"ababababababababababACccccccccccccccccccccababababababababababACccccccccccccccccccccababababababababababACccccccccccccccccccccababababababababababACccccccccccccccccccccababababababababababACcccccccccccccccccccc"
### 代码实现
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)) {
//not number = c-'0',因为存在重复次数位数大于1的情况，比如：10[abcd]Ac20[abcde]
//题目不考虑重复次数大于等于100 的情况
//c-'0' c的ascii码减去0 的ascii码
number = number*10 + c - '0';
} else if (c == '[') {
//not stack.push(number);
stack.push(Integer.valueOf(number));
number = 0;
} else if (c == ']') {
//碰到], 得到stack中 的不是整数的字符,此时stack的顶部是数字
String newStr = popStack(stack);
// Integer not int
Integer count = (Integer) stack.pop();
for (int i = 0; i < count; i++) {
stack.push(newStr);
}
} else {
stack.push(String.valueOf(c));
}
}
return popStack(stack);
}
private String popStack(Stack<Object> stack) {
Stack<Object> buffer = new Stack<>();
//将stack中的不为数字的字符加入buffer中 ，因为直接从原来的栈tan加入sb,顺序和最初加入的相反
while (!stack.isEmpty() && (stack.peek() instanceof String)) {
buffer.push(stack.pop());
}
StringBuilder sb = new StringBuilder();
while (!buffer.isEmpty()) {
sb.append(buffer.pop());
}
//转换成String
return sb.toString();
}
}
