多项式相加（Python实现）_给定如下的多项式,用字典表示该多项式,并完成多项式的加法。要求:无论在运算对象-程序员宅基地

技术标签： python Python

多项式

使用列表存储多项式

使用字典存储多项式

多项式

多项式是数学中相当重要的表达方式，如果使用计算机来处理多项式的各种相关运算，通常可以使用线性表、链表和字典等数据结构来存储多项式。

假如一个多项式 $P(x)=a_{n}X^{n}+a_{n-1}X^{n-1}+...+a_{1}X+a_{0}$ ，P(x)就为一个n次多项式。

使用列表存储多项式

使用一个二维列表来存储多项式。二维列表中的每个元素均为一个列表，存储多项式中某一项的指数和系数。例如多项式 $p=2X^{5}+3X^{4}+5X^{2}+4X+1$ 可以用二维列表表示为：

[[5, 2], [4, 3], [2, 5], [1, 4], [0, 1]]

使用字典存储多项式

字典也可以存储一个多项式。字典中以多项式指数为key，指数对应的系数和为value。例如多项式 $p=2X^{5}+3X^{4}+5X^{2}+4X+1$ 可以用字典存储为：

{5: 2, 4: 3, 2: 5, 1: 4, 0: 1}

使用链表存储多项式

链表也可以存储多项式。每一个节点的数据域中，存储每项的系数和指数。

解决方案

使用列表

根据上面建立的数据结构模型，我们使用二维列表来表示和存储多项式。

class PolyException(Exception):
    def __init__(self, message, code):
        self.message = message
        self.code = code


def parse_poly(poly):
    """
    parse poly
    :param poly: string
    :return: list
    """
    poly_list = poly.split("+")
    result = []
    for pos in range(len(poly_list)):
        poly_list[pos] = poly_list[pos].strip()
        if "X" not in poly_list[pos]:
            if not poly_list[pos].isdigit():
                raise PolyException("poly format error.", 1001)

        temp_list = poly_list[pos].split("X^")
        if len(temp_list) != 2 and len(temp_list) != 1:
            raise PolyException("poly format error.", 1002)

        if len(temp_list) == 2:
            key = int(temp_list[1])
            if temp_list[0] == "":
                value = 1
            else:
                value = int(temp_list[0])
        else:
            key = 0
            value = int(temp_list[0])

        index = -1
        for i in range(len(result)):
            if result[i][0] == key:
                index = i
                break

        if index != -1:
            result[index][1] += value
        else:
            result.append([key, value])

    return result


def add(poly_a_list, poly_b_list):
    for data in poly_b_list:
        exist = False
        for i in range(len(poly_a_list)):
            if data[0] == poly_a_list[i][0]:
                poly_a_list[i][1] += data[1]
                exist = True
                break

        if not exist:
            poly_a_list.append(data)
    return poly_a_list


if __name__ == '__main__':
    # 1. 输入两个多项式
    try:
        poly_a = input("Input polynomial A: ")
        # poly_a = "X^4+1"
        poly_a_list = parse_poly(poly_a)
        poly_b = input("Input polynomial B: ")
        # poly_b = "3X^2+3X^4+3"
        poly_b_list = parse_poly(poly_b)

        # 2. 多项式相加
        result = add(poly_a_list, poly_b_list)

        # 3. 输出结果
        print("result is: ", end="")

        message_list = []
        for data in result:
            if data[0] == 0:
                message_list.append(str(data[1]))
            else:
                message_list.append(str(data[1]) + "X^" + str(data[0]))
        print("+".join(message_list))
    except PolyException as e:
        print("errcode: %s" % e.code)
        print("errmsg: %s" % e.message)

使用字典

下面采用字典数据结构来存储多项式。当多项式相加时，指数相同（即Key相同），系数相加（即Value相加合并），最后得到的字典就是两个多项式相加的结果。

class PolyException(Exception):
    def __init__(self, message, code):
        self.message = message
        self.code = code


