小算法，能搞定的来拿分!

Question

现有基本字符串：String[] strs={"q1","q2","q3"};
再有一个有规律的字符串：
               String S= "a=q1+q2;b=q2+q3;c=a+q1;d=q1*q3;e=a+b*q3;f=a+b+c+d*e";
首先把字符串S按“；”拆开后会得到一系列的表达式，a=q1+q2 b=q2+q3  c=a+q1 d=q1*q3 e=a+b*q3 f=a+b+c+d*e
这里有一个规律：每一个表达式里面的字符都必须是由基本字符串和前面的表达式中已经出现的字符组成，我的要求如下，现需要把这些表达式全部改为用基本字符串组成。
上面的结果就应该是：
String s1="a=q1+q2;b=q2+q3;c=q1+q2+q1;d=q1*q3;e=q1+q2+(q2+q3)*q3;f=q1+q2+q2+q3+q1+q2+q1+(q1*q3)*(q1+q2+(q2+q3)*q3)";
50分相求。

Answer 1

public class TestOperator { public static void main(String[] args) {
String s = "a=q1+q2;b=q2+q3;c=a+q1;d=q1*q3;e=a+b*q3;f=a+b+c+d*e";
System.out.println(convert(s, new String[] { "a" },
new String[] { "q1+q2" }));
} public static String convert(String opt, String[] keys, String[] values) {
int length = keys.length;
String[] opts = opt.split(";");
if (length == opts.length)
return opt;
String temp = opts[length];
String[] temparr = temp.split("=");
String[] kkeys = new String[length + 1];
String[] vvalues = new String[length + 1];
System.arraycopy(keys, 0, kkeys, 0, length);
System.arraycopy(values, 0, vvalues, 0, length);
String s = temparr[1];
for (int i = 0; i < length; i++) {
if (s.indexOf(keys[i]) != -1) {
int index = s.indexOf(keys[i]);
if((index!=s.length()-1&&"*".equals(s.substring(index+1,index+2)))||(index!=0&&"*".equals(s.substring(index-1,index)))){
s = s.replace(keys[i], "("+values[i]+")");
}else{
s = s.replace(keys[i], values[i]);
}
}
}
vvalues[length] = s;
kkeys[length] = temparr[0];
String ss = "";
for (int i = 0; i < opts.length; i++) {
if (i == length) {
ss += temparr[0] + "=" + s + ";";
} else {
ss += opts[i] + ";";
}
}
return convert(ss, kkeys, vvalues);
}
}

Answer 2

按我的理解，以为楼主S中的表达式可以随便换位的。
好奇能不能拼出来所以写了下算法滥不要笑噢。
毕竟我弄了一个多小时
辛苦啊给点分吧多了括号，懒得再加if、else了将就着看吧
package test;public class TestA {
public static void main(String[] args) {
String[] strs = { "q1", "q2", "q3" };
String aa = "";
String target = "a=q1+q2;b=q2-q3+a;f=a/b+c+d*e;c=a-q1;d=q1*q3;e=a+b/q3";
String flags = "[+][-]*[/]";
System.out.println(TestA.parser(strs, target, flags));
} public static String parser(String[] strs, String target, String flags) {
String[] one = target.split(";");
String[] cloneOne = target.split(";");
for (int i = 0; i < one.length; i++) {
String[] two = one[i].split("=");
String left = two[0]; // e
String right = two[1]; // a+b/q3
int previous = 0;
for (int j = 0; j < right.length(); j++) {
if ((flags.indexOf(right.charAt(j)) > 0)
|| (j == right.length() - 1)) { String firstParam = "";
if (j < (right.length() - 1)) {
firstParam = right.substring(previous, j).replaceAll(
"\\)", "");
} else {
firstParam = right.substring(right.length() - 1);
}
boolean isPrimary = false;
for (int k = 0; k < strs.length; k++) {
// 如果该字符串是原始字符，则继续
if (strs[k].equals(firstParam)) {
isPrimary = true;
previous = j + 1;
break;
}
}
// 如果不是原始字符
if (!isPrimary) {
for (int l = 0; l < cloneOne.length; l++) {
// 如果左字符与目标串中某个键相等，则替换
if (cloneOne[l].split("=")[0].equals(firstParam)) {
// 移动到括号重新开始
if (j < right.length() - 1) {
j = j - 2;
previous++;
} else {
j++;
previous++;
}
one[i] = left
+ "="
+ right.replaceAll(firstParam, "("
+ cloneOne[l].split("=")[1]
+ ")");
right = right.replaceAll(firstParam, "("
+ cloneOne[l].split("=")[1] + ")");
break;
}
}
}
} }
}
String ret = "";
for (int i = 0; i < one.length; i++) {
ret += one[i] + ";";
}
return ret.substring(0, ret.length() - 1);
}
}
输出：
IWAV0055I Java Bean test.TestA started with the main method
a=q1+q2;b=q2-q3+(q1+q2);f=(q1+q2)/(q2-q3+(q1+q2))+((q1+q2)-q1)+(q1*q3)*((q1+q2)+(q2-q3+(q1+q2))/q3);c=(q1+q2)-q1;d=q1*q3;e=(q1+q2)+(q2-q3+(q1+q2))/q3

Answer 3

呵呵，多谢各位相助，不过我提出的问题只是我的问题的一个小缩影而已，实际上我是在写一个类似 解析sql语句的东西，昨天花了半个晚上的时间，自己也写出来了。不过还是要多谢各位！