問題：

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的系數合并起來，將常數合并起來，化簡成ax=b的形式來求解。

例：
x + 5 -2x = 6-3x;
leftPart：tokens= {x，+ 5，-2x}; 系數為x = 1-2 = -1; 常數= 5;
rightPart：tokens = {6，-3x}; 系數為x = -3; 常數= 6;

最終結果=（6-5）/（-1 - （ - 3））

class Solution { //12ms
? ? public String solveEquation(String equation) {
? ? ? ? String[] parts = equation.split("=");
? ? ? ? int[] leftPart = evaluate(parts[0]);
? ? ? ? int[] rightPart = evaluate(parts[1]);
? ? ? ? if (leftPart[0] == rightPart[0] && leftPart[1] == rightPart[1]){
? ? ? ? ? ? return "Infinite solutions";
? ? ? ? }else if (leftPart[0] == rightPart[0]){
? ? ? ? ? ? return "No solution";
? ? ? ? }
? ? ? ? return "x=" + (rightPart[1] - leftPart[1]) / (leftPart[0] - rightPart[0]);
? ? }
? ? public int[] evaluate(String str){
? ? ? ? String[] tokens = str.split("(?=[+-])");//（）匹配組; ？=匹配并包含在res中; [+ - ]表示+或 - ;
? ? ? ? int[] res = new int[2];//記錄系數為x; 系數為常數
? ? ? ? for (String token : tokens){
? ? ? ? ? ? if (token.equals("+x") || token.equals("x")){
? ? ? ? ? ? ? ? res[0] ++;// x表示1x
? ? ? ? ? ? }else if (token.equals("-x")){
? ? ? ? ? ? ? ? res[0] --;
? ? ? ? ? ? }else if (token.contains("x")){
? ? ? ? ? ? ? ? res[0] += Integer.parseInt(token.substring(0,token.length() - 1));
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? res[1] += Integer.parseInt(token);
? ? ? ? ? ? }

? ? ? ? }
? ? ? ? return res;
? ? }
}

② 在discuss中看到的，思路相同。

class Solution { //9ms
? ? public String solveEquation(String equation) {
? ? ? ? if(equation == null || equation.length() == 0) return "No solution";
? ? ? ? String[] sides = equation.split("=");
? ? ? ? int[] left = parse(sides[0]), right = parse(sides[1]);
? ? ? ? if(left[0] == right[0]) {
? ? ? ? ? ? if(left[1] == right[1]) return "Infinite solutions";
? ? ? ? ? ? return "No solution";
? ? ? ? }
? ? ? ? int val = (right[1] - left[1]) / (left[0] - right[0]);
? ? ? ? return "x=" + val;
? ? }
? ??
? ? private int[] parse(String s) {
? ? ? ? int sign = 1, val = 0;
? ? ? ? int[] res = new int[2];
? ? ? ? for(int i = 0; i < s.length(); i ++) {
? ? ? ? ? ? char c = s.charAt(i);
? ? ? ? ? ? if(c == 'x') {
? ? ? ? ? ? ? ? if(i == 0) res[0] ++;
? ? ? ? ? ? ? ? else if(s.charAt(i-1) == '-' || s.charAt(i-1) == '+') res[0] += sign;
? ? ? ? ? ? ? ? else res[0] += sign * val;
? ? ? ? ? ? ? ? val = 0;
? ? ? ? ? ? } else if(c == '-' || c == '+') {
? ? ? ? ? ? ? ? res[1] += sign * val;
? ? ? ? ? ? ? ? val = 0;
? ? ? ? ? ? ? ? sign = c == '-' ? -1 : 1;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? val = val * 10 + c - '0';
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? res[1] += sign * val;
? ? ? ? return res;
? ? }
}