To almost all of us solving sets of linear equations is quite obviously the most exciting bit of linear algebra. Benny does not agree though and wants to write a quick program to solve his homework problems for him. Unfortunately Benny's lack of interest in linear algebra means he has no real clue on how to go about this. Fortunately, you can help him!

Write a method ```solve``` that accepts a list of linear equations that your method will have to solve. The output should be a map (a `Map` object in JavaScript) with a value for each variable in the equations. If the system does not have a unique solution (has infinitely many solutions or is unsolvable), return ```null``` (`None` in python).

For example :  
  
"2x + 4y + 6z = 18"  
"3y + 3z = 6"  
"x + 2y = z - 3"
  
should result in a map :  
  
x = 2  
y = -1  
z = 3  
  
Possible input equations have the following rules:  
-   Only the plus and minus operators are used on both the left and right hand side of the equation.  
-   Both sides of the equation can have variables; One variable can appear in multiple terms, on both sides.
-   Variable names are strings of arbitrary length.  
-   All coefficients are integers and generally fall within the range of -150 to 150, with a few ranging from -1000 to 1000. Free terms are integers in range -20000 to 20000.  
-   Equations do not necessarily have variables.  
-   Equations have exactly one operator (+ or -) between terms.  


Comparisons are performed with accuracy of `1e-6`.

**Note on numerical stability:**

There are many possible ways to solve a system of linear equations. One group of such algorithms is based on reduction and elimination methods. If you are going to use any of these, remember that such algorithms are in general *numerically unstable*, i.e. division operations repeated over and over introduce inaccuracies which accumulate from row to row. As a result it might occur that some value which is expected to be zero is actually larger, for example, `2.5e-10`. Such inaccuracies tend to be bigger in large equation systems, and random tests check systems of up to 26 equations. If it happens that small tests pass for you, and large tests fail, it probably means that you did not account for inaccuracies correctly.
Also note that tests do not depend on any reference solution, so the way how test cases are generated _is numrically stable_ - the only source of inaccuracies is your solution, and you need to account for it.

```if:python
___Note for python users:___

`numpy` module has been disabled, so that the task matches the one of the other languages. There is an anti-cheat measure about that, so you won't be able to import some other modules too (either way, you shouldn't need any module to solve this kata...)
```

Difficulty: interview

Starter code:

def solve(*equations):
	

Solutions:
from collections import defaultdict
from functools import reduce
import re

P_EQ = re.compile("(?P<eq>=)|(?P<coef>[+-]?\d*)(?P<var>[a-zA-Z]*)")


def solve(*equations):
    
    eqsMap = list(map(parse, equations))                         # Transform each string in a dict {'var': coef}
    vars   = reduce(set.union, (set(e) for e in eqsMap))         # Extract all the variables
    vars   = list(set(vars)-{''}) + ['']                         # Push the "constants" at the end of the list
    
    if len(vars)-1 > len(equations): return None                 # Not enough equations to solve the system
    
    m = [ [eqm[v] for v in vars] for eqm in eqsMap]              # Build the matrix
    
    return solveMatrix(m, vars)                                  # Solve using Gauss elimination
    

def parse(eq):
    rev, dct = 1, defaultdict(int)
    for m in P_EQ.finditer(eq.replace(" ","")):
        if m['eq']:
            rev = -1
        else:
            gc, gv = m['coef'], m['var']
            if gc or gv:
                coef = 1 if not gc or gc == '+' else -1 if gc == '-' else int(gc)
                dct[ m['var'] ] += coef * rev
    return dct


def solveMatrix(m, vars):
    
    EPS    = 1e-10
    pivots = {}                                                  # dict of the indexes of the pivots (avoid to have to move the raws)
    toDo   = set(range(len(m)))                                  # set with the indexes of all the lines where the pivot will have to be sought for
    
    for y in range(len(vars)-1):                                 # "-1" to avoid the constants
        
        _,px = max( ((abs(m[x][y]),x) for x in toDo if abs(m[x][y]) > 0), default=(-1,-1))
        
        if px == -1: continue                                    # No pivot found
        pivots[px] = y
        toDo.remove(px)
        
        maxP, m[px][y] = m[px][y], 1
        for j in range(y+1,len(vars)):                           # Update the line of the current pivot
            m[px][j] /= maxP
            if abs(m[px][j]) < EPS: m[px][j] = 0                 # Handle floating point errors
        
        for x in range(0,len(m)):                                # Update all the lines, doing the elimination
            if x==px: continue                                   # Skip the line of the current pivot
            
            coef, m[x][y] = m[x][y], 0
            for j in range(y+1,len(vars)):                       # Update the line of the current pivot
                m[x][j] -= coef * m[px][j]
                if abs(m[x][j]) < EPS: m[x][j] = 0               # Handle floating point errors, again...
        
    
    solvedDct = {}
    for x in range(len(m)):                                      # Build the solution dict
        yP = pivots.get(x, None)
        if yP is None: continue
        
        solvedDct[ vars[yP] ] = -m[x][-1]
    
    if len(solvedDct) == len(vars)-1: return solvedDct           # Valid only if all the variables have been used as pivots 