def parse_poly(poly):
    """
    parse poly
    :param poly: string
    :return: dict
    """
    poly_list = poly.split("+")
    poly_dict = {}
    for pos in range(len(poly_list)):
        poly_list[pos] = poly_list[pos].strip()
        if "X" not in poly_list[pos]:
            if not poly_list[pos].isdigit():
                raise PolyException("poly format error.", 1001)

        temp_list = poly_list[pos].split("X^")
        if len(temp_list) != 2 and len(temp_list) != 1:
            raise PolyException("poly format error.", 1002)

        if len(temp_list) == 2:
            key = temp_list[1]
            value = temp_list[0]
        else:
            key = 0
            value = temp_list[0]

        if key in poly_dict:
            poly_dict[key] += value
        else:
            poly_dict[key] = value

    return poly_dict


if __name__ == '__main__':
    # 1. 输入两个多项式
    try:
        poly_a = input("Input polynomial A: ")
        # poly_a = "3X^4+1"
        poly_a_dict = parse_poly(poly_a)
        poly_b = input("Input polynomial B: ")
        # poly_b = "3X^4+5"
        poly_b_dict = parse_poly(poly_b)
    except PolyException as e:
        print("errcode: %s" % e.code)
        print("errmsg: %s" % e.message)
        exit(e.code)

    # 2. 多项式相加
    for key in poly_b_dict:
        if key in poly_a_dict:
            poly_a_dict[key] = int(poly_a_dict[key]) + int(poly_b_dict[key])
        else:
            poly_a_dict[key] = int(poly_b_dict[key])

    # 3. 输出结果
    print("result is: ")

    message = ""
    for key in poly_a_dict:
        if key == 0:
            message += str(poly_a_dict[key]) + " + "
        else:
            message += str(poly_a_dict[key]) + "X^" + str(key) + " + "
    message = message[:-3]
    print(message)

使用链表

我们使用单向链表结构来表示和存储多项式。不同于链接中单向链表的节点数据结构，我们重新定义节点结构PolyNode，并重写链表类，仅保留多项式相加相关的方法，并适配新的节点结构。我们将上述代码保存在link.py中：

class PolyNode(object):
    def __init__(self, value, exponent):
        self.value = value
        self.exponent = exponent
        self.next = None

    def __add__(self, other_node):
        self.next = other_node

    def __eq__(self, other_node):
        if self.value != other_node.value:
            return False
        elif self.exponent != other_node.exponent:
            return False
        else:
            return True

    def update(self, other_node):
        self.value = other_node.value
        self.exponent = other_node.exponent


class LinkedList(object):
    def __init__(self):
        self.head = PolyNode(0, 0)

    def empty(self) -> bool:
        return self.head.next is None

    def add(self, node):
        if self.empty():
            self.head + node
        else:
            ptr = self.head.next
            self.head + node
            node + ptr

    def extend(self, linked_list):
        if linked_list.empty():
            return

        point = self.head.next
        while point.next is not None:
            point = point.next
        point + linked_list.head.next
        return

    def remove(self, target: PolyNode):
        if self.empty():
            raise ValueError("remove from empty linked list")

        ptr = self.head.next
        left_ptr = self.head

        while True:
            if ptr == target:
                break

            if ptr.next is None:
                raise IndexError("value do not exist")

            ptr = ptr.next
            left_ptr = left_ptr.next

        if ptr.next is None:
            left_ptr.next = None
        else:
            left_ptr.next = ptr.next
        return

    def __len__(self):
        if self.empty():
            return 0

        ptr = self.head.next
        count = 0
        while ptr is not None:
            count += 1
            ptr = ptr.next
        return count

    def find(self, exponent):
        if self.empty():
            return

        ptr = self.head
        while ptr.next is not None:
            ptr = ptr.next
            if ptr.exponent == exponent:
                return ptr


def create() -> LinkedList:
    return LinkedList()


