#!/usr/bin/env python3
import sys
import collections
import time
import re
import decimal


def get_new_form(polynomial, variables):
    dic = {}
    splitted = split_polynomial(polynomial)
    for mono in splitted:
        coefficients = []
        coefficients.append(1.0)
        powers = []
        power_zero = []
        for v in variables:
            powers.append(0)
            power_zero.append(0)
        i = 0
        while i < len(mono):
            if mono[i] == '-':
                coefficients.append(-1.0)
            elif mono[i] in variables:
                variable = mono[i]
                if i < len(mono)-1 and mono[i+1] == '^':
                    i += 2
                    power = float(mono[i])
                else:
                    power = 1.0
                powers[variables.index(variable)] += power
            elif is_number(mono[i]):
                coefficients.append(float(mono[i]))
            i += 1
        final_coef = 1.0
        for e in coefficients:
            e = float(e)
            final_coef *= e
        a = tuple(powers)
        if len(coefficients) == 1 and power_zero == powers:
            dic[a] = 0
        else:
            if a in dic:
                dic[a] += final_coef
            else:
                dic[a] = final_coef
        final_poly = Polynomial(dic)
    return final_poly


def calculate_polynomial(polynomial, variables):
    standart_operators = ["+", "-", "*", "/", "^"]
    polynomial_good_form = ['(']
    open_bracket = False
    close_bracket = False
    i = 0
    polynomial.insert(0, '(')
    polynomial.append(')')
#    #if polynomial[0] == '(':
    #    i += 1
    i += 1
    while i < len(polynomial):
        if polynomial[i] == '(' or polynomial[i] == ')':
            list = []
            next = i
            open_bracket = False
            close_bracket = False
            if polynomial[i] == '(':
                open_bracket = True
                if polynomial[i-1] in standart_operators:
                    operand = polynomial[i-1]
                else:
#                    #print(i)
                    #print('(')
                    polynomial_good_form.append('(')
                    i += 1
                    continue
                i -= 1
            elif polynomial[i] == ')':
                if polynomial[i-1] == ')':
#                    #print(i)
                    #print(')k')
                    polynomial_good_form.append(')')
                    i += 1
                    continue
                elif (i < len(polynomial)-2):
                        if polynomial[i+2] != '(' and polynomial[i+1] != '(' and polynomial[i+1] != ')':
#                            #print(i)
                            close_bracket = True
                            #print(close_bracket)
                            operand = polynomial[i+1]
                            if operand == '-':
                                operand = '+'
            i -= 1
            while polynomial[i] != '(' and polynomial[i] != ')' and i >= 0:
                list.append(polynomial[i])
                i -= 1
            list.reverse()
            #print(list)
            if len(list) == 0:
                pass
#                #polynomial_good_form.append(operand)
            else:
                polynomial_good_form.append(get_new_form(list, variables))
##dict pered skobkoi
            if open_bracket:
#                #print(operand)
                #print('operando')
                polynomial_good_form.append(operand)
                open_bracket = False
#                #print(next)
                #print(polynomial[next])
                polynomial_good_form.append(polynomial[next])
            elif close_bracket:
#                #print(next)
                #print(polynomial[next])
                polynomial_good_form.append(polynomial[next])
#                #print('operandc')
                #print(operand)
                polynomial_good_form.append(operand)
                close_bracket = False
            else:
#                #print(next)
                #print(polynomial[next])
                polynomial_good_form.append(polynomial[next])
            i = next + 1
        else:
            i += 1
    return polynomial_good_form


def convert_to_postfix_notation(input):
    outputSeparated = []
    stack = []
    operators = ['(', ')', '+', '-', '*', '/', '^']
    for c in input:
        if c in operators:
            if len(stack) > 0 and c != '(':
                if c == ')':
                    s = stack.pop()
                    while s != '(':
                        outputSeparated.append(s)
                        s = stack.pop()
                elif get_priority(c) > get_priority(stack[len(stack)-1]):
                    stack.append(c)
                else:
                    while len(stack) > 0 and get_priority(c) <= get_priority(stack[len(stack)-1]):
                        outputSeparated.append(stack.pop())
                    stack.append(c)
            else:
                stack.append(c)
        else:
            outputSeparated.append(c)
    if (len(stack) > 0):
        for i in range(len(stack)):
            outputSeparated.append(stack[len(stack)-1-i])
    return outputSeparated