from fractions import Fraction
a=0
variable=[]
def solve(*equations):
    
    sq = [i for i in equations]
    print(sq)
    
    def extract_number(s):
        temp = ''
        variable = ''
        L=[]
        for i in range(len(s)):
            try:
                if s[i] in ['+','-'] and temp=='':
                    temp+=s[i];
                    if variable!='':L.append(variable);variable=''
                elif s[i] in ['+','-'] and temp!='':   #2x=2-4y
                    L.append(temp);temp=s[i]
                else:
                    temp+=str(int(s[i]))
            except:
                if s[i] not in ['+','-','=']:variable+=s[i]
                if len(L)==0 and temp=='':L.append('1')                      #x+5=9
                elif temp in ['+','-']:
                    L.append(temp+'1')                    #7+x=9
                elif temp!='' and s[i]!='=':L.append(temp);                  #7x+8y=9
                elif temp!='' and s[i]=='=':L.extend([temp,'='])             #7x+8=9
                elif temp=='' and s[i]=='=':
                    if variable!='': 
                        L.append(variable);variable=''
                    L.extend(['='])
                else:pass
                temp=''
    
        if temp!='':L.append(temp)
        if variable!='':L.append(variable)
        return L
    
    def refine(raw_matrix):
        refine_dict = dict({})
        flag=0
        num=0
        refine_dict['constant']=0
        for i in raw_matrix:
            try:
                if num!=0 and str(int(i))!='':refine_dict['constant']+=num
                if flag==0:
                    num=int(i)
                else:
                    num=-int(i)
            except:
                if i!='=':
                    if i not in refine_dict.keys():
                        refine_dict[i]=num
                    else:
                        refine_dict[i]+=num
                    num=0
                else:
                    flag=1
        if num!=0:
            refine_dict['constant']+=num
        else:
            refine_dict['constant']+=0
        return refine_dict
    
    def reduction(List_of_dict):
        L=[]
        max_number=0;max_dict=dict({})
        for findout in range(len(List_of_dict)):
            if len(List_of_dict[findout])>max_number:
                max_number=len(List_of_dict[findout])
                max_dict = List_of_dict[findout]
        nonlocal variable
        variable = [i for i in max_dict.keys()][::-1]
        insert = 0
        for i in List_of_dict:
            keys_list=[m for m in i.keys()]
            temp_list=[]
            for j in variable:
                try:
                    temp_list.append(i[j])
                    keys_list.remove(j)
                except:
                    temp_list.append(0)
            for k in keys_list:
                variable.insert(-1,k)
                temp_list.append(i[k])
            L.append(temp_list)          
        
        print(variable)
        
        for i in range(len(List_of_dict)):
            if L[i][i]==0:
                for j in range(i,len(List_of_dict)):
                    if L[j][i]!=0:
                        temp_list = L[i]
                        L[i] = L[j]
                        L[j] = temp_list
                        break
            a=L[i][i]
            if i==len(variable)-1 and a==0:return L
            if L[i][:i+1]==[0]*(i+1) and L[i][-1]!=0 :return None
            if L[i]==[0]*(len(L[i])) and i<len(variable)-1:return None
            L[i] = list(map(lambda x:Fraction(x,a),L[i]))
            K = [num for num in range(len(List_of_dict))]
            del K[i]
            for j in K:
                if i<len(variable)-1:
                    L[j]=[L[j][index]-L[i][index]*Fraction(L[j][i],L[i][i]) for index in range(len(L[j]))]
                else:
                    if a!=0:
                        return None
        return L
    
    
    def sol(equation):
        L=[]
        for s in equation:
            L.append(refine(extract_number(s)))
        Ans = reduction(L)
        if Ans!=None:
            show = dict({})
            keys = [i for i in variable]
            nonlocal a
            a=len(keys)
            for i in Ans:
                for j in range(len(i)):
                    if i[j]==1:
                        show[keys[j]]=float(-i[-1])
                        break
            return show
        else:
            return None
        

    solution = sol(sq)        
    
    if len(variable)-1>len(sq):return None

    return solution

import copy
import re


