Polynomial Division多项式除法

收藏到CSDN网摘

多项式除法的问题,可将字符串转为{次数:系数}的dict保存起来,然后进行四则混合运算.并将结果输出.具体与手算区别不大,唯一要注意的是:
1.±1的处理
2.0次项处理
3.空字符串处理
4.合并同次数项.


下面的poly类可以接受一个字符串或者dict来初始化,可做+-*/四则混合运算,可以print或者str()转为字符串输出.
这是个多项式除法的例子,该类也可被用来化简多项式.

class poly(object):
    # equation class, read string in, save the polynomial equation
    def __init__(self,eq):
        if isinstance(eq,str):
            if len(eq)==0:
                self.dic = {}
            else:
                eq = eq.replace('-','+-')
                self.dic = {} # use loop to process case like: x+x+3 = 2*x+3
                for part in eq.split('+'):
                    if len(part)==0: continue
                    self.dic[part.count('x')] = self.dic.get(part.count('x'),0) + \
                            float(part.replace('*','').replace('x','')!='' and \
                                  (part.replace('*','').replace('x','')!='-' and part.replace('*','').replace('x','') or \
                                   -1) or 1)
        elif isinstance(eq,dict):
            self.dic = eq
        else:
            self.dic = {}

    def order(self):
        if len(self.dic)==0: return 0
        return max(self.dic.keys())
    
    def __repr__(self):
        # str()
        if len(self.dic)==0:
            return ''
        s = []
        for k in sorted(self.dic.keys(),reverse=True):
            s.append((self.dic[k]==-1 and (k==0 and '-1' or '-') or \
                      (self.dic[k]!=1 and str(int(self.dic[k])==self.dic[k] and int(self.dic[k]) or self.dic[k]) + \
                       (k>0 and '*' or '') or (k==0 and '1' or ''))) + \
                     '*'.join('x'*k))
        return '+'.join(s).replace('+-','-')

    def __add__(self,x):
        # a + b
        new_dic = {}
        for k in self.dic.keys()+x.dic.keys():
            new_dic[k] = self.dic.get(k,0)+x.dic.get(k,0)
        new_dic = {k:v for k,v in new_dic.items() if v!=0}
        return poly(new_dic)

    def __sub__(self,x):
        # a - b
        new_dic = {}
        for k in self.dic.keys()+x.dic.keys():
            new_dic[k] = self.dic.get(k,0)-x.dic.get(k,0)
        new_dic = {k:v for k,v in new_dic.items() if v!=0}
        return poly(new_dic)

    def __mul__(self,x):
        # a * b
        new_dic = {}
        for k1,v1 in self.dic.items():
            for k2,v2 in x.dic.items():
                ck = k1+k2
                cv = v1*v2
                new_dic[ck] = new_dic.get(ck,0)+cv
        new_dic = {k:v for k,v in new_dic.items() if v!=0}
        return poly(new_dic)

    def __div__(self,x):
        # a / b
        max_x = x.order()
        if self.order() < max_x:
            return [str(poly({})),str(self)]
        else:
            new_dic = self.dic # save original dic
            q = poly({})
            while self.order() >= max_x:
                cur_k = self.order()-max_x
                cur_v = self.dic[self.order()]/x.dic[max_x]
                q.dic[cur_k] = cur_v
                self -= poly({cur_k:cur_v})*x
            r = self.dic
            self.dic = new_dic
            return [str(q),str(poly(r))]
        
def checkio(data):
    a, b = data
    ap = poly(a)
    bp = poly(b)
    result = ap/bp
    print a,'/',b,'=',result
    return result

checkio(["x*x*x-12*x*x-42","x-3"])

#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    assert checkio(['x*x*x-12*x*x-42', 'x-3']) == ['x*x-9*x-27', '-123'], "1st"
    assert checkio(['x*x-1', 'x+1']) == ['x-1', ''], "2nd"
    assert checkio(['x*x*x+6*x*x+12*x+8', 'x+2']) == ['x*x+4*x+4', ''], "3rd"
    assert checkio(['x*x*x*x*x+5*x+1', 'x*x']) == ['x*x*x', '5*x+1'], "4th"

结果:

>>> ================================ RESTART ================================
>>> 
x*x*x-12*x*x-42 / x-3 = ['x*x-9*x-27', '-123']
x*x*x-12*x*x-42 / x-3 = ['x*x-9*x-27', '-123']
x*x-1 / x+1 = ['x-1', '']
x*x*x+6*x*x+12*x+8 / x+2 = ['x*x+4*x+4', '']
x*x*x*x*x+5*x+1 / x*x = ['x*x*x', '5*x+1']
>>>