https://leetcode.com/problems/solve-the-equation/#/description
Solve a given equation and return the value of
http://www.cnblogs.com/grandyang/p/7350578.html
X. Use regex
https://leetcode.com/articles/solve-the-equation/
还有大神巧妙地运用了regrex中的奇淫技巧。
比如：x +5 -2x = 6 -3x; 那么运用了 rex 之后，
左边的表达式 : tokens= { x, +5, -2x }; x的系数 = 1-2 =-1; 常数 = 5;
右边的表达式: tokens= { 6, -3x }; x的系数 = -3; 常数 = 6;
为啥 exp.split("(?=[-+])"); 得到的是包含+/-的token呢？可以看看stackoverflow的解答：https://stackoverflow.com/questions/10804732/what-is-the-difference-between-and-in-regex
https://leetcode.com/articles/solve-the-equation/
Solve a given equation and return the value of
x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable x and its coefficient.
If there is no solution for the equation, return "No solution".
If there are infinite solutions for the equation, return "Infinite solutions".
If there is exactly one solution for the equation, we ensure that the value of
x is an integer.
Example 1:
Input: "x+5-3+x=6+x-2" Output: "x=2"
Example 2:
Input: "x=x" Output: "Infinite solutions"
Example 3:
Input: "2x=x" Output: "x=0"
Example 4:
Input: "2x+3x-6x=x+2" Output: "x=-1"
Example 5:
Input: "x=x+2" Output: "No solution"
这道题给了我们一个用字符串表示的方程式，让我们求出x的解，根据例子可知，还包括x有无穷多个解和x没有解的情况。解一元一次方程没什么难度，难点在于处理字符串，如何将x的系数合并起来，将常数合并起来，化简成ax=b的形式来求解。博主最开始的思路是先找到等号，然后左右两部分分开处理。由于要化成ax=b的格式，所以左半部分对于x的系数都是加，右半部分对于x的系数都是减。同理，左半部分对于常数是减，右半部分对于常数是加。
那么我们就开始处理字符串了，我们定义一个符号变量sign，初始化为1，数字变量num，初始化为-1，后面会提到为啥不能初始化为0。我们遍历每一个字符，如果遇到了符号位，我们看num的值，如果num是-1的话，说明是初始值，没有更新过，我们将其赋值为0；反之，如果不是-1，说明num已经更新过了，我们乘上当前的正负符号值sign。这是为了区分"-3"和"3+3"这种两种情况，遇到-3种的符号时，我们还不需要加到b中，所以num此时必须为0，而遇到3+3中的加号时，此时num已经为3了，我们要把前面的3加到b中。
遇到数字的时候，我们还是要看num的值，如果是初始值，那么就将其赋值为0，然后计算数字的时候要先给num乘10，再加上当前的数字。这样做的原因是常数不一定都是个位数字，有可能是两位数或者三位数，这样做才能正确的读入数字。我们在遇到数字的时候并不更新a或者b，我们只在遇到符号位或者x的时候才更新。这样如果最后一位是数字的话就会产生问题，所以我们要在字符串的末尾加上一个+号，这样确保了末尾数字会被处理。
遇到x的时候比较tricky，因为可能是x, 0x, -x这几种情况，我们还是首先要看num的值是否为初始值-1，如果是的话，那么就可能是x或-x这种情况，我们此时将num赋值为sign；如果num不是-1，说明num已经被更新了，可能是0x, -3x等等，所以我们要将num赋值为num*sign。这里应该就明白了为啥不能将num初始化为0了，因为一旦初始化为0了，就没法区分x和0x这两种情况了。
那么我们算完了a和b，得到了ax=b的等式，下面的步骤就很简单了，只要分情况讨论得出正确的返回结果即可
https://www.cnblogs.com/seyjs/p/9660467.html
本题的思路就是解析字符串，然后是小学时候学的解方程的思想，以"2x+3x-6x+1=x+2"，先把左右两边的x项和非x项进行合并，得到"-x+1=x+2"，接下来就是移项，把x项移到左边，常数项移到右边，得到"2x=-1",最后的解就是x=-1/2。对于任意一个表达式ax+b = cx+d来说，最终都能得到解x=(d-b)/(a-c)，这里要对(a-c)是否为0做判断，同时根据(d-b)是否为0等到Infinite solutions，No solution，常规解三种结果。
public String coeff(String x) {
if (x.length() > 1 && x.charAt(x.length() - 2) >= '0' && x.charAt(x.length() - 2) <= '9')
return x.replace("x", "");
return x.replace("x", "1");
}
public String solveEquation(String equation) {
String[] lr = equation.split("=");
int lhs = 0, rhs = 0;
for (String x : breakIt(lr[0])) {
if (x.indexOf("x") >= 0) {
lhs += Integer.parseInt(coeff(x));
} else
rhs -= Integer.parseInt(x);
}
for (String x : breakIt(lr[1])) {
if (x.indexOf("x") >= 0)
lhs -= Integer.parseInt(coeff(x));
else
rhs += Integer.parseInt(x);
}
if (lhs == 0) {
if (rhs == 0)
return "Infinite solutions";
else
return "No solution";
}
return "x=" + rhs / lhs;
}
public List<String> breakIt(String s) {
List<String> res = new ArrayList<>();
String r = "";
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '+' || s.charAt(i) == '-') {
if (r.length() > 0)
res.add(r);
r = "" + s.charAt(i);
} else
r += s.charAt(i);
}
res.add(r);
return res;
}
X. Use regex
https://leetcode.com/articles/solve-the-equation/
public String coeff(String x) {
if (x.length() > 1 && x.charAt(x.length() - 2) >= '0' && x.charAt(x.length() - 2) <= '9')
return x.replace("x", "");
return x.replace("x", "1");
}
public String solveEquation(String equation) {
String[] lr = equation.split("=");
int lhs = 0, rhs = 0;
for (String x : lr[0].split("(?=\\+)|(?=-)")) {
if (x.indexOf("x") >= 0) {
lhs += Integer.parseInt(coeff(x));
} else
rhs -= Integer.parseInt(x);
}
for (String x : lr[1].split("(?=\\+)|(?=-)")) {
if (x.indexOf("x") >= 0)
lhs -= Integer.parseInt(coeff(x));
else
rhs += Integer.parseInt(x);
}
if (lhs == 0) {
if (rhs == 0)
return "Infinite solutions";
else
return "No solution";
} else
return "x=" + rhs / lhs;
}
https://blog.csdn.net/huanghanqian/article/details/77340481还有大神巧妙地运用了regrex中的奇淫技巧。
比如：x +5 -2x = 6 -3x; 那么运用了 rex 之后，
左边的表达式 : tokens= { x, +5, -2x }; x的系数 = 1-2 =-1; 常数 = 5;
右边的表达式: tokens= { 6, -3x }; x的系数 = -3; 常数 = 6;
为啥 exp.split("(?=[-+])"); 得到的是包含+/-的token呢？可以看看stackoverflow的解答：https://stackoverflow.com/questions/10804732/what-is-the-difference-between-and-in-regex
?: is for non capturing group
?= is for positive look ahead
?! is for negative look ahead
?<= is for positive look behind
?<! is for negative look behind?:Match expression but do not capture it.?=Match a suffix but exclude it from capture.?!Match if suffix is absent.
e.g. x+5-3+x=6+x-2
- Firstly, we split the equation by "=":
leftPartis x+5-3+x;rightPartis 6+x-2; - Secondly, we sum up coefficient and the rest numbers separately, i.e.
leftValsis 2x + 2, i.e., [2, 2];rightValsis x + 4, i.e., [1, 4]; - Thirdly, we solve the simplified equation by moving all elements to the left of "=",
cntX = leftVals[0] - rightVals[0];, i.e., 2 - 1 = 1,cntNum = leftVals[1] - rightVals[1];, i.e., 2 - 4 = -2,cntX * x + cntNum = 0, i.e., 1 * x + (-2) = 0,x = (-cntNum) / cntX, i.e., x = 2
Please note that
https://leetcode.com/problems/solve-the-equation/discuss/105311/Concise-Java-Solutionexp.split(""); split exp by 0-length string ("a+b-c" to "a", "+", "b", "-", "c")exp.split("(?=[-+])");split exp by 0-length string only if they are follow by "-" or "+" ("a+b-c" to "a", "+b", "-c")public String solveEquation(String equation) {
int[] res = evaluateExpression(equation.split("=")[0]),
res2 = evaluateExpression(equation.split("=")[1]);
res[0] -= res2[0];
res[1] = res2[1] - res[1];
if (res[0] == 0 && res[1] == 0) return "Infinite solutions";
if (res[0] == 0) return "No solution";
return "x=" + res[1]/res[0];
}
public int[] evaluateExpression(String exp) {
String[] tokens = exp.split("(?=[-+])");
int[] res = new int[2];
for (String token : tokens) {
if (token.equals("+x") || token.equals("x")) res[0] += 1;
else if (token.equals("-x")) res[0] -= 1;
else if (token.contains("x")) res[0] += Integer.parseInt(token.substring(0, token.indexOf("x")));
else res[1] += Integer.parseInt(token);
}
return res;
}public String coeff(String x) { if (x.length() > 1 && x.charAt(x.length() - 2) >= '0' && x.charAt(x.length() - 2) <= '9') return x.replace("x", ""); return x.replace("x", "1"); } public String solveEquation(String equation) { String[] lr = equation.split("="); int lhs = 0, rhs = 0; for (String x: lr[0].split("(?=\\+)|(?=-)")) { if (x.indexOf("x") >= 0) { lhs += Integer.parseInt(coeff(x)); } else rhs -= Integer.parseInt(x); } for (String x: lr[1].split("(?=\\+)|(?=-)")) { if (x.indexOf("x") >= 0) lhs -= Integer.parseInt(coeff(x)); else rhs += Integer.parseInt(x); } if (lhs == 0) { if (rhs == 0) return "Infinite solutions"; else return "No solution"; } else return "x=" + rhs / lhs; }X.
https://leetcode.com/articles/solve-the-equation/
We treat the given equation as if we're bringing all the
x's on the left hand side and all the rest of the numbers on the right hand side as done below for an example.x+5-3+x=6+x-2x+x-x=6-2-5+3
Thus, every
x in the left hand side of the given equation is treated as positive, while that on the right hand side is treated as negative, in the current implementation. Likewise, every number on the left hand side is treated as negative, while that on the right hand side is treated as positive. Thus, by doing so, we obtain all the x's in the new and all the numbers in the new of the original equation.
Further, in case of an
x, we also need to find its corresponding coefficients in order to evaluate the final effective coefficient of x on the left hand side. We also evaluate the final effective number on the right hand side as well.
Now, in case of a unique solution, the ratio of the effective and gives the required result. In case of infinite solutions, both the effective and turns out to be zero e.g.
x+1=x+1. In case of no solution, the coefficient of x() turns out to be zero, but the effective number on the is non-zero.public String coeff(String x) { if (x.length() > 1 && x.charAt(x.length() - 2) >= '0' && x.charAt(x.length() - 2) <= '9') return x.replace("x", ""); return x.replace("x", "1"); } public String solveEquation(String equation) { String[] lr = equation.split("="); int lhs = 0, rhs = 0; for (String x: breakIt(lr[0])) { if (x.indexOf("x") >= 0) { lhs += Integer.parseInt(coeff(x)); } else rhs -= Integer.parseInt(x); } for (String x: breakIt(lr[1])) { if (x.indexOf("x") >= 0) lhs -= Integer.parseInt(coeff(x)); else rhs += Integer.parseInt(x); } if (lhs == 0) { if (rhs == 0) return "Infinite solutions"; else return "No solution"; } return "x=" + rhs / lhs; } public List < String > breakIt(String s) { List < String > res = new ArrayList < > (); String r = ""; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '+' || s.charAt(i) == '-') { if (r.length() > 0) res.add(r); r = "" + s.charAt(i); } else r += s.charAt(i); } res.add(r); return res; }https://discuss.leetcode.com/topic/95207/easiest-java-solution-self-explanatory
public String solveEquation(String equation) {
if(equation == null || equation.length() == 0) {
return equation;
}
String[] parts = equation.split("=");
String left = parts[0];
String right = parts[1];
int[] lco = process(left);
int[] rco = process(right);
int x = lco[0] - rco[0];
int co = rco[1] - lco[1];
if(x == 0) {
if(co == 0) {
return "Infinite solutions";
} else {
return "No solution";
}
} else if(co == 0) {
return "x=0";
} else {
return "x=" + "" + String.valueOf((int) (co/x));
}
}
public int[] process(String left) {
char[] array = left.toCharArray();
int length = array.length;
int prev = 1;
int x = 0;
int co = 0;
int cur = 0;
for(int i = 0; i < length; ++i) {
if(array[i] != 'x') {
if(array[i] == '-') {
prev = -1;
} else if(array[i] == '+') {
prev = 1;
} else {
cur = 0;
while(i < length && array[i] != '+' && array[i] != '-' && array[i] != 'x') {
cur = cur * 10 + ((int)(array[i] - '0'));
i++;
}
if(i < length && array[i] == 'x') {
x = x + prev * ((int) (cur));
i++;
} else {
co = co + prev * ((int) (cur));
}
--i;
}
} else {
x += prev;
}
}
return new int[]{x, co};
}