class Fraction:

    def __init__(self, numerator, denominator):
        self.numerator = numerator
        self.denominator = denominator
        if not (isinstance(self.numerator, int) and isinstance(self.denominator, int)):
            raise ValueError('Expecting integer values.')
        if not self.denominator:
            raise ValueError('Division by 0.')
        self.reduce()

    def reduce(self):
        gcd = self._gcd(self.numerator, self.denominator)
        self.numerator = self.numerator // gcd
        self.denominator = self.denominator // gcd

    def to_float(self):
        return self.numerator / self.denominator

    @classmethod
    def to_fraction(cls, obj):
        if isinstance(obj, int):
            return Fraction(obj, 1)
        elif isinstance(obj, float):
            i, j = str(obj).split('.')
            return Fraction(int(j) + int(i) * 10 ** len(j), 10 ** len(j))
        else:
            raise ValueError('Only int or float.')

    @staticmethod
    def _gcd(x, y):
        while y:
            x, y = y, x % y
        return x

    def _lcm(self, x, y):
        return abs(x * y) // self._gcd(x, y)

    def __add__(self, other):
        lcm = self._lcm(self.denominator, other.denominator)
        numerator = (self.numerator * (lcm // self.denominator)) + (other.numerator * (lcm // other.denominator))
        return Fraction(numerator, lcm)

    def __sub__(self, other):
        lcm = self._lcm(self.denominator, other.denominator)
        numerator = (self.numerator * (lcm // self.denominator)) - (other.numerator * (lcm // other.denominator))
        return Fraction(numerator, lcm)

    def __mul__(self, other):
        return Fraction(self.numerator * other.numerator, self.denominator * other.denominator)

    def __truediv__(self, other):
        return Fraction(self.numerator * other.denominator, self.denominator * other.numerator)

    def __bool__(self):
        return self.numerator != 0

    def __str__(self):
        return str(self.numerator) + '/' + str(self.denominator)


class LinearEquation:

    PATTERN = '[+-]?([0-9]+[a-zA-Z]*|[a-zA-Z]+)([+-]([0-9]+[a-zA-Z]*|[a-zA-Z]+))*'

    def __init__(self, eq):
        self.eq = eq.replace(' ', '')
        if not self._validation():
            raise ValueError('Expecting correct Equation.')

    def _validation(self):
        if re.match('^' + LinearEquation.PATTERN + '=' + LinearEquation.PATTERN + '$', self.eq):
            return True
        else:
            return False

    @staticmethod
    def _tokenize(string):
        tokens = re.findall('[+-]?(?:[0-9]+[a-zA-Z]*|[a-zA-Z]+)', string)
        values = dict()
        for token in tokens:
            value, var = re.findall('^([+-]?[0-9]*)([a-zA-Z]*)$', token)[0]
            if not value or value == '+':
                value = Fraction(1, 1)
            elif value == '-':
                value = Fraction(-1, 1)
            else:
                value = Fraction.to_fraction(float(value))
            if var in list(values.keys()):
                values[var] += value
            elif value:
                values[var] = value
        return values

    def parse(self):
        left_side, right_side = self.eq.split('=')
        values = self._tokenize(left_side)
        for var, value in list(self._tokenize(right_side).items()):
            value *= Fraction(-1, 1)
            if var in list(values.keys()):
                values[var] += value
            else:
                values[var] = value
        if '' not in list(values.keys()):
            values[''] = Fraction(0, 1)
        return values


class LinearEquationSystem:

    def __init__(self, m, x, b):
        self.m = m
        self.x = x
        self.b = b
        if not self._validate():
            raise ValueError('Wrong arguments.')

    def _validate(self):
        if not isinstance(self.m, list) and not isinstance(self.x, list) and not isinstance(self.b, list):
            return False
        if not (len(self.m) == len(self.b)):
            return False
        for eq in self.m:
            if not isinstance(eq, list) and len(eq) == len(self.x):
                return False
        return True

    @staticmethod
    def _rank(m):
        rank = min(len(m[0]), len(m))
        ind = min(len(m[0]), len(m))
        for i in range(ind):
            if m[i][i]:
                for j in range(i + 1, len(m)):
                    multiplier = m[j][i] / m[i][i]
                    for k in range(i, len(m[0])):
                        m[j][k] -= (multiplier * m[i][k])
            else:
                reduce = True
                for j in range(i + 1, len(m)):
                    if m[j][i]:
                        reduce = False
                        m[i], m[j] = m[j], m[i]
                        break
                if reduce:
                    rank -= 1
                else:
                    for j in range(i + 1, len(m)):
                        multiplier = m[j][i] / m[i][i]
                        for k in range(i, len(m[0])):
                            m[j][k] -= (multiplier * m[i][k])
        return rank, m

    def solve(self):
        m = copy.deepcopy(self.m)
        m_rank, _ = self._rank(m)
        m_b = copy.deepcopy(self.m)
        for i, row in enumerate(m_b):
            row.append(self.b[i])
        m_b_rank, m_b = self._rank(m_b)

        if m_rank == m_b_rank and m_rank == len(self.x):
            solutions = dict()
            b = list()

            for row in m_b:
                b.append(Fraction(-1, 1) * row[-1])
                del row[-1]
            while len(m_b) > len(m_b[0]):
                del m_b[-1]

            for i in range(len(m_b))[::-1]:
                multiplier = None
                for j in range(len(m_b[i])):
                    if j == i:
                        multiplier = Fraction(1, 1) / m_b[i][i]
                    elif m_b[i][j]:
                        b[i] -= (m_b[i][j] * solutions[self.x[j]])
                solutions[self.x[i]] = b[i] * multiplier

            for var in solutions:
                solutions[var] = solutions[var].to_float()

            return solutions

        else:
            return None

def solve(*eqs):
    print(eqs)
    values_list = list()
    variables = set()
    coefficient_matrix = list()
    b = list()
    for i, eq in enumerate(eqs):
        values_list.append(LinearEquation(eq).parse())
        for var in list(values_list[i].keys()):
            variables.add(var)
        coefficient_matrix.append(list())
    variables = sorted(list(variables))
    for i in range(len(eqs)):
        for var in variables:
            if not var:
                b.append(values_list[i][var])
            elif var in list(values_list[i].keys()):
                coefficient_matrix[i].append(values_list[i][var])
            else:
                coefficient_matrix[i].append(Fraction(0, 1))
    system = LinearEquationSystem(m=coefficient_matrix, x=variables[1::], b=b)
    return system.solve()


import re
from functools import reduce

# Parsing ###################################################################

# Returns a dictionary {k:v} where k is the variable (or None for constant),
# and v is the value. This dictionary is in effect a singleton term set.
def parse_term(term, scale):
    parts = re.findall('[+-]?\d+|[+-]|[^\d]+', term)
    
    if parts[0] in '+-': parts[0] += "1"
    
    if len(parts) == 2:
        return { parts[1] : int(parts[0]) * scale }
    elif len(parts) == 1:
        try:
            return { None : int(parts[0]) * scale }
        except ValueError:
            return { parts[0] : scale }
    else:
        raise Exception('assertion failed')

def combine_term_dicts(a, b):
    common_keys = set(a.keys()).intersection(b.keys())
    
    common_terms = {k:a[k]+b[k] for k in common_keys}

    unique_terms = lambda c: {k:v for k,v in c.items() if k not in common_keys}
    
    return {**common_terms, **unique_terms(a), **unique_terms(b)}

# Parses the expression in a single side of an equation
# Parameter 'scale' is 1 for left-hand side, and -1 for right-hand side.
def parse_side(side, scale):
    no_ws = re.sub(' ', '', side)

    # The following regex will always produce an empty match at the
    # end of string, which we remove at the end.
    term_str = re.findall("[+-]?\d*[^\d+-]*", no_ws)[0:-1]

    term_lst = [parse_term(t, scale) for t in term_str]
    
    return reduce(combine_term_dicts, term_lst)

# Parses a single equation
def parse_equation(eq):
    sides = eq.split('=')
    
    lhs = parse_side(sides[0],  1)
    rhs = parse_side(sides[1], -1)
    
    return combine_term_dicts(lhs, rhs)

# Linear algebra ############################################################

def argmax(lst):
    return [i for i in range(len(lst)) if lst[i] == max(lst)][0]

aug = [[1, -4, 0], [2, -8, 0], [1, 1, 5]]

def gaussian_elimination_inplace(aug):
    n_equations = len(aug)
    n_variables = len(aug[0]) - 1
    
    for i in range(min(n_variables, n_equations - 1)):
        # find pivot row
        p = i + argmax([abs(aug[j][i]) for j in range(i, n_equations)])
        
        if abs(aug[p][i]) < 1e-12:
            raise ValueError('system is singular')

        aug[i], aug[p] = aug[p], aug[i]

        for j in range(i + 1, n_equations):
            beta = aug[j][i] / aug[i][i]
            
            for k in range(n_variables + 1):
                aug[j][k] -= aug[i][k] * beta

def backsolve(aug):
    n_equations = len(aug)
    n_variables = len(aug[0]) - 1
    
    sol = [aug[i][n_variables] for i in range(n_variables)]
    
    for i in reversed(range(n_variables)):
        for j in range(i + 1, n_variables):
            sol[i] -= aug[i][j] * sol[j]
            
        if abs(aug[i][i]) < 1e-12:
            raise ValueError('system is singular')
            
        sol[i] /= aug[i][i]
        
    return sol

# Driver ####################################################################

def solve(*equations):
    lst = [parse_equation(eq) for eq in equations]
    
    variables = map(set, map(dict.keys, lst))
    
    variables = [v for v in reduce(set.union, variables) if v]
    
    n_variables = len(variables)
    n_equations = len(equations)
    
    if n_equations < n_variables:
        return None
        
    aug = [[0] * (n_variables + 1) for i in range(n_equations)]

    for i in range(n_equations):
        for j in range(n_variables):
            aug[i][j] = lst[i].get(variables[j], 0)
            
        aug[i][n_variables] = -lst[i].get(None, 0)
        
    try:
        gaussian_elimination_inplace(aug)
        
        sol = backsolve(aug)
    except ValueError:
        return None
    
    return {k:v for k,v in zip(variables, sol)}

import re
from math import gcd

def solve(*eqs):
    # Print equations for reference
    for e in eqs:
        print(e)
    # Parsed equations into values
    parsed_eqs = []
    for e in eqs:
        e = ('' if e[0] == '-' else '+') + e
        parts = re.match(r'\A(([+-][0-9]*[a-z]*)+)=(([+-]?[0-9]*[a-z]*)+)\Z', e).groups()
        parts = parts[0], ('' if parts[2][0] == '-' else '+') + parts[2]
        parts = [re.findall(r'[+-][0-9]*[a-z]*', p) for p in parts]
        parts = [[[''.join(re.findall(r'\A([+-][0-9]*)', i)), ''.join(re.findall(r'[a-z]', i))] for i in p] for p in parts]
        parsed = {}
        for i, p in enumerate(parts):
            for v, k in p:
                if k not in parsed:
                    parsed[k] = 0
                parsed[k] += (int(v) if v not in '-+' else int(v + '1')) * [1, -1][i]
        parsed_eqs.append(parsed)
    # Parsed values into matrix
    keys = set()
    for parsed_eq in parsed_eqs:
        for key in parsed_eq:
            keys.add(key)
    for parsed_eq in parsed_eqs:
        for key in keys:
            if key not in parsed_eq:
                parsed_eq[key] = 0
    ordered_keys = sorted(keys - {''}) + ['']
    print(('\n' + str(ordered_keys)))
    matrix = []
    for parsed_eq in parsed_eqs:
        matrix.append([[parsed_eq[k], 1] for k in ordered_keys])
    for line in matrix:
        print(line)
    # Reduce the matrix with standard operations
    def swap(i0, i1):
        # matrix[i1], matrix[i0] = matrix[i0], matrix[i1]
        tmp = matrix[i0]
        matrix[i0] = matrix[i1]
        matrix[i1] = tmp
    def mul(i, n):
        for l in matrix[i]:
            l[0] *= n
    def div(i, n):
        for l in matrix[i]:
            l[1] *= n
    def add(io, it):
        for c in range(len(matrix[0])):
            matrix[it][c][0] = matrix[it][c][0] * matrix[io][c][1] + matrix[io][c][0] * matrix[it][c][1]
            matrix[it][c][1] *= matrix[io][c][1]
    def sub(io, it):
        for c in range(len(matrix[0])):
            matrix[it][c][0] = matrix[it][c][0] * matrix[io][c][1] - matrix[io][c][0] * matrix[it][c][1]
            matrix[it][c][1] *= matrix[io][c][1]
    def reduce(i):
        for l in matrix[i]:
            divisor = gcd(l[0], l[1])
            if l[1] < 0:
                divisor *= -1
            if divisor != 0:
                l[0], l[1] = l[0] // divisor, l[1] // divisor
    # Convert to row echelon form
    def ref(r0, c0):
        print()
        if r0 >= len(matrix) or c0 >= len(matrix[0])-1:
            return
        if matrix[r0][c0][0] == 0:
            r = r0
            while r < len(matrix) and matrix[r][c0][0] == 0:
                r += 1
            if r == len(matrix):
                return ref(r0, c0+1)
            swap(r0, r)
        for i in range(r0, len(matrix)):
            if matrix[i][c0][0] != 0:
                div(i, matrix[i][c0][0])
                reduce(i)
        for i in range(r0, len(matrix)):
            mul(i, matrix[i][c0][1])
            reduce(i)
        for i in range(r0+1, len(matrix)):
            if matrix[i][c0][0] != 0:
                sub(r0, i)
                reduce(i)
        return ref(r0+1, c0+1)
    ref(0, 0)
    # Remove lines that lack meaning
    matrix = [line for line in matrix 
              if line != [[0, 1] for x in range(len(line))]]
    print('REF:')
    for line in matrix:
        print(line)
    # Generate reduced row echelon form by retracing up the matrix
    def rref(r0, c0):
        while r0 > 0 and c0 > 0 and matrix[r0][c0] != [1, 1]:
            if r0 > 0 and matrix[r0][c0][0] == 0:
                r0 -= 1
            elif c0 > 0 and matrix[r0][c0] != [1, 1]:
                c0 -= 1
        if r0 <= 0 or c0 <= 0:
            return
        for i in range(0, r0):
            matrix[-1] = [[0, 1] for x in range(len(matrix[0]))]
            add(r0, -1)
            div(-1, matrix[i][c0][1])
            mul(-1, matrix[i][c0][0])
            sub(-1, i)
            reduce(i)
        return rref(r0-1, c0-1)
    matrix.append([[0, 1] for x in range(len(matrix[0]))])
    rref(len(matrix)-2, len(matrix[0])-2)
    matrix.pop()
    print()
    for line in matrix:
        print(line)
    print()
    for line in matrix:
        print(line)
    if len(matrix) == 0 or len(matrix) != len(matrix[0]) - 1:
        print(('Bad dimensions: {}, {}'.format(len(matrix), len(matrix[0]))))
        return None
    result = {}
    for i in range(len(matrix)):
        result[ordered_keys[i]] = -matrix[i][-1][0]/matrix[i][-1][1]
    return result


import re
from fractions import Fraction
def solve(*equations): 
        equations2 = []
        for x in equations:
           equations2.append(x)
        equations = equations2
        def parsing(equations):
            vectconstant = []
            matrixcoefficient = []
            listvariables = []
            for equation in equations :
                eqvariables = re.findall('[A-Za-z]+' , equation )
                listvariables = listvariables + eqvariables
            listvariables = list(set(listvariables))  
            for equation in equations :
                listcoefficient = []
                equation = re.sub('\s' , '' , equation)
                eqdivided = equation.split('=')
                firstp , secondp = eqdivided[0] , eqdivided[1]
                constantterm1 = re.findall('[\-\+]*\d+\.?\d*(?=[+-])|[\-\+]*\d+\.?\d*$', firstp)
                constantterm2 = re.findall('[\-\+]*\d+\.?\d*(?=[+-])|[\-\+]*\d+\.?\d*$', secondp)
                for x in range(len(constantterm1)):
                    constantterm1[x] = '-' + constantterm1[x]
                    constantterm1[x] = re.sub('\+\+|\-\-', '+', re.sub('\+\-|\-\+', '-',constantterm1[x]))
                constantterm = Fraction((sum(list(map(float, constantterm1 + constantterm2)))))
                vectconstant.append(constantterm)
                for x in listvariables :
                    values1 = re.findall('([\-\+]*[\d.]*)'+re.escape(x)+'(?=[+-]|$)' , firstp)
                    values2 = re.findall('([\-\+]*[\d.]*)'+re.escape(x)+'(?=[+-]|$)', secondp)
                    for x in range(len(values2)): 
                        values2[x] = '-' + values2[x]
                        values2[x] = re.sub('\+\+|\-\-', '+', re.sub('\+\-|\-\+', '-',values2[x]))
                    values = values1 + values2
                    for x in range(len(values)):
                        if values[x] == '' or values[x] == '+' :
                            values[x] = '1'
                        elif values[x] == '-' :
                            values[x] = '-1'
                        values[x] = float(values[x])
                    coefficient = Fraction((sum(values)))
                    listcoefficient.append(coefficient)
                matrixcoefficient.append(listcoefficient)
            return matrixcoefficient , vectconstant , listvariables
        def eliminateuselessrows(matrixcoefficient,vectconstant):
            newmatrix , newvector = [] , []
            for t,x in enumerate(matrixcoefficient) :
                for y in x :
                    if y != Fraction(0,1) :
                        newmatrix.append(x) , newvector.append(vectconstant[t])
                        break
            return newmatrix , newvector
        def GaussReduction(matrixcoefficient,vectconstant) :
            c = 0
            while c < min(len(matrixcoefficient[0]),len(matrixcoefficient)):
                if matrixcoefficient[c][c] == Fraction(0,1) :
                    for t,x in enumerate(matrixcoefficient):
                        if matrixcoefficient[t][c] != Fraction(0,1) :
                            matrixcoefficient[c] , matrixcoefficient[t] = matrixcoefficient[t] , matrixcoefficient[c]
                            vectconstant[c] , vectconstant[t] = vectconstant[t] , vectconstant[c]                
                for t,x in enumerate(matrixcoefficient):
                    factor = x[c]
                    if t > c and  matrixcoefficient[c][c] != Fraction(0,1) :
                        vectconstant[t] = vectconstant[t]-vectconstant[c]*factor/matrixcoefficient[c][c]
                        for s,y in enumerate(x):
                            matrixcoefficient[t][s] = y-matrixcoefficient[c][s]*factor/matrixcoefficient[c][c]
                matrixcoefficient,vectconstant = eliminateuselessrows(matrixcoefficient,vectconstant)            
                c=c+1
            return matrixcoefficient , vectconstant
        matrixcoefficient , vectconstant , listvariables = parsing(equations)        
        matrixcoefficient , vectconstant = GaussReduction(matrixcoefficient , vectconstant)                
        rk1 , rk2 = 0 , 0
        for t,x in enumerate(matrixcoefficient) :
            for y in x :
                if y != Fraction(0,1) :
                    rk1 = rk1 + 1
                    rk2 = rk2 + 1
                    break
            else :
                if vectconstant[t] != Fraction(0,1) :
                    rk2 = rk2 + 1
        if rk1 < rk2 :
            return None
        if rk1 == rk2 < len(listvariables) :
            return None
        matrixcoefficient,vectconstant = eliminateuselessrows(matrixcoefficient,vectconstant)
        for x in matrixcoefficient:
             x.reverse()
        matrixcoefficient.reverse() , vectconstant.reverse() , listvariables.reverse()
        matrixcoefficient , vectconstant = GaussReduction(matrixcoefficient , vectconstant)
        for t,x in enumerate(matrixcoefficient):
            vectconstant[t] = vectconstant[t]*(1/x[t])
        dictsolutions ={}
        for t,x in enumerate(vectconstant) :
            dictsolutions.update({listvariables[t]:float(vectconstant[t])})
        return dictsolutions

import re
from fractions import Fraction as fraction

def solve(*equations):
    A, x, b = parse_equations(equations)
    answer = gaussian_elimination(A, x, b)
    return answer

def parse_equations(equations):
    create_equation = Equation.from_string
    equations = [create_equation(eq) for eq in equations]
    x = []
    for eq in equations:
        for var in eq.variables.keys():
            x.append(var)
    seen = set()
    x = [var for var in x if not (var in seen or seen.add(var))]
    A = []
    b = []
    for i, eq in enumerate(equations):
        A.append([])
        b.append(eq.constant)
        for var in x:
            constant = eq.variables.get(var)
            A[i].append(constant if constant else 0)
    return A, x, b

def gaussian_elimination(A, x, b):
    n = len(A)
    if n < len(x):
        return None #There will be free variables
    for a, b in zip(A, b):
        a.append(b)
    for i in range(len(x)):
        max_el = abs(A[i][i])
        max_row = i
        for j in range(i+1, n):
            if abs(A[j][i]) > max_el:
                max_el = abs(A[j][i])
                max_row = j
        if max_row != i:
            A[i], A[max_row] = A[max_row], A[i]
        a1 = A[i][i]
        if round(a1, 9) == 0:
            return None
        for j in range(i + 1, n):
            a2 = A[j][i]
            if a2 == 0:
                continue
            c = -a2/a1
            A[j][i] = 0
            for k in range(i + 1, len(x) + 1):
                A[j][k] += c*A[i][k]
    return back_substitution(A, x)

def back_substitution(U, x):
    answer = {}
    col = len(x) - 1
    for row in range(len(U) - 1, -1, -1):
        if U[row][col] == 0:
            if round(U[row][len(x)], 9) != 0: #b not in C(A)
                return None
            continue
        answer[x[col]] = U[row][len(x)]/U[row][col]
        for i in range(row -1, -1, -1):
            U[i][len(x)] -= U[i][col]*answer[x[col]]
        col -= 1
    return answer

class Equation:
    def __init__(self, variables, constant):
        self.variables = variables
        self.constant = constant

    @classmethod
    def from_string(cls, eq):
        obj_list = [] #ax+by+cz-5=0 => [a,b,c]
        obj_regex = re.compile(r"-?\d*[a-z]+|-?\d+")

        substring = eq[0: eq.find("=")]
        found_obj = obj_regex.findall(substring)
        if len(found_obj):
            for obj in found_obj:
                obj_list.append(obj)
        
        substring = eq[eq.find("=") + 1:]
        found_obj = obj_regex.findall(substring)
        if len(found_obj):
            for obj in found_obj:
                obj = obj[1:] if "-" in obj else "-" + obj #Right hand objects become negative
                obj_list.append(obj)
        
        s_regex = re.compile(r"[a-z]+")
        constant = -sum(int(obj) for obj in obj_list if not s_regex.search(obj))
        variable_list = [obj for obj in obj_list if s_regex.search(obj)]

        variable_dict = {}
        n_regex = re.compile(r"-?\d*")
        for obj in variable_list:
            s = s_regex.search(obj).group()
            n = n_regex.search(obj).group()
            if n == "-":
                n = -1
            else:
                if n == "":
                    n = 1
                else:
                    n = int(n)
            if variable_dict.get(s):
                variable_dict[s] += n
            else:
                variable_dict[s] = n
        return cls(variable_dict, constant)
        
    def __repr__(self):
        return "Variables: {}\nConstant: {}".format(self.variables, self.constant)

import re
from collections import defaultdict

def parse_terms(term, sn):
    d = defaultdict(int)
    for m in re.finditer('([+-]?)\s*(\d*)\s*([a-z]*)', term):
        s, n, v = m.groups()
        if n or v:
            n = sn * (int(n or 1) * (1, -1)[s == '-'])
            d[v or '_'] += n    
    return d

def parse_equations(equations):
    res = []
    for eq in equations:
        a, b = eq.split('=')
        d = parse_terms(a, 1)
        for k, v in parse_terms(b, -1).items():
            d[k] += v
        res.append(d)
    return res

def norm_mat(m, var_pos):
    val = m[var_pos]
    if abs(val) > 1e-8:
        for a in range(len(m)):
            m[a] /= val

def sub_mat(m1, m2, var_pos):
    if non_zero(m1[var_pos]):
        for c, v in enumerate(m2):
            m1[c] -= v

def non_zero(x):
    return abs(x) > 1e-8

def solve(*equations):
    print(equations)
    eqs = parse_equations(equations)
    var = sorted({k for d in eqs for k in d}, reverse = True)
    mat = [[d.get(k, 0) for k in var] for d in eqs]
    num_of_vars = len(var) - 1
    seen = set()
    p = 0
    while p < len(mat):
        var_pos = next(c for c in range(num_of_vars) if non_zero(mat[p][c]) and c not in seen)
        seen.add(var_pos)
        norm_mat(mat[p], var_pos)
        for n in range(p + 1, len(mat)):
            norm_mat(mat[n], var_pos)
            sub_mat(mat[n], mat[p], var_pos)
        mat = [m for m in mat if any(map(non_zero, m))]
        p += 1
    seen.clear()

    d = {}
    while mat:
        el = mat.pop()
        p = next(a for a in range(num_of_vars) if el[a] == 1.0 and a not in d)
        for k, v in d.items():
            el[-1] += el[k] * v
        d[p] = -el[-1]
    
    if len(d) == num_of_vars:
        return {var[k] : v for k, v in d.items()}

def decode_eq_side(eq_side):
    result = {}
    sign, factor, var_name = 1, "", ""

    def add_variable():
        nonlocal factor, var_name, result
        if var_name:
            result[var_name] = result.get(var_name, 0) + sign * int(factor) if factor else result.get(var_name, 0) + sign
        elif factor:
            result[""] = result.get(var_name, 0) + sign * int(factor) if factor else result.get(var_name, 0) + sign
        factor, var_name = "", ""

    for i, s in enumerate(eq_side.replace(" ", "")):
        if s == "+":
            add_variable()
            sign = 1
        elif s == "-":
            add_variable()
            sign = -1
        elif s.isdigit():
            factor += s
        else:
            var_name += s
    else:
        add_variable()
    return result


def decode_equation(equation):
    variables, variables2 = [decode_eq_side(side) for side in equation.split("=")]
    for var, factor in variables2.items():
        variables[var] = variables.get(var, 0) - factor
    variables[""] = -1*variables.get("", 0)
    return variables


def solve(*equations):
    # get equation variables and matrix
    equations_variables = [decode_equation(equation) for equation in equations]
    variable_names = {var_name for eq_vars in equations_variables for var_name in eq_vars}
    variable_names.discard("")
    variable_names = list(variable_names)
    if len(variable_names) > len(equations_variables):
        return None
    equations_matrix = [[variables.get(var_name, 0) for var_name in variable_names] + [variables.get("", 0)] for variables in equations_variables]
    del equations_variables
    # gauss elimination
    gauss_matrix = []
    for i in range(len(variable_names)):
        chosen_row = max(equations_matrix, key=lambda row: abs(row[i]))
        # check if solution is indeterminate
        if abs(chosen_row[i]) < 1e-10:
            return None
        equations_matrix.remove(chosen_row)
        gauss_matrix.append([0]*i + [param/chosen_row[i] for param in chosen_row[i:]])
        for row_i, row in enumerate(equations_matrix):
            equations_matrix[row_i] = [0]*(i+1) + [param - row[i]*gauss_matrix[-1][i+j+1] for j, param in enumerate(row[i+1:])]
    # check if there are no solution
    if any(abs(row[-1]) > 1e-10 for row in equations_matrix):
        return None
    solution = []
    for equation in reversed(gauss_matrix):
        solution.append(equation[-1] - sum([equation[-(2+i)]*param for i, param in enumerate(solution)]))
    return dict(zip(variable_names, reversed(solution)))

import re
def solve(*eqs):
    #put all equations in list of dictionaries
    sysofeq = []
    for x in eqs:
        #check if it is an equation
        if '=' not in x:
            return None
        else:
            sysofeq.append(elabString(x))
    
    #create matrix and vector
    #get all the variables
    varis = {}
    for eq in eqs:
        va = re.findall("[a-z]+",eq)
        for char in va:
                varis.update({char:0})
    listofvars = list(varis.keys())
    mat = []
    vec = []
    for eq in sysofeq:
        row = []
        for v in range(0,len(listofvars)):
            if eq.get(listofvars[v]) == None:
                row.append(0)
            else:    
                row.append(eq.get(listofvars[v]))
        mat.append(row)
        vec.append(eq.get("sum"))
    #check for number of equations
    if len(listofvars) > len(mat):
        return None
    withPivot(mat, vec)
    #check if number of equations is greater than num of variables
    if len(mat) > len(mat[0]):
            for x in range(len(mat[0]),len(vec)):
                if abs(vec[x]) > 1e-6:
                    return None
    #check if pivot = 0
    for pivot in range(0,len(mat[0])):
        if abs(mat[pivot][pivot])<1e-8:
            return None
    result = {}
    for x in range(0,len(listofvars)):
        
        result.update({listofvars[x]:vec[x]})
    return result
def elabString(equation):
    equation = re.sub("\+"," + ",equation)
    equation = re.sub("-"," - ",equation)
    equation = re.sub("="," = ",equation)
    varis = {}
    allvars = re.findall("[a-z]+",equation)
    for char in allvars:
            varis.update({char:0})
    varis.update({"sum":0})
    leftpart = equation.split("=")[0]
    rightpart = equation.split("=")[1][1:]
    #elaborate leftparts
    leftparts = leftpart.split(" ")
    for x in range(0,len(leftparts)):
        if re.search("[a-z]+$",leftparts[x]):
            num = re.search("[0-9]*",leftparts[x]).group()
            if len(num)== 0:
                num = '1'
            if x > 0 and leftparts[x-1] == '-':
                num = "-" + num
            curvar = (re.search("[a-z]+$",leftparts[x])).group()
            curval = varis.get(curvar)
            varis.update({re.search("[a-z]+$",leftparts[x]).group():int(num)+curval})
        if re.search("[0-9]$",leftparts[x]):
            origval = varis.get("sum")
            if x > 0 and leftparts[x-1] == '-':
                varis.update({"sum":origval + int(leftparts[x])})
            else:    
                varis.update({"sum":origval - int(leftparts[x])})
    #elaborate rightparts
    rightparts = rightpart.split(" ")
    for x in range(0,len(rightparts)):
        if re.search("[a-z]+$",rightparts[x]):
            num = re.search("[0-9]*",rightparts[x]).group()
            if len(num)== 0:
                num = '1'
            if x > 0 and rightparts[x-1] == '+':
                num = "-" + num
            if x == 0:
                num = "-" + num
            curvar = (re.search("[a-z]+$",rightparts[x])).group()
            curval = varis.get(curvar)
            varis.update({re.search("[a-z]+$",rightparts[x]).group():int(num)+curval})
        if re.search("[0-9]$",rightparts[x]):
            origval = varis.get("sum")
            if x == 0:
                varis.update({"sum":origval + int(rightparts[x])})
            elif rightparts[x-1] == '-':    
                varis.update({"sum":origval - int(rightparts[x])})
            else:
                varis.update({"sum":origval + int(rightparts[x])})
    
    return varis
def swapRows(matrix,vector,x,y):
    rowx = matrix[x]
    matrix[x] = matrix[y]
    matrix[y] = rowx
    varx = vector[x]
    vector[x] = vector[y]
    vector[y]= varx
def addRows(matrix,x,y,mul):
    for p in range(0,len(matrix[0])):
        matrix[y][p]=matrix[y][p]-mul*matrix[x][p]
def addScalar(vector,x,y,mul):
    vector[y] = vector[y] - mul * vector[x]
def withPivot(matrix, vector):
    for r in range(0,len(matrix[0])):
        #find row number with max diagonal element
        p = [r,matrix[r][r]]
        for v in range(r,len(matrix)):
            if abs(matrix[v][r])>abs(p[1]):
                p = [v,matrix[v][r]]
        swapRows(matrix, vector, r, p[0])
        for q in range(r+1,len(matrix)):
            if matrix[r][r] == 0:
                return None
            mult = matrix[q][r]/matrix[r][r]
            addRows(matrix,r,q,mult)
            addScalar(vector,r,q,mult)
    for r in range(len(matrix[0])-1,0,-1):
        for q in range(0,r):
            if matrix[r][r] == 0:
                return None
            mult = matrix[q][r]/matrix[r][r]
            addRows(matrix,r,q,mult)
            addScalar(vector,r,q,mult)
    for s in range(0,len(matrix[0])):
        vector[s]= vector[s]/matrix[s][s]
    return (matrix,vector)