題目
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
### 解題思路
將字符串轉(zhuǎn)換成字符數(shù)組癣漆，遍歷數(shù)組涡匀，遇到數(shù)字的就number = number*10 + c - '0';
遇到'[',將number叫入棧友扰，number清零腮出，
遇到字母，加入棧
遇到']',將調(diào)用popStack函數(shù)肛走，依據(jù)棧頂?shù)臄?shù)字恶复，將數(shù)字后的一切字母重復(fù)加入棧详羡，
最后州弟，調(diào)用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
];調(diào)用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
];調(diào)用popStack();stack:5, ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A,C,c,..,c(20個(gè)c);number = 0
];調(diào)用popStack();stack: (ab,ab,ab,ab,ab,ab,ab,ab,ab,ab,A,C,c,..,c(20個(gè)c))*5;
最后呆馁，調(diào)用popStack()桐经，返回String"ababababababababababACccccccccccccccccccccababababababababababACccccccccccccccccccccababababababababababACccccccccccccccccccccababababababababababACccccccccccccccccccccababababababababababACcccccccccccccccccccc"
### 代碼實(shí)現(xiàn)
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',因?yàn)榇嬖谥貜?fù)次數(shù)位數(shù)大于1的情況毁兆，比如：10[abcd]Ac20[abcde]
//題目不考慮重復(fù)次數(shù)大于等于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中 的不是整數(shù)的字符,此時(shí)stack的頂部是數(shù)字
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中的不為數(shù)字的字符加入buffer中 浙滤，因?yàn)橹苯訌脑瓉?lái)的棧tan加入sb,順序和最初加入的相反
while (!stack.isEmpty() && (stack.peek() instanceof String)) {
buffer.push(stack.pop());
}
StringBuilder sb = new StringBuilder();
while (!buffer.isEmpty()) {
sb.append(buffer.pop());
}
//轉(zhuǎn)換成String
return sb.toString();
}
}
