Given an expressions
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.
Example
s =abc3[a]
returnabcaaa
s =3[abc]
returnabcabcabc
s =4[ac]dy
, returnacacacacdy
s =3[2[ad]3[pf]]xyz
, returnadadpfpfpfadadpfpfpfadadpfpfpfxyz
Solution: 1个stack存数字,1个stack存字母,遇到]时弹出stack。注意数字>9时
public String expressionExpand(String s) {
if(s == null || s.length() == 0){
return "";
}
StringBuilder ans = new StringBuilder();
StringBuilder temp1 = new StringBuilder();
Stack<Character> stack2 = new Stack<Character>();
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if((c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') && stack.empty()){
ans.append(c);
continue;
}
if(c >= '0' && c <= '9'){
int val = 0;
while(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
val = val * 10 + s.charAt(i) - '0';
i++;
}
stack.push(val);
i--;
continue;
}
if(c == ']'){
int count = stack.pop();
while(stack2.peek() != '['){
temp1.append(stack2.pop());
}
stack2.pop();
if(stack.empty()){
for(int j = 0; j < count; j++){
for(int k = temp1.length() - 1; k >= 0; k--){
ans.append(temp1.charAt(k));
}
}
} else{
for(int j = 0; j < count; j++){
for(int k = temp1.length() - 1; k >= 0; k--){
stack2.push(temp1.charAt(k));
}
}
}
temp1.delete(0, temp1.length());
continue;
}
stack2.push(c);
}
return ans.toString();
}