def get_priority(s):
    if s in ['(', ')']:
        return 0
    if s in ['+', '-']:
        return 1
    if s in ['*', '/']:
        return 2
    if s in ['^']:
        return 3
    else:
        return 4


def split_polynomial(polynomial):
    monomials = []
    monomial = []
    sign_in_the_begin = False
    if polynomial[0] == '-':
        monomial.append('-')
        sign_in_the_begin = True
        k = 1
    elif polynomial[0] == '+':
        monomial.append('+')
        sign_in_the_begin = True
        k = 1
    else:
        monomial.append('+')
        k = 0
    for i in range(k, len(polynomial)):
        if polynomial[i] != '+' and polynomial[i] != '-':
            monomial.append(polynomial[i])
        else:
            monomials.append(monomial)
            monomial = []
            monomial.append(polynomial[i])
    monomials.append(monomial)
    return monomials


class Polynomial:
    dict = {}

    def __init__(self, poly):
        self.dict = poly

    def __str__(self):
        return str(self.dict)

    def __add__(self, poly2):
        for key in poly2.dict:
            if key in self.dict:
                self.dict[key] += poly2.dict[key]
            else:
                self.dict[key] = poly2.dict[key]
        return self.simplify()

    def __mul__(self, poly2):
        result_poly = {}
        for e1 in self.dict:
            for e2 in poly2.dict:
                e3 = list()
                for i in range(len(e1)):
                    e3.append(e1[i] + e2[i])
                e3 = tuple(e3)
                if e3 in result_poly:
                    result_poly[e3] += self.dict[e1] * poly2.dict[e2]
                else:
                    result_poly[e3] = self.dict[e1] * poly2.dict[e2]
        self.dict = result_poly
        result_poly = self.simplify()
        return self

    def simplify(self):
        list_for_delete = []
        for e in self.dict:
            if self.dict[e] == 0:
                list_for_delete.append(e)
        for e in list_for_delete:
            self.dict.pop(e)
        return self


def is_number(s):
    try:
        float(s)
        return True
    except ValueError:
        return False


def separate(input):
    tokens = []
    pos = 0
    while pos < len(input):
        standart_operators = ["(", ")", "+", "-", "*", "/", "^"]
        s = input[pos]
        if not input[pos] in standart_operators:
            if input[pos].isdigit():
                for i in range(pos+1, len(input)):
                    if not input[i].isdigit(()) and input[i] != ',' and input[i] != '.':
                        break
                    s += input[i]
            elif input[pos].isalpha():
                for i in range(pos+1, len(input)):
                    if not input[i].isalpha() and not input[i].isdigit():
                        s += input[i]
                tokens.append(s)
                pos += len(s)
    return tokens


def delete_spaces(input):
    list_without_spaces = []
    for i in range(len(input)):
        if input[i] != ' ':
            list_without_spaces.append(input[i])
    return list_without_spaces


def add_multiple_symbol(input):
    list1 = []
    symbols = ["(", ")", "+", "-", "*", "/", "^"]
    for i in range(len(input)):
        if i > 0 and input[i].isdigit() and input[i-1].isdigit():
            list1[len(list1)-1] = list1[len(list1)-1] + input[i]
        elif i > 0 and ((input[i-1] not in symbols and input[i] not in symbols) or
        (input[i] == '(' and input[i-1] not in symbols) or
        (input[i-1] == ')' and input[i] not in symbols) or
        (input[i-1] == ')' and input[i] == '(')):
            list1.append('*')
            list1.append(input[i])
        else:
            list1.append(input[i])
    return list1

