4.10华为第2题解答
题目没有说清楚是否是递归展开的部分是否需要翻转.事实证明题目的意思是整体展开后才反序
重点在于如何展开,想法是递归.如果没有找到数字那么直接输出原字符串,如果找到数字n,说明数字后面
有一对括号.
原来的字符串拆为4部分,第1部分是数字n之前,第2部分是数字n,第3部分是n后面的括号中内容,第4部分是括号后面部分
s=part1+part2+(part3)+part4
递归展开part3,重复n次后挂到part1后面.再挂上part4递归展开的结果得到整个展开式
下面的代码保留了一些调试信息.如果要通过测试,需要将类名改为Main并且将main函数中的
new HuaWeiQ5()...改为new Main()...
import java.util.*;
public class HuaWeiQ5 {
public String expandString(String s) {
boolean findNumber=false;
for(int i=0;i<s.length();i++)
if(Character.isDigit(s.charAt(i))) {
findNumber=true;
break;
}
if(!findNumber) {
StringBuilder sb=new StringBuilder(s);
sb.reverse();
//return sb.toString();
return s;
}
Stack<Character>stack=new Stack<Character>();
int firstDigitPos=-1,lastDigitPos=-1;
int i=0;
while(!Character.isDigit(s.charAt(i)))i++;
firstDigitPos=i;
while(Character.isDigit(s.charAt(i)))i++;
lastDigitPos=i-1;
String part1=s.substring(0,firstDigitPos);
String part2=s.substring(firstDigitPos,lastDigitPos+1);
int leftParentesePos=lastDigitPos+1;
int rightParentesePos=-1;
//s[leftParentesePos]应该是一个括号,我们需要找到与它匹配的括号
stack.push(s.charAt(leftParentesePos));
for(i=leftParentesePos+1;i<s.length();i++) {
if(isLeftParenthese(s.charAt(i)))
stack.push(s.charAt(i));
else if(isRightParenthese(s.charAt(i)))
stack.pop();
if(stack.isEmpty()) {
rightParentesePos=i;
break;}
}
String part3=s.substring(leftParentesePos+1,rightParentesePos);
String part4=s.substring(rightParentesePos+1);
//System.out.println(part1);
//System.out.println(part2);
//System.out.println(part3);
String later=expandString(part4);
int repeatTimes=Integer.parseInt(part2);
StringBuilder sb=new StringBuilder(part1);
part3=expandString(part3);
for(int j=0;j<repeatTimes;j++)
sb.append(part3);
sb.append(later);
return sb.toString();
}
public boolean isLeftParenthese(char ch) {
return ch=='('||ch=='['||ch=='{';
}
public boolean isRightParenthese(char ch) {
return ch==')'||ch==']'||ch=='}';
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//String s="abc3(A)";
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
String ans=new HuaWeiQ5().expandString(s);
System.out.println(ans);
}
} 
投递三环集团等公司6个岗位 >