algorithm - 在单独的列表中获取多项式的幂和系数

Question

我已尽力获得用户在单独列表中给出的任意多项式的幂和系数。

基本上只使用系数部分而不使用幂部分，而是使用幂列表(变量)仅用于比较。我已经做到了并且它有效，但是代码有点草率和不优雅。有没有更好的编码方式？

基本上应该做的是:

当用户输入说:4x3+3 时，它应该返回如下内容:

coeffs = [4,0,0,3]    

这样我就可以使用 Horner 的方法求解多项式。

这是可运行的代码:REPL CODE

代码与测试函数一起运行:

x = solve(function)
x.parse()  

.

    #!/usr/bin/python3


    ######################################################################
    #code information
    #
    #
    #   When the user provides the input of the form
    #   4x3+2x+1
    #   The parse method is expected to return
    #   A coefficient list of the provided polynomial
    #   in ready for use for the horner's method of solving
    #######################################################################




    function = "4x3+2x+1" #this is the sample input the user is expected to give

    #

    class solve:

        def __init__(self, string):
            self.function = string
            self.letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g',
                            'h', 'i', 'j', 'k', 'l', 'm', 'n',
                            'o', 'p', 'q', 'r', 's', 't', 'u',
                            'v', 'w', 'x', 'y', 'z']


        #######################################################################
        #######################################################################
        #######################################################################
        #######################################################################   

        def parse(self):

            signs = ['+', '-', '*']
            for sign in signs:
                self.function = self.function.replace(sign, ' ')#this is where all the
                                                                #signs are converted
                                                                #to spaces





            self.function = self.function.split()       #this is where all the
                                                        #list is split into terms


            self.function.sort(reverse = True)      #the polynomial is sorted always
                                                    #in the decreasing order
                                                    #from higher to lower order of x





            coeffs = []         #list that holds all the coefficients

            powers = []         #list that holds all the powers


            while self.function:
                term = self.function.pop(0)#for each term in the polynomial

                for letter in self.letters: 
                    #check for the alphabets in the letters(The list above)



                    if letter in term:
                        x, y = term.split(letter)
                        coeffs.append(int(x))#append the coefficient to the list
                        if y != '':
                            powers.append(int(y))#append the power to the list
                        else:
                            powers.append(1) #append 1 for x ^ 1 term

                    else:
                        try:
                            temp = int(term) #exception occurs here
                            coeffs.append(temp)#append constant term after exhaution
                                                #of all the polynomial terms
                                                #if no constants exits
                                                #this is not reached
                                                #and neither the line
                                                #directly below
                            powers.append(0)#only for a constant,we have power 0

                            break   #break nonsense to append only once
                        except:
                            pass #exception passed silently


            return self.check_complete(coeffs, powers)








            print("The coefficients are: ", coeffs)
            print("The powers are: ", powers)


            #######################################################################
            #######################################################################
            #######################################################################
            #######################################################################



        def check_complete(self, coeffs, powers):
            """This function checks if the polynomial is a
            complete polynomial that is if it has all the powers of x
            it does this by comparing the two lists hand in hand,
            that is checks the corresponding terms"""

            try:
                #while the function arrives here
                #power and range are assumed to be of same length

                factor = 0  #factor for keeping track of index below

                for index in range(len(powers)):



                    ########################################
                    ########################################
                    Index = index + factor #just cleaning up


                    ########################################
                    ########################################



                    difference = powers[Index] - powers[Index+1]

                    while difference > 1:

                        factor += 1  #factor incremented to keep track
                                     #of where to add
                        difference -= 1

                        coeffs.insert(Index+1, 0)#in the coefficient list
                                            #insert zeros where the
                                            #polynomial is missing a term


            except:

                return coeffs #pass the exception

Answer 1

是的，你把这件事搞得太复杂了。另外，我认为您在解析时犯了一个错误，因为您将所有运算符都视为加法:将它们更改为空格，然后忽略差异。我会对此进行测试，但您未能提供 MCVE。

我建议采取一些简单的步骤。考虑多项式 1+4x3-2x。

1. 从您的文本中，我得知您只允许使用单个小写字母的单个变量。不要经历定义字母表的麻烦(无论如何已经在系统包中)；只需在字符串中找到一个字母，并将其存储为分隔符 sep。
2. 扫描字符串，除以任何加号或减号； 保留标志。这应该产生列表 ["1", "+4x3", "-2x"]。
3. 扫描列表；对于没有 sep 变量的任何字符串，附加“x0”；对于任何在 sep 之前没有数字的，在前面加上“1”；对于 sep 之后没有数字的任何内容，附加一个“1”；对于任何没有前导符号的(只能是列表的第一个元素)，在前面加上“+”。我们现在有 ["+1x0", "+4x3", "-2x1"].
4. 现在，扫描列表中的每个元素。在 sep 拆分并将元素转换为整数元组。 [(1, 0), (4, 3), (-2, 1)]。
5. 最后，构建您的系数列表。我们将元组列表称为术语。获得最高权力并使其成为 0 列表的最大索引。然后简单地将每个系数分配到相应幂的位置。

代码:

size = max[z[1] for z in terms] + 1
coeff = [0]*size
for term in terms:
    coeff[term[1]] = term[0]