[leetcode] 640. Solve the Equation

Description

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"      

分析

• 等式左邊sign=1，等式右邊sign=-1；b用來累加數，a用來累加符号x上的數。然後-b/a就是結果了哈，注意無解和無窮解的情況。無解a=0&&b!=0,無窮解a=0&&b=0。

代碼

class Solution {
public:
    string solveEquation(string equation) {
        int n=equation.size();
        int j=0;
        int sign=1;
        int b=0,a=0;
        for(int i=0;i<n;i++){
            if(equation[i]=='+'||equation[i]=='-'){
                if(i>j){
                    b+=stoi(equation.substr(j,i-j))*sign;
                }
                j=i;
            }else if(equation[i]=='x'){
                if(i==j||equation[i-1]=='+'){
                    a+=sign;
                }else if(equation[i-1]=='-'){
                    a-=sign;
                }else{
                    a+=stoi(equation.substr(j,i-j))*sign;
                }
                j=i+1;
            }else if(equation[i]=='='){
                if(i>j){
                    b+=stoi(equation.substr(j,i-j))*sign;
                }
                sign=-1;
                j=i+1;
            }
        }
        if(j<n) b+=stoi(equation.substr(j))*sign;
        if(a==0&&b==a) return "Infinite solutions";
        if(a==0&&a!=b) return "No solution";
        return "x="+to_string(-b/a);
    }
};      

參考文獻