<p>Solve a given equation and return the value of <code>&#39;x&#39;</code> in the form of a string <code>&quot;x=#value&quot;</code>. The equation contains only <code>&#39;+&#39;</code>, <code>&#39;-&#39;</code> operation, the variable <code>&#39;x&#39;</code> and its coefficient. You should return <code>&quot;No solution&quot;</code> if there is no solution for the equation, or <code>&quot;Infinite solutions&quot;</code> if there are infinite solutions for the equation.</p>

<p>If there is exactly one solution for the equation, we ensure that the value of <code>&#39;x&#39;</code> is an integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> equation = &quot;x+5-3+x=6+x-2&quot;
<strong>Output:</strong> &quot;x=2&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> equation = &quot;x=x&quot;
<strong>Output:</strong> &quot;Infinite solutions&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> equation = &quot;2x=x&quot;
<strong>Output:</strong> &quot;x=0&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= equation.length &lt;= 1000</code></li>
	<li><code>equation</code> has exactly one <code>&#39;=&#39;</code>.</li>
	<li><code>equation</code> consists of integers with an absolute value in the range <code>[0, 100]</code> without any leading zeros, and the variable <code>&#39;x&#39;</code>.</li>
	<li>The input is generated that if there is a single solution, it will be an integer.</li>
</ul>

class Solution {
    struct Expression {
        int32_t concrete_coefficient;
        int32_t symbolic_coefficient;
    };

    Expression parseExpression(const string& equation, size_t& i) {
        Expression result = {0, 0};

        for (; i < equation.size();) {
            if (equation[i] == '=') {
                i++;
                break;
            }
            
            bool negate = (equation[i] == '-');
            if (equation[i] == '-' || equation[i] == '+') {
                i++;
            }

            size_t j = i;
            int32_t current_coefficient = 0;
            bool parsed = false;
            for (; j < equation.size(); j++) {
                if (isdigit(equation[j])) {
                    current_coefficient *= 10;
                    current_coefficient += equation[j] - '0';
                } else if (equation[j] == 'x') {
                    if (j == i) {
                        current_coefficient = 1;
                    }

                    if (negate) {
                        result.symbolic_coefficient -= current_coefficient;
                    } else {
                        result.symbolic_coefficient += current_coefficient;
                    }
                    j++;
                    parsed = true;
                    break;
                } else if (equation[j] == '+' || equation[j] == '-' || equation[j] == '=') {
                    if (negate) {
                        result.concrete_coefficient -= current_coefficient;
                    } else {
                        result.concrete_coefficient += current_coefficient;
                    }
                    parsed = true;
                    break;
                }
            }
            if (j == equation.size() && !parsed) {
                if (negate) {
                    result.concrete_coefficient -= current_coefficient;
                } else {
                    result.concrete_coefficient += current_coefficient;
                }
            }

            i = j;
        }

        return result;
    }

public:
    string solveEquation(string equation) {
        size_t i = 0;
        Expression lhs = parseExpression(equation, i);
        Expression rhs = parseExpression(equation, i);

        Expression aggregated = {lhs.concrete_coefficient - rhs.concrete_coefficient, 
                                 lhs.symbolic_coefficient - rhs.symbolic_coefficient};
        if (aggregated.concrete_coefficient == 0 && aggregated.symbolic_coefficient == 0) {
            return "Infinite solutions";
        }
        if (aggregated.symbolic_coefficient == 0) {
            return "No solution";
        }
        return string("x=") + to_string(-aggregated.concrete_coefficient / aggregated.symbolic_coefficient);
    }
};
7300