'''
def parse_polynomial(text):
    return re.split(r'-+', text).strip()


def get_dictionary_of_polynomial(polynomial):
    dictionary = {}
    i = 0
    while i < len(polynomial):
        power = ''
        factor = '
        if polynomial[i] == ' ':
            i+=1
            continue
        if polynomial[i] == '+' or polynomial[i] == '-':
            sign =  polynomial[i]
            i+=1
            while polynomial[i].isdigit() and i < len(polynomial)-1 or polynomial[i] == r'/':
                factor = factor + polynomial[i]
                i += 1
            if i == len(polynomial)-1 and polynomial[i].isdigit():
                factor = factor + polynomial[i]
        if factor != '':
            if factor.find(r'/') == -1:
                factor = float(factor)
            else:
                numerator = factor[:factor.index(r'/')]
                denominator = factor[factor.index(r'/') +1:]
                factor = float(numerator)/ float(denominator)
            if sign == '-':
                factor = -factor
        else:
            if sign == '-':
                factor = -1.0
            else:
                factor = 1.0
        print('factor:', factor)
        if polynomial[i] == 'x':
            i += 1
            if polynomial[i] == '^':
                i+=1
                while polynomial[i].isdigit():
                    power = power + polynomial[i]
                    i+=1
                power = float (power)
            else:
                power = 1.0
            print('power', power)
        else:
            power = 0.0
            print('power', power)
        if power in dictionary:
            dictionary[power] += factor
        else:
            dictionary[power] = factor
        i+=1
    return dictionary
    '''


def final_move(notation):
    stack = []
    standart_operators = ["+", "-", "*", "/", "^"]
    for e in notation:
        if e in standart_operators:
            w1 = stack.pop()
            w2 = stack.pop()
            result = make_operation(e, w1, w2)
            stack.append(result)
        else:
            stack.append(e)
    return stack[0]


def make_operation(e, w1, w2):
    if e == '+':
        return w1 + w2
    if e == '*':
        return w1*w2
    if e == '-':
        w2 = w2 * get_new_form(['-', '1'], ['x', 'y', 'z'])
        return w1 + w2


def main():
    variables = ['x', 'y', 'z']
    polynomial1 = '(x+z)(y+x)-z(x+y)'
    polynomial2 = 'x(y+x)'
    if final_move(convert_to_postfix_notation(calculate_polynomial(add_multiple_symbol(delete_spaces(polynomial1)),
                                                                   variables))).dict ==\
            final_move(convert_to_postfix_notation(calculate_polynomial(add_multiple_symbol(delete_spaces(polynomial2)),
                                                                        variables))).dict:
        print('Polynomials are the same')
    else:
        print(final_move(convert_to_postfix_notation(calculate_polynomial(add_multiple_symbol(delete_spaces(polynomial1)),
                                                                   variables))).dict)
        print(final_move(convert_to_postfix_notation(calculate_polynomial(add_multiple_symbol(delete_spaces(polynomial2)),
                                                                          variables))).dict)
    '''
    print(calculate_polynomial(['(', 'x', '+', 'y', ')', '*', '(', 'x', '-', 'y', ')'], variables))
    print(calculate_polynomial(['(', '(', '(', 'x', '+', 'z', ')', '*',  '(', 'x', '-', 'y', ')', '-', '6', '*', 'x',
                                ')', ')'], ['x', 'y', 'z']))
    print(calculate_polynomial(['x', '+' ,'(', 'y', '+', '4', '*', 'x', '-', '(','5', '*', 'y' ,'-', '6',')','+', '(',
    '6','*', 'y','+','x',')','*','(', '5', '*', 'y', '-', '6',')',')','*','(','x','-','y' ,')'],  ['x', 'y', 'z']))

    polynomial1 ='+x^2 +2/4x^3 +54 -21'
    polynomial2 = '+8/16x^3 +1x^2 +33'
    dictionary1 = get_dictionary_of_polynomial(polynomial1)
    dictionary2 = get_dictionary_of_polynomial(polynomial2)
    for e in dictionary1:
        print (e, dictionary1[e])
    if dictionary1 == dictionary2:
        print('True')
    else:
        print('False')
    for e in dictionary2:
        print (e, dictionary2[e])
    '''
if __name__ == '__main__':
    main()