def parse_poly(poly):
    poly_list = poly.split("+")
    poly_linked = create()
    for pos in range(len(poly_list)):
        poly_list[pos] = poly_list[pos].strip()
        if "X" not in poly_list[pos]:
            if not poly_list[pos].isdigit():
                raise ValueError("poly format error.")

        temp_list = poly_list[pos].split("X^")
        if len(temp_list) != 2 and len(temp_list) != 1:
            raise ValueError("poly format error.")

        if len(temp_list) == 2:
            key = temp_list[1]
            value = temp_list[0]
        else:
            key = 0
            value = temp_list[0]

        if value == "":
            value = 1
        else:
            value = int(value)
        key = int(key)

        node = poly_linked.find(key)
        if node is None:
            poly_linked.add(PolyNode(value, key))
        else:
            value += node.value
            poly_linked.replace(node, PolyNode(value, key))
    return poly_linked


def add(linked1, linked2):
    ptr1 = linked1.head.next

    added_node = []
    while ptr1 is not None:
        ptr2 = linked2.head.next
        while ptr2 is not None:
            if ptr2.exponent == ptr1.exponent:
                ptr1.value += ptr2.value
                added_node.append(ptr2)
                break
            ptr2 = ptr2.next
        ptr1 = ptr1.next

    for node in added_node:
        linked2.remove(node)
    if len(linked2) > 0:
        linked1.extend(linked2)


def print_result(linked):
    print("result is:", end="")
    ptr = linked.head.next
    message_list = []
    while ptr is not None:
        if ptr.exponent == 0:
            message_list.append(str(ptr.value))
        else:
            message_list.append(str(ptr.value) + "X^" + str(ptr.exponent))
        ptr = ptr.next
    print("+".join(message_list))


if __name__ == '__main__':
    try:
        poly_a = input("Input polynomial A: ")
        # poly_a = "X^4+1"
        poly_a_linked = parse_poly(poly_a)

        poly_b = input("Input polynomial B: ")
        # poly_b = "3X^2+3X^4+6"
        poly_b_linked = parse_poly(poly_b)

        add(poly_a_linked, poly_b_linked)
        print_result(poly_a_linked)
    except ValueError as e:
        print(str(e))

传送门

本文链接：https://blog.csdn.net/TCatTime/article/details/104464335

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

c# 调用c++ lib静态库_c#调用lib-程序员宅基地

文章浏览阅读2w次，点赞7次，收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案，在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建：添加Visual C++ , Win32 项目这......_c#调用lib

deepin/ubuntu安装苹方字体-程序员宅基地

文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体，挺好看的。注重颜值的网站都会使用，例如知乎：font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang

html表单常见操作汇总_html表单的处理程序有那些-程序员宅基地

文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--method将表单中的数据传送给服务器处理，get方式直接显示在url地址中，数据可以被缓存，且长度有限制；而post方式数据隐藏传输，_html表单的处理程序有那些

PHP设置谷歌验证器（Google Authenticator）实现操作二步验证_php otp 验证器-程序员宅基地

文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证（即Google Authenticator服务）后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器

【Python】matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距-程序员宅基地

文章浏览阅读4.3k次，点赞5次，收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距

docker — 容器存储_docker 保存容器-程序员宅基地

文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节，实现了多层数据的堆叠，为用户提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制（CoW）策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的，不建议用于生成环境。_docker 保存容器

随便推点

网络拓扑结构_网络拓扑csdn-程序员宅基地

文章浏览阅读834次，点赞27次，收藏13次。网络拓扑结构是指计算机网络中各组件（如计算机、服务器、打印机、路由器、交换机等设备）及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式，也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn

JS重写Date函数，兼容IOS系统_date.prototype 将所有 ios-程序员宅基地

文章浏览阅读1.8k次，点赞5次，收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时，通常的做法是：new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的，而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠，也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑，需要做一些额外的特殊处理，笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数，一劳永逸，避免每次ne_date.prototype 将所有 ios