头歌实践平台（python数据结构）(1-6)-Toy模板网

这篇具有很好参考价值的文章主要介绍了头歌实践平台（python数据结构）(1-6)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第1关：栈抽象数据类型及其实现

任务描述
相关知识
- 栈抽象数据类型
- List 的操作方法
编程要求
测试说明

任务描述

本关任务：编写代码实现栈的基本操作。

相关知识

为了完成本关任务，你需要掌握：

栈抽象数据类型；
Python 中 List 的操作方法。

栈抽象数据类型

抽象数据类型“栈”是一个有次序的数据集。在栈中，数据项的加入和移除都仅发生在同一端，这一端被称为栈顶，相对地，把另一端称为栈底。

距离栈底越近的数据项，留在栈中的时间就越长，而最新加入栈的数据项会被最先移除。这种次序通常称为“后进先出”（ LIFO ）：Last in First out。下图是一个栈的抽象模型：

图1 栈模型

抽象数据类型“栈”定义为如下的操作：

Stack()创建一个新的空栈。它不需要参数，并返回一个空栈。
push(item)将新项添加到堆栈的顶部。它需要参数 item 并且没有返回值。
pop()从栈顶删除项目。它不需要参数，返回 item。栈被修改。
peek()返回栈顶的项，不删除它。它不需要参数。堆栈不被修改。
is_empty()测试看栈是否为空。它不需要参数，返回一个布尔值。
size()返回栈的项目数。它不需要参数，返回一个整数。

下面通过一个案例来演示栈的使用：

stack = Stack() # 创建一个新的空栈
stack.is_empty() # 通过 is_empty() 函数检验栈是否为空，返回值为 True
# 向栈内压入三个元素
stack.push(2020)
stack.push('mouse')
stack.push('Educoder')
# 此时，栈中内容为：[2020, 'mouse', 'Educoder']（第一个压入的元素为栈底）
stack.pop() # 使用 pop() 函数将栈顶元素弹出，返回值为 'Educoder'
# 此时，栈中内容为：[2020, 'mouse']
stack.size() # 使用 size() 函数统计栈的项目数，返回值为 2

List 的操作方法

列表（ List ）是 Python 中最基本的数据结构。List 中的每个元素都分配有索引，第一个索引是 0，第二个索引是 1，依此类推。

List 可以进行的操作包括增加元素，删除元素，检查成员等。借助 List 的append()和pop()，用户可以方便地实现栈的压入和弹出。

编程要求

在右侧编辑器 Begin - End 之间补充代码，使用 List 实现栈。具体要求为：补充完整is_empty()、push()、pop() 和size()四个函数，分别实现判断栈是否为空、出栈、入栈和统计栈的项目数四个功能。

测试说明

平台会对你编写的代码进行测试，为了检查栈的定义是否正确，后台会通过 input 接收一个包含数字的字符串，调用定义的栈的操作，分别打印输出栈的长度和栈内的元素：

测试输入：

1 2 3 4 5

预期输出：

5
5 4 3 2 1

# -*- coding: utf-8 -*-

'''请在Begin-End之间补充代码, 完成Stack类'''
class Stack():
    # 创建空列表实现栈
    def __init__(self): 
        self.__list = []
  
    # 判断是否为空，输出为True或False
    def is_empty(self): 
        if len(self.__list)==0:
            return True
        return False
    # 压栈，添加元素
    def push(self,item): 
        # ********** Begin ********** #
        self.__list.append(item)

        # ********** End ********** #  
    # 弹栈，弹出最后压入栈的元素
    def pop(self): 
        # ********** Begin ********** #
        assert not self.is_empty()
        return self.__list.pop()

        # ********** End ********** #  
    # 栈的长度
    def size(self):
        # ********** Begin ********** #
        return len(self.__list)

        # ********** End ********** #      

if __name__ == "__main__":
    stack = Stack() 
    nums = input().split()
    # 将nums中的元素依次入栈
    for num in nums:
        stack.push(num)
    # 打印栈的长度
    print(stack.size())
    # 将栈中元素依次弹出
    while not stack.is_empty():
        print(stack.pop(), end = ' ')

第2关：栈应用之括号匹配问题

任务描述
相关知识
编程要求
测试说明

任务描述

本关任务：编写程序检查该字符串的括号是否成对出现。

相关知识

为了完成本关任务，你需要掌握：栈的 Python 实现。栈的相关知识及其实现参见第一关。

编程要求

根据提示，在右侧编辑器 Begin - End 之间补充代码，判断字符串是否有效，即字符串中括号是否成对出现。若是，则输出 True ，否则输出 False 。其中字符串的字符只包含三种括号，花括号{}、中括号[]、圆括号()，即它仅由 (、)、[、]、{、}六个字符组成。

提示

S1：遍历输入的括号序列，如果是左括号，进入S2，如果是右括号，进入S3；
S2：如果当前遍历到左括号，则入栈；
S3：如果当前遍历到右括号，则出栈一个元素，看其是否与当前的右括号组成一对，如果不是，则匹配失败。或者在出栈过程中发生异常（从空栈中出栈），也匹配失败；
S4：若能顺利遍历完成，检查栈中是否还有剩余元素，如果有，则匹配失败；如果没有，则匹配成功。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：

测试输入：{ [ ] ( ) } 预期输出：True

测试输入：[ ( { } [ ] ) ] 预期输出：True

开始你的任务吧，祝你成功！

# -*- coding: utf-8 -*-

class Stack():
    # 创建空列表实现栈
    def __init__(self): 
        self.__list = []   
    # 判断是否为空
    def is_empty(self): 
        return self.__list == []
    # 压栈，添加元素
    def push(self,item): 
        self.__list.append(item)
    # 弹栈，弹出最后压入栈的元素
    def pop(self): 
        if self.is_empty():
            return 
        else:
            return self.__list.pop() 
        
'''请在Begin-End之间补充完成代码, 完成syntaxChecker函数, 解决括号匹配问题'''
def syntaxChecker(strList):
    ### strList: 字符串列表
    stack = Stack()
    left = '([{'     # 左括号
    right = ')]}'    # 右括号
    flag = True      # 标志位
    # ********** Begin ********** #
    #判断字符长度如果不能整除2或者输入为空，直接返回false
    if len(strList)%2!=0 or len(strList)==0:
        flag=False
    else:
        i=0
        while i<len(strList):
            e = strList[i] 
            if e in left:
                stack.push(e)#元素依次入栈
            else:#如果该元素在右括号内，判断栈为空或者出栈元素不为左括号返回false
                if e ==right[0] and (stack.is_empty() or stack.pop() !=left[0] ):
                    flag = False
                if e == right[1] and (stack.is_empty() or stack.pop() != left[1]):
                    flag = False
                if e ==right[2] and (stack.is_empty() or stack.pop() !=left[2] ):
                    flag = False
            i+=1#while循环遍历，flag不变则返回True
    # ********** End ********** # 
    return flag

if __name__ == "__main__":
    strList = input().split()
    result = syntaxChecker(strList)
    print(result)

第1关：队列抽象数据类型

任务描述
相关知识
- 队列抽象数据类型
- List 的操作方法
编程要求
测试说明

任务描述

本关任务：编写代码实现队列的基本操作。

编程要求

在右侧编辑器 Begin - End 之间补充代码，使用 List 实现队列的基本抽象数据类型，即is_empty()、enqueue()、dequeue( )和size()。具体要求如下：

实现enqueue()函数，将输入数组依次压入队列中；
实现size()函数，打印队列的长度；
实现is_empty()和dequeue()函数，将队列中元素依次弹出并打印出来。

测试说明

平台会对你编写的代码进行测试：

测试输入：

1 5 3 4 2

预期输出：

5
1 5 3 4 2

开始你的任务吧，祝你成功！

# -*- coding: utf-8 -*-

'''请在Begin-End之间补充代码, 完成Queue类'''


class Queue():
    # 创建空列表实现队列
    def __init__(self):
        self.__list = []
        # 判断是否为空

    def is_empty(self):
        # ********** Begin ********** #
        return len(self.__list)==0
        # ********** End ********** #

    # 从队尾插入
    def enqueue(self, item):
        # ********** Begin ********** #
        self.__list.append(item)
        # ********** End ********** #

    # 从队首弹出
    def dequeue(self):
        # ********** Begin ********** #
        assert not self.is_empty()
        return self.__list.pop(0)
        # ********** End ********** #

    # 队列的长度
    def size(self):
        # ********** Begin ********** #
        return len(self.__list)
        # ********** End ********** #


if __name__ == "__main__":
    queue = Queue()
    nums = input().split()
    # 将nums中的元素依次送入队列
    for num in nums:
        queue.enqueue(num)
    print(queue.size())
    # 将队列中的元素依次弹出
    while not queue.is_empty():
        print(queue.dequeue(), end=' ')

第2关：队列应用之约瑟夫环问题

任务描述
相关知识
- 队列的 Python 实现
- 约瑟夫环问题
编程要求
测试说明

任务描述

本关任务：使用队列解决约瑟夫环问题。

编程要求

根据提示，在右侧编辑器 Begin - End 之间补充代码，完成 JosephusSolver 函数，求解被杀掉人的顺序。

提示：

S1：将编号0,…,n−1循环压入队列；
S2：设置一个计数器，保存当前次数；
S3：当队列的长度大于1时，一直进行循环操作 S4；
S4：从队首取一个人出队，如果这个人报数正好是 m 那么就被杀掉，然后下一个人继续从1开始报数。如果不是 m 的话在重新入队，计数器继续 +1。

测试说明

平台会对你编写的代码进行测试：

测试输入：

输入说明：输入第一行为n，第二行为m。

预期输出：[4, 3, 5, 1, 2, 0]

测试输入：

12
3

预期输出：[2, 5, 8, 11, 3, 7, 0, 6, 1, 10, 4, 9]

开始你的任务吧，祝你成功！

# -*- coding: utf-8 -*-

class Queue():
    # 创建空列表实现队列
    def __init__(self):
        self.__list = []
        # 判断是否为空

    def is_empty(self):
        return self.__list == []

    # 从队尾插入
    def enqueue(self, item):
        self.__list.insert(0, item)

    # 从队首弹出
    def dequeue(self):
        if self.is_empty():
            return
        else:
            return self.__list.pop()
            # 队列长度

    def size(self):
        return len(self.__list)


'''请在Begin-End之间补充完成代码, 完成JosephusSolver函数, 解决约瑟夫环问题'''


def JosephusSolver(n, m):
    queue = Queue()
    result = []
    # ********** Begin ********** #
    for i in range(0, n): # 元素进队
        queue.enqueue(i)
    number = 1 #
    while queue.size()>0: # 不为空
        if number == m:
            result.append(queue.dequeue())# 出队
            number = 1 #循环遍历列表
        else:
            queue.enqueue(queue.dequeue()) # 出队元素出队又重进，改变顺序
            number = number + 1
    # ********** End ********** #
    return result


if __name__ == "__main__":
    n = int(input())
    m = int(input())
    print(JosephusSolver(n, m))

第1关：双端队列抽象数据

任务描述
相关知识
编程要求
测试说明

任务描述

本关任务：编写代码实现双端队列的基本操作。

相关知识

为了完成本关任务，你需要掌握：双端队列抽象数据类型。

双端队列 Deque 是一种有次序的数据集。跟队列相似，其两端可以称首端和尾端，但 Deque 中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。

某种意义上说，双端队列集成了栈和队列的能力，但双端队列并不具有内在的 LIFO 或者 FIFO 特性。下图是一个双端队列的抽象模型：

图1 - 双端队列模型

抽象数据类型 Deque 由如下操作定义：

Deque()：创建一个空双端队列，无参数，返回值为 Deque 对象。
add_front(item)：在队首插入一个元素，参数为待插入元素，无返回值。
add_rear(item)：在队尾插入一个元素，参数为待插入元素，无返回值。
remove_front()：在队首移除一个元素，无参数，返回值为该元素。双端队列会被改变。
remove_rear()：在队尾移除一个元素，无参数，返回值为该元素。双端队列会被改变。
is_empty()：判断双端队列是否为空，无参数，返回布尔值。
size()：返回双端队列中数据项的个数，无参数，返回值为整型数值。

下面通过一个案例来演示队列的使用： # 创建一个空双端队列 deque = Deque()

# 通过`is_empty()`函数检验双端队列是否为空
deque.is_empty() # 返回值为 True
# 通过 add_front() 从队首插入两个元素
deque.add_front(2020)
deque.add_front('mouse')
# 此时，队列中内容为：['mouse', 2020]（左侧为队首）
# 通过 add_rear() 从队尾插入两个元素
deque.add_front(3)
deque.add_front(26)
# 此时，队列中内容为：['mouse', 2020, 3, 26]（右侧为队尾）
# 通过 remove_front() 函数将队首元素弹出
deque.remove_front() # 返回值为 'mouse'
# 此时，队列中内容为：[2020, 3, 26]
# 通过 remove_rear() 函数将队尾元素弹出
deque.remove_rear() # 返回值为 26
# 此时，队列中内容为：[2020, 3]
# 通过 size()函数统计队列的项目数
# deque.size() # 返回值为 2

编程要求

在右侧编辑器 Begin - End 补充代码，使用 List 实现双端队列。具体要求如下：

实现add_rear()函数，将第一行输入的元素依次从队尾送入队列；
实现add_front()函数，将第二行输入的元素依次从队头送入队列；
实现remove_front()函数，将队列内元素从队头弹出；
实现remove_rear()函数，将队列内元素从队尾弹出；
队列中的元素平台将按照先头后尾的次序交替打印。

例如：第一行输入：1 2 3，从队尾送入队列；第二行输入4 5，从队头送入队列；此时双端队列中的内容为5 4 1 2 3；按照先头后尾的次序将队列中的元素交替弹出，故输出为：5 3 4 2 1。

测试说明

平台会对你编写的代码进行测试：

测试输入： 1 3 5 7 8 6 4 2 1 3 5 7 8 6 4 2 预期输出： 2 2 4 4 6 6 8 8 7 7 5 5 3 3 1 1

测试输入： 1 7 2 6 3 5 4 1 2 3 4 5 6 7 预期输出： 7 4 6 5 5 3 4 6 3 2 2 7 1 1

开始你的任务吧，祝你成功！

# -*- coding: utf-8 -*-
      
'''请在Begin-End之间补充代码, 完成 Deque 类'''
class Deque():
    #初始化列表
    def __init__(self): 
        self.items = []
    # 判断队列是否为空
    def is_empty(self): 
        return self.items == []
    # 在队头添加元素
    def add_front(self, item): 
        # ********** Begin ********** #
        self.items.insert(0,item)
    # ********** End ********** #
    # 队尾添加元素
    def add_rear(self, item):
    # ********** Begin ********** #
        self.items.append(item)

    # ********** End ********** #
    # 从队头弹出元素
    def remove_front(self):

    # ********** Begin ********** #
        return self.items.pop(0)

    # ********** End ********** #
    # 从队尾弹出元素
    def remove_rear(self):

    # ********** Begin ********** #
         return self.items.pop(-1)

        # ********** End ********** # 
    # 返回队列尺寸
    def size(self): 
        return len(self.items)


if __name__ == "__main__":
    deque = Deque()
    nums1 = input().split()
    # 将nums1中的元素依次从队尾送入队列
    for num in nums1:
        deque.add_rear(num)
    nums2 = input().split()
    # 将nums2中的元素依次从队头送入队列
    for num in nums2:
        deque.add_front(num)    
    # 将队列中的元素按照先头后尾的次序交替弹出
    while not deque.is_empty():
        print(deque.remove_front(), end = ' ')    # 先从队头弹出元素
        if not deque.is_empty():
            print(deque.remove_rear(), end = ' ') # 再从队尾弹出元素

第2关：双端队列应用之回文

任务描述
相关知识
- 回文词
编程要求
测试说明

任务描述

本关任务：编写程序应用双端队列判定字符串是否为回文词。

相关知识

为了完成本关任务，你需要掌握双端队列的 Python 实现和回文词。双端队列的相关知识及其实现方法参见第一关。

回文词

“回文词”是指正读和反读都一样的词，如 radar、 madam、 toot 等。

编程要求

根据提示，在右侧编辑器 Begin - End 之间补充代码，完成 palChecker 函数，应用双端队列解决判定字符串是否为回文词。若输入的字符串是回文词，则输出True；否则，输出False。

提示

S1：将字母依次压入双端队列中；
S2：从首端和尾侧分别弹出字母，若两者不相同，则不是回文词；
S3：重新执行步骤 S2，当队列中没有元素或仅有一个元素时，该单词为回文词。

测试说明

平台会对你编写的代码进行测试：

测试输入： lsdkjfskf 预期输出： False

测试输入： radar 预期输出： True

开始你的任务吧，祝你成功！

# -*- coding: utf-8 -*-
  
class Deque():
    #初始化列表
    def __init__(self): 
        self.items = []
    # 判断队列是否为空
    def is_empty(self): 
        return self.items == []
    # 在队头添加元素
    def add_front(self, item): 
        self.items.insert(0,item)
    #队尾添加元素
    def add_rear(self, item): 
        self.items.append(item)
    # 从队头弹出元素
    def remove_front(self): 
        if self.is_empty():
            return 
        else:
            return self.items.pop(0)
    # 从队尾弹出元素
    def remove_rear(self): 
        if self.is_empty():
            return 
        else:
            return self.items.pop()
    # 返回队列大小
    def size(self): 
        return len(self.items)
    
'''请在Begin-End之间补充完成代码, 完成 palChecker 函数, 完成回文词判定'''
def palChecker(String):
    deque = Deque()
    # ********** Begin ********** #
    for i in String:
        deque.add_rear(i) # 任意输入方式
    l=int(len(String)/2)
    for i in range(l):
        if deque.remove_rear()!=deque.remove_front(): # 如果首出与尾出在前半部分不同则False
            return False

    return True
    # ********** End ********** #

if __name__ == "__main__":
    String = input()
    print(palChecker(String))

第1关：无序列表的链表实现

任务描述
相关知识
- 列表
- 无序列表抽象数据类型
- 节点 Node 类
编程要求
测试说明

任务描述

本关任务：编写程序基于链表实现无序列表。

相关知识

为了完成本关任务，你需要掌握：

列表；
无序列表抽象数据类型；
节点 Node 类。

列表

列表是一种数据项按照相对位置存放的数据集。其中，无序列表的数据项只按照存放位置来索引，如第1个、第2个、……、最后一个等；而有序列表的数据项依照其某可比性质来决定其在列表中的位置，如整数大小、字母表先后。

下面我们先来学习无序列表。

无序列表抽象数据类型

无序列表是一个没有特定顺序的列表项的集合，其特点为数据的排列不具有顺序性。无序表 List 的操作定义如下：

List()：创建一个新的空列表。它不需要参数，并返回一个空列表。
add(item)：向列表中添加一个新项。它需要 item 作为参数，并不返回任何内容（假定该 item 不在列表中）。
remove(item)：从列表中删除该项。它需要 item 作为参数并修改列表（假设项存在于列表中）。
search(item)：搜索列表中的项目。它需要 item 作为参数，并返回一个布尔值。
isEmpty()：检查列表是否为空。它不需要参数，并返回布尔值。
size（）：返回列表中的项数。它不需要参数，并返回一个整数。
index(item)：返回项在列表中的位置。它需要 item 作为参数并返回索引（假定该项在列表中）。
insert(pos，item)：在位置 pos 处向列表中添加一个新项。它需要 item 作为参数并不返回任何内容。假设该项不在列表中，并且有足够的现有项使其有 pos 的位置。
pop()：删除并返回列表中的最后一个项（假设该列表至少有一个项）。
pop(pos)：删除并返回位置 pos 处的项。它需要 pos 作为参数并返回项（假定该项在列表中）。

下面通过一个案例来演示无序列表的使用： # 创建一个新的无序列表 ulist = List()

# 通过 isEmpty() 函数检验列表是否为空
ulist.isEmpty() # 返回值为 True
# 通过 add() 向列表内添加三个元素
ulist.add(2020)
ulist.add(3)
ulist.add(26)
# 此时，列表中元素为：26 3 2020
# 通过 search() 操作判断列表内是否存在某元素
ulist.search(3) # 返回值为 True
# 通过remove()操作删除该项
ulist.remove(3)
# 此时，列表中元素为：26 2020
# 通过 size() 函数统计列表的项目数
ulist.size() # 返回值为 2

节点 Node 类

为了实现无序列表，我们需要构造链表。外部引用通常被称为链表的头。节点（ Node ）是实现链表的基本模块，由数据字段（数据域）和对下一个节点的“引用”（指针域）组成。Node 类包括访问，修改数据和访问下一个引用等常用方法，它的结构如下图所示：

图1 - 节点结构图

Node 类的代码如下：

class Node():
def __init__(self, init_data):
self.data = init_data
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, new_data):
self.data = new_data
def setNext(self, new_next):
self.next = new_next

下面通过一个案例来演示 Node 类的使用：

# 创建一个新的节点，该节点保存的初始数据为 2020
temp = Node(2020)
# 通过 getData() 操作得到当前节点保存的数据
temp.getData() # 返回值为 2020
# 通过 setData() 操作，可以修改当前节点保存的数据
temp.setData(520)
# 再次获取当前节点保存的数据
temp.getData() # 返回值为 520

编程要求

在右侧编辑器 Begin - End 之间补充代码，构建无序列表。具体要求如下：

实现add()函数，依次将“第一行输入数据”添加到无序列表中；
实现search()函数和remove()函数，在列表中搜索“第二行输入的元素”，并输出搜索结果（True or False）；若当前列表中存在该元素，则删除该元素；
实现size()函数，输出列表长度；
实现print_data()函数，依次打印列表内各元素。

测试说明

平台会对你编写的代码进行测试：

测试输入：

1 2 3 4 5
1

输入说明：第一行输入：数据；第二行输入：搜索元素，若存在，则删除此元素。

预期输出：

True
4
5 4 3 2

输出说明：第一行输出：搜索结果；第二行输出：列表长度；第三行输出：列表内元素。

开始你的任务吧，祝你成功！

# -*- coding: utf-8 -*-

class Node():
    def __init__(self, init_data):
        self.data = init_data
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, new_data):
        self.data = new_data

    def setNext(self, new_next):
        self.next = new_next


'''请在Begin-End之间补充代码, 完成 UnorderedList 类'''


class UnorderedList():
    # 初始化列表
    def __init__(self):
        self.head = None

    # 判断队列是否为空
    def isEmpty(self):
        return self.head == None

    # 添加元素item
    def add(self, item):
        # ********** Begin ********** #
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
        # ********** End ********** #

    # 返回列表长度
    def size(self):

    # ********** Begin ********** #
        p=self.head
        cnt=0
        while p:
            cnt+=1
            p=p.next
        return cnt

    # ********** End ********** #
    # 查询列表内是否存在item，查询结果：True or False
    def search(self, item):

    # ********** Begin ********** #
        j=0
        p=self.head.next
        while p is not None and p.data!=item:
            j+=1
            p=p.next
        if p is None:
            return False
        else:
            return True
    # ********** End ********** #
    # 删除item元素
    def remove(self, item):

    # ********** Begin ********** #
        assert self.search(item)
        index=self.head
        p=None
        flag=False
        while not flag:
            if index.getData()==item:
                flag=True
            else:
                p=index
                index=index.getNext()
        if p==None:
            self.head=index.getNext()
        else:
            p.setNext(index.getNext())


    # ********** End ********** #
    # 打印列表内全部元素
    def print_data(self):
# ********** Begin ********** #
        index=self.head
        while index:
            print(index.getData(),end=' ')
            index=index.getNext()
# ********** End ********** #
          
if __name__ == "__main__":
    # 读取数据
    line1 = list(map(int, input().split()))
    line2 = int(input())
    
    ulist = UnorderedList()
    # 将数据依次压入
    for i in line1: 
        ulist.add(i)
    # 输出搜索结果
    print(ulist.search(line2)) 
    # 判定是否存在元素，若存在，则删除该元素
    if ulist.search(line2):
        ulist.remove(line2) 
    # 输出列表长度
    print(ulist.size()) 
    # 输出列表数据
    ulist.print_data()

第2关：有序列表的链表实现

任务描述
相关知识
- 有序列表抽象数据类型
- 节点 Node 类
编程要求
测试说明

任务描述

本关任务：编写程序基于链表实现有序列表。

相关知识

为了完成本关任务，你需要掌握：

有序列表抽象数据类型；
节点 Node 类。

有序列表抽象数据类型

上一关我们学习了无序列表的抽象数据类型，本关我们将主要介绍有序列表。

有序列表是一个拥有特定顺序的列表项的集合，其特点为数据的排列具有顺序性。换言之，有序表的数据项依照其某可比性质（如整数大小、字母表先后）来决定其在列表中的位置。越“小”的数据项越靠近列表的头，越靠“前”。

有序表 List 的操作如下：

List()：创建一个新的空列表。它不需要参数，并返回一个空列表。
add(item)：向列表中添加一个新项。它需要 item 作为参数，并不返回任何内容（假定该 item 不在列表中）。
remove(item)：从列表中删除该项。它需要 item 作为参数并修改列表（假设项存在于列表中）。
search(item)：搜索列表中的项目。它需要 item 作为参数，并返回一个布尔值。
isEmpty()：检查列表是否为空。它不需要参数，并返回布尔值。
size())：返回列表中的项数。它不需要参数，并返回一个整数。
index(item)：返回项在列表中的位置。它需要 item 作为参数并返回索引（假定该项在列表中）。
pop()：删除并返回列表中的最后一个项（假设该列表至少有一个项）。
pop(pos)：删除并返回位置 pos 处的项。它需要 pos 作为参数并返回项（假定该项在列表中）。

下面通过一个案例来演示有序列表的使用：

# 创建一个新的有序列表
olist = List()
# 通过 isEmpty() 函数检验列表是否为空
olist.isEmpty() # 返回值为 True
通过 add() 向列表内添加三个元素
olist.add(2020)
olist.add(3)
olist.add(26)
# 此时，列表中元素为：3 26 2020
# 通过 search() 操作判断列表内是否存在某元素
olist.search(26) # 返回值为 True
# 通过 remove() 操作删除该项
olist.remove(26)
# 此时，列表中元素为：3 2020
# 通过 size() 函数统计列表的项目数
olist.size() # 返回值为 2

节点 Node 类

节点 Node 类的相关知识参加第一关。

编程要求

在右侧编辑器 Begin - End 之间补充代码，构建有序列表。具体要求如下：

实现add()函数，依次将“第一行输入数据”添加到有序列表中；
实现search()函数和remove()函数，在列表中搜索“第二行输入的元素”，并输出搜索结果（ True or False ）；若当前列表中存在该元素，则删除该元素；
实现size()函数，输出列表长度；
实现print_data()函数，依次打印列表内各元素。

测试说明

平台会对你编写的代码进行测试：

测试输入：

1 5 3 4 2
1

输入说明：第一行输入：数据；第二行输入：搜索元素，若存在，则删除此元素。

预期输出：

True
4
2 3 4 5

输出说明：第一行输出：搜索结果；第二行输出：列表长度；第三行输出：列表内元素。

开始你的任务吧，祝你成功！

# -*- coding: utf-8 -*-
class Node():
    def __init__(self, init_data):
        self.data = init_data
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, new_data):
        self.data = new_data

    def setNext(self, new_next):
        self.next = new_next


'''请在Begin-End之间补充代码, 完成 OrderedList 类'''


class OrderedList:
    # 初始化列表
    def __init__(self):
        self.head = None

    # 判断队列是否为空
    def isEmpty(self):
        return self.head == None

    # 添加元素item
    def add(self, item):
    # ********** Begin ********** #
        index=self.head #指针
        p=None # 指针前
        flag=None
        '''
        在插值之前，
        如果原来有比item大的值，找到比item大的第一个对象在其之前插入，
        如果原来的值都比item小，遍历到最后一个对象插入
        '''
        while index!=None and not flag:
            #找到比item大的第一个元素就中止循环
            if index.getData()>item:
                flag=True
            else:
                p=index
                index=index.getNext()
        # 插入元素
        t=Node(item)
        if p is None:# 在已有最大值后插入
            t.setNext(self.head)
            self.head=t
        else:# 在第一个比item大的值前插入
            t.setNext(index)
            p.setNext(t)

    # ********** End ********** #
    # 返回列表长度
    def size(self):

    # ********** Begin ********** #
        index=self.head #初始指针指向头结点
        cnt=0
        while index is not None:#遍历到最后一个Node对象
            cnt+=1
            index=index.getNext()
        return cnt
    # ********** End ********** #
    # 查询列表内是否存在item，查询结果：True or False
    def search(self, item):

    # ********** Begin ********** #
        index=self.head
        flag=False #默认找不到的flag标记为False
        while index!=None and not flag :
            if index.getData()==item:
                flag=True #找到item更改flag为True
                break
            else:
                if index.getData()>item:
                    return flag
                    #已经遍历到大于item的值但是没找到item，直接返回False
                else:
                    index=index.getNext()
        return flag
    # ********** End ********** #
    # 删除item元素
    def remove(self, item):

    # ********** Begin ********** #
        assert self.search(item) and not self.isEmpty()
        index=self.head
        p=None
        flag=False
        while index!=None and not flag:
            # 指针遍历所有元素直至找到item
            if index.getData()==item:
                flag=True
            else:
                p=index
                index=index.getNext()

            if p==None:
                self.head=index.getNext()
            else:
                p.setNext(index.getNext())

    # ********** End ********** #
    # 打印列表内全部元素
    def print_data(self):


# ********** Begin ********** #
        index=self.head
        while index!=None:#遍历所有对象输出
            print(index.getData(),end=' ')
            index=index.next

# ********** End ********** #
if __name__ == "__main__":
    # 读取数据
    line1 = list(map(int, input().split()))
    line2 = int(input())

    olist = OrderedList()
    # 将数据依次压入
    for i in line1:
        olist.add(i)
    # 输出搜索结果
    print(olist.search(line2))
    # 判定是否存在元素，若存在，则删除该元素
    if olist.search(line2):
        olist.remove(line2)
        # 输出列表长度
    print(olist.size())
    # 输出列表数据
    olist.print_data()

第1关：结点链接法实现二

任务描述
相关知识
- 树的基本概念
- 二叉树的基本概念
- 二叉树结点的链式存储
编程要求
测试说明

任务描述

本关任务：编写代码实现二叉树的链式结构。

相关知识

为了完成本关任务，你需要掌握：1.树的基本概念，2.二叉树的基本概念，3.二叉树结点的链式存储。

树的基本概念

如图1所示就是一棵树，它是若干结点的集合，是由唯一的根（ A 结点）和若干棵互不相交的子树组成。其中每一棵子树又是一棵树，也是由唯一的根结点和若干棵互不相交的子树组成。当树的结点数为 0 时，这棵树称为一棵空树。结点的度是结点拥有的子树个数或者分支的个数。度为 0 的结点为叶子结点，如图中的 F 、J 、L 、K 、O 、P 结点。结点的子树的根为该结点的孩子，如图中 A 结点的孩子为 B、 C。同时，A 结点也称为 B 、C 结点的双亲。

图1 - 树

二叉树的基本概念

二叉树是在树的基础上加上如下两个限制条件：

每个结点最多只有两棵子树，即二叉树中结点的度只能为 0 、1 、2 ；
子树有左右之分，不能颠倒。

根据二叉树的定义，可以知道二叉树共有 5 种基本的形态，如下面图2所示。

图2 - 二叉树的 5 种基本形态

（1）空二叉树（2）只有根结点（3）只有左子树，右子树为空（4）只有右子树，左子树为空（5）既有左子树，又有右子树

二叉树结点的链式存储

二叉树中的每个结点用一个链结点来存放。每个链结点保存该结点的数据项，以及指向左右子树的链接。结点结构如图3所示。

图3 - 二叉树的结点结构

定义 BinaryTree 类，初始化根结点数据项以及指向左右子树的链接。示例如下：

class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj # 成员key保存根结点数据项
self.leftChild = None # 成员leftChild保存指向左子树的引用
self.rightChild = None # 成员rightChild保存指向右子树的引用

当我们插入一个新的左子结点到树中时：

若根结点的左子树为 None ，我们需要创建另一个 BinaryTree 的实例，并修改根结点的self.leftChild使之指向新的树。示例如下：
1. self.leftChild = BinaryTree(newNode)
若根结点的左子树不为 None ，我们将原来根的左子树作为新结点的左子树，并且也修改根结点的self.leftChild使之指向新的树。示例如下：
1. t = BinaryTree(newNode) # 创建一个BinaryTree类型的新结点t
2. t.leftChild = self.leftChild
3. self.leftChild = t

编程要求

在右侧编辑器中的 Begin-End 区间补充代码，参考 BinaryTree 类中的__init__、insertLeft方法，补充insertRight、setRootVal、getRightChild、getLeftChild和getRootVal方法。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确的数值，只有所有数据全部计算正确才能通过测试：

测试输入：a,b,c 预期输出：

a
b
c
a
b
hello

输入说明：后台将接收输入字符串，该字符串中以逗号分隔的字符为创建二叉树的结点。我们对二叉树中的结点按照从上到下、从左到右的顺序编号。根据输入结点a、b、c，按编号顺序创建二叉树，创建的过程如下：

创建结点 a；
将 b 插入到 a 的左子树；
将 c 插入到 a 的右子树。

输出说明：前三行输出：对创建的二叉树按编号顺序输出结点。后三行输出：代码最后利用setRootVal方法将根结点的右孩子的值设为 hello。在修改根结点的右孩子的值为 hello 后，对修改后新的二叉树按编号顺序输出结点。

创建的二叉树如下面图4所示。

图4 - 测试案例创建的二叉树

开始你的任务吧，祝你成功！

# -*- coding: utf-8 -*-

'''请在Begin-End之间补充代码, 完成BinaryTree类'''


class BinaryTree:
    # 创建左右子树为空的根结点
    def __init__(self, rootObj):
        self.key = rootObj  # 成员key保存根结点数据项
        self.leftChild = None  # 成员leftChild初始化为空
        self.rightChild = None  # 成员rightChild初始化为空

    # 把newNode插入到根的左子树
    def insertLeft(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)  # 左子树指向由newNode所生成的BinaryTree
        else:
            t = BinaryTree(newNode)  # 创建一个BinaryTree类型的新结点t
            t.leftChild = self.leftChild  # 新结点的左子树指向原来根的左子树
            self.leftChild = t  # 根结点的左子树指向结点t

    # 把newNode插入到根的右子树
    def insertRight(self, newNode):
        if self.rightChild == None:
        # 右子树指向由newNode所生成的BinaryTree
        # ********** Begin ********** #
            self.rightChild=BinaryTree(newNode)


        # ********** End ********** #
        else:
    # 创建新结点，并将其右子树指向原来根的右子树
    # 将根结点的右子树指向新结点
    # ********** Begin ********** #
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t
    # ********** End ********** #

    # 取得右子树,返回值是一个BinaryTree类型的对象
    def getRightChild(self):

    # ********** Begin ********** #
        assert  not self.rightChild==None
        return self.rightChild
    # ********** End ********** #

    # 取得左子树
    def getLeftChild(self):

    # ********** Begin ********** #
        assert not self.leftChild==None
        return self.leftChild

    # ********** End ********** #

    # 设置根结点的值
    def setRootVal(self, obj):

    # 将根结点的值赋值为obj
    # ********** Begin ********** #
        self.key=obj
        self.rightChild='Hello'
    # ********** End ********** #

    # 取得根结点的值
    def getRootVal(self):
# ********** Begin ********** #
        return self.key
# ********** End ********** #

第2关：建立特定的二叉链表

任务描述
相关知识
- 如何插入新结点
编程要求
测试说明

任务描述

本关任务：按特定要求编写代码建立二叉树的链表结构。

相关知识

为了完成本关任务，你需要掌握：如何插入新结点。

如何插入新结点

二叉链表的结点结构如图1所示：

图1 - 二叉链表的结点结构

在创建了根结点后，为了添加左子结点，我们将创建一个新的二叉树对象，并设置根的 left 属性指向这个新对象。我们必须考虑以下两种情况进行插入：

根没有左子结点。当没有左子结点时，简单地将新结点添加到树中即可。
根有左子结点。此时，我们插入一个结点并将已存在的子结点降级。

对于添加右子结点，同样也是这样。根结点的左右子结点本身就是 BinaryTree 类的不同实例。正如我们在树的原始递归定义中所说的，这使我们能够把一个二叉树的任何子结点当成二叉树本身。所以我们可通过定义一个 BinaryTree 类实例来创建一个根结点，然后通过调用insertLeft()或insertRight()方法对其插入左右子结点。根结点的左右子结点的左右子树也可按照此方法进行添加。示例如下：

r = BinaryTree('a')
r.insertLeft('b')

编程要求

在右侧编辑器中的 Begin-End 区间补充代码，利用结点链接法生成如下图2所示的二叉树。需要实现的操作如下：

创建根结点 a；
将 b 插入到 a 的左子树；
将 c 插入到 a 的右子树；
将 d 插入到 a 的左子树的右子树；
将 e 插入到 a 的右子树的左子树；
将 f 插入到 a 的右子树的右子树。

图2 - 要求实现的二叉树

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确的数值，只有所有数据全部计算正确才能通过测试：

预期输出：

输出说明：输出为这棵树的中序遍历结果。

开始你的任务吧，祝你成功！


'''请在Begin-End之间补充代码, 完成相应二叉树的构建'''
class BinaryTree:
    # 创建左右子树为空的根结点
    def __init__(self,rootObj):
        self.key = rootObj  # 成员key保存根结点数据项
        self.leftChild = None # 成员leftChild初始化为空
        self.rightChild = None # 成员rightChild初始化为空

    # 把newNode插入到根的左子树
    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode) # 左子树指向由newNode所生成的BinaryTree
        else:
            t = BinaryTree(newNode) # 创建一个BinaryTree类型的新结点t
            t.leftChild = self.leftChild # 新结点的左子树指向原来根的左子树
            self.leftChild = t # 根结点的左子树指向结点t

    # 把newNode插入到根的右子树
    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode) # 右子树指向由newNode所生成的BinaryTree
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild # 新结点的右子树指向原来根的右子树
            self.rightChild = t

    # 取得右子树
    def getRightChild(self):
        return self.rightChild  # 返回值是一个BinaryTree类型的对象

    # 取得左子树
    def getLeftChild(self):
        return self.leftChild

    # 设置根结点的值
    def setRootVal(self,obj):
        self.key = obj

    # 取得根结点的值
    def getRootVal(self):
        return self.key

r = BinaryTree('a') 
# ********** Begin ********** #
r.insertLeft('b')
r.insertRight('c')
# p1=BinaryTree('d')
# p2=BinaryTree('e')
# p3=BinaryTree('f')
r.leftChild.insertRight('d')
r.rightChild.insertLeft('e')
r.rightChild.insertRight('f')
def _InOrder(t):
    if t!=None:
        _InOrder(t.leftChild)
        print(t.key)
        _InOrder(t.rightChild)
def InOrder(tree):
    _InOrder(tree)


# ********** End ********** #

第1关：表达式解析树的建立

相关知识
- 表达式树的基本概念
- 构造表达式解析树
编程要求
测试说明

任务描述

本关任务：编写代码实现表达式解析树的建立。

相关知识

为了完成本关任务，你需要掌握：1.表达式树的基本概念，2.构造表达式解析树。

表达式树的基本概念

为了处理表达式而遵循相应规则构造的树被称为表达式树。表达式树的结构如图1所示，它的叶结点保存操作数，内部结点保存操作符。在表达式树中，表达式层次决定计算的优先级，越底层的表达式，优先级越高，树根是最后被计算的。对于下图所表示的表达式((7+3)*(5-2))，需要计算*的话就先要计算7+3和5-2。

图1 - 表达式树的结构

构造表达式解析树

全括号表达式中的单词分为括号()、操作符+-*/和操作数0~9这几类。左括号是表达式的开始，而右括号是表达式的结束。下面以表达式(3+(4*5))为例，构造表达式的步骤如下：

创建单词表

对于表达式(3+(4*5))可在代码中可通过split()方法创建单词表。split()函数语法：

str.split(str="", num=string.count(str))

参数：

str：分隔符，默认为所有的空字符，包括空格、换行（\n）、制表符（\t）等。
num：分割次数。默认为 -1, 即分隔所有。

返回值：分割后的字符串列表。

我们使用split()以空字符为分隔符对表达式创建单词表，所以表达式字符串中的字符以空字符进行隔开。示例如下：

pt = "( 3 + ( 4 * 5 ) )"
ptlist = pt.split() # split()通过指定分隔符对字符串进行切片
print(ptlist)

输出：['(', '3', '+', '(', '4', '*', '5', ')', ')']

创建空树

首先用 BinaryTree 类创建一个空的二叉树对象。同时为了成功构建表达式解析树，我们需要利用pStack.push入栈操作把刚建立的结点入栈。最后把当前结点设置成此时建立的结点。创建结果如图2所示，代码示例如下：

eTree = BinaryTree('') # BinaryTree()为上一次实训中详细讲过的方法
pStack.push(eTree)
currentTree = eTree # 当前结点为根结点

图2 - 创建空树

读入'('为第一个字符。创建一个新的结点作为当前节点的左子结点,并将当前结点变为这个新的子结点。实现结果如图3所示。

图3 - 创建根结点的左子结点

读入'3'为下一个字符。将当前结点的值赋值为3，然后返回当前结点的父结点。实现结果如图4所示。

图4 - 当前结点赋值为 3

读入'+'为下一个字符。将当前结点的值赋值为+，然后添加一个新的结点作为其右子结点，并且将当前结点变为这个新的子结点。实现结果如图5所示。

图5 - 根结点赋值为 +，创建右子结点作为当前结点

读入'('为下一个字符。创建一个新的结点作为当前结点的左子结点，并将当前结点变为这个新的子结点。实现结果如图6所示。

图6 - 创建左子结点作为当前结点

读入'4'为下一个字符。将当前结点的值赋值为4，然后返回到当前结点的父结点。实现结果如图7所示。

图7 - 结点赋值为 4，其父结点作为当前结点

读入'*'为下一个字符。将当前结点的值赋值为*，然后添加一个新的结点作为其右子结点,并且将当前结点变为这个新的子结点。实现结果如图8所示。

图8 - 结点赋值为 *，创建右子结点作为当前结点

读入'5'为下一个字符。将当前结点的值赋值为5，然后返回到当前结点的父结点。实现结果如图9所示。

图9 - 结点赋值为 5，其父结点作为当前结点

读入')'作为下一个字符。将当前结点变为当前结点*的父结点。
读入')'作为下一个字符。将当前结点变为当前结点+的父结点，然而当前结点没有父结点，所以我们完成了解析树的构建。

在第 3、 5、 6、 8 步，即读入字符为'('或操作符时，需要执行当前结点下降的操作，在此之前需要进行入栈操作，来保证之后执行上升操作时能知道返回到哪里。示例如下（下降到左子结点的情况）：

pStack = Stack() # Stack()为定义好的栈方法
currentTree.insertLeft('') # 创建一个当前结点的左子结点
pStack.push(currentTree) # 将当前结点入栈
currentTree = currentTree.getLeftChild() # 将当前结点下降到左子结点

在第 4、 7、 9、 10、 11 步，即读入字符为操作数或')'时，需要执行当前结点上升的操作，需要通过出栈来得到返回的结点。示例如下：

pStack = Stack() # Stack()为定义好的栈方法
parent = pStack.pop() # 出栈一个结点作为当前结点的父结点
currentTree = parent # 将当前结点上升到父结点

编程要求

在右侧编辑器中的 Begin-End 区间补充代码，通过扫描表达式单词表中的单词，判断该单词是左括号、操作数、操作符还是右括号，并实现不同判断结果对应的操作，以此正确构建表达式解析树。为了检查表达式解析树的构建是否正确，后台会通过input()接收一个表达式字符串，调用定义的printexp()函数，输出对应表达式解析树的内容。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确的数值，只有所有数据全部计算正确才能通过测试：测试输入：( ( 7 + 4 ) * 9 )

预期输出：( ( 7 + 4 ) * 9 )

开始你的任务吧，祝你成功！

from stack import Stack
from binaryTree import BinaryTree

'''请在Begin-End之间补充代码, 完成表达式解析树的建立'''
# 创建表达式解析树
def buildParseTree(fpexp):
    fplist = fpexp.split()
    pStack = Stack()  # 存储树结点的栈
    eTree = BinaryTree('')  # 创建一个空的二叉树
    pStack.push(eTree)  # 把刚建立的结点入栈，该结点将最后出栈
    currentTree = eTree  # 把当前结点设成刚才建立的结点
    for i in fplist:  # 对每个单词进行从左到右扫描
        # 表达式开始
        if i == '(':
        # 创建一个当前结点的左孩子结点
        # 将当前结点入栈，这样等下上升的时候才知道返回到哪里
        # 将当前结点下降到左孩子结点
        # ********** Begin ********** #
            currentTree.insertLeft('')
            pStack.push(currentTree)
            currentTree=currentTree.getLeftChild()

        # ********** End ********** #
        # 操作数
        elif i not in ['+', '-', '*', '/', ')']:
        # 将当前结点的根值设置成把i转化为整数后的结果
        # 出栈一个结点作为当前结点的父结点
        # 将当前结点上升到 父结点
        # ********** Begin ********** #
            currentTree.key=int(i)
            parent=pStack.pop()
            currentTree=parent

        # ********** End ********** #
        # 操作符
        elif i in ['+', '-', '*', '/']:
        # 将当前结点的根值设置成操作符i
        # 创建一个当前结点的右孩子结点
        # 将当前结点入栈
        # 将当前结点下降到右孩子结点
        # ********** Begin ********** #
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree=currentTree.getRightChild()

        # ********** End ********** #
        # 表达式结束
        elif i == ')':
        # 出栈上升，返回到父结点
        # ********** Begin ********** #
            parent=pStack.pop()
            currentTree=parent
        # ********** End ********** #
        else:
            raise ValueError
    return eTree


pt = buildParseTree(input())  # 一个字符串表达的全括号表达式

第2关：利用表达式解析树求值

任务描述
相关知识
- 利用表达式解析树求值
- Python 中的内置模块 operator
- Python 中的字典
编程要求
测试说明

任务描述

本关任务：编写代码利用表达式解析树对表达式进行求值，并返回该计算结果。

相关知识

为了完成本关任务，你需要掌握：1.利用表达式解析树求值，2.Python 中的内置模块 operator，3.Python 中的字典。

利用表达式解析树求值

表达式解析树中每一个子树都表示一个子表达式。我们可以利用树的分层结构，将子树替换为子表达式的结点，即可实现求值。如图1所示，我们将原始的树替换成了化简后的树。所以根据此思想可以写一个能够通过计算每个子树的值从而算出整个解析树值的递归算法。

图1 - 表达式解析树的化简

在表达式解析树中，越靠近操作数的底层子表达式树是越先计算的，所以递归算法是从树的底层子树开始，逐步向上层求值，最终得到整个表达式的值。在求值过程中，从根结点开始，调用求值函数计算当前结点左子树和右子树的值，然后将左右子树的值依根结点的操作符进行计算。虽然树根是最先访问的，但是树根是最后计算的。叶结点是最简单的子树，没有左右子结点，同时叶结点始终是操作数，所以叶结点的值就是以该叶结点为根的子树的子表达式的值，这个递归算法的最小基本问题是检查当前结点是否为叶结点，若是则直接返回叶结点中操作数的值。

Python 中的内置模块 operator

operator 模块包括一系列对应 Python 内部操作符的函数。以下为加减乘除操作的示例：

import operator
op1 = operator.add # 加法
op2 = operator.sub # 减法
op3 = operator.mul # 乘法
op4 = operator.truediv # 除法（真除）
n1 = op1(6,2)
n2 = op2(6,2)
n3 = op3(6,2)
n4 = op4(6,2)
print(n1,n2,n3,n4)

输出：8 4 12 3.0

Python 中的字典

Python 内置了字典（dictionary）。字典是一种通过名字或者关键字引用的数据结构，其键可以是数字、字符串、元组，这种结构类型也称之为映射。键在字典中是唯一的，而值可以不必唯一。每个键与其值使用一个冒号:分开，这些键-值对使用逗号分隔，整个字典项目用大括号括起来。没有任何项目的空字典只用两个花括号写成：{}。

字典具有极快的查找速度，为了实现表达式求值算法，可构建键值分别为'+','-','*'和'/'的字典。当我们在字典中查找一个操作符时，相应的函数功能会被取回。示例如下：

import operator
opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv} # 定义字典
fn = opers['+'] # fn表示为operator.add功能
print(fn(4,5))

输出：9

编程要求

在右侧编辑器中的 Begin-End 区间补充代码，完成evaluate()函数，计算并输出表达式解析树的表达式值。表达式解析树由input()输入的全括号表达式所构建。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确的数值，只有所有数据全部计算正确才能通过测试：

测试输入：( ( 7 + 4 ) * 9 ) 预期输出：99

测试输入：( 5 + ( 6 - 3 ) ) 预期输出：8

开始你的任务吧，祝你成功！

import operator
from parsetree import buildParseTree

'''请在Begin-End之间补充代码, 完成evaluate()'''
def evaluate(parseTree):
    opers = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv}
    # 取得左右子树，实现缩小规模
    # ********** Begin ********** #
    leftC=parseTree.leftChild
    rightC=parseTree.rightChild
    # ********** End ********** #
    # 如果存在左右子树就进行递归调用
    if leftC and rightC:
        fn = opers[parseTree.getRootVal()]  # fn翻译成根结点操作符中对应的操作
        # 返回递归调用求得的结果
        # ********** Begin ********** #
        return fn(evaluate(leftC),evaluate(rightC))
        # ********** End ********** #
    # 如果不存在左右子树就走到了叶结点，达到了基本结束条件，直接返回结点的值
    else:
# ********** Begin ********** #
        return parseTree.key
# ********** End ********** #



pt = buildParseTree(input())

第3关：前中后缀表达式

任务描述
相关知识
- 前中后缀表达式的基本概念
  - 中缀表达式
  - 前缀表达式
  - 后缀表达式
- 通过表达式解析树输出前中后缀表达式
编程要求
测试说明

任务描述

本关任务：编写代码通过构建的表达式解析树输出对应的前缀、后缀表达式。

相关知识

为了完成本关任务，你需要掌握：1.前中后缀表达式的基本概念，2.通过表达式解析树输出前中后缀表达式。

前中后缀表达式的基本概念

中缀表达式

中缀表达式是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间，例如3+4。

在中缀表达式中，运算符有不同的优先级，圆括号用于改变运算顺序，这使得运算规则比较复杂，求值过程不能直接从左到右顺序进行，不利于计算机处理。

前缀表达式

将操作符写在前面，操作数写在后面的算术表达式。后缀表达式中没有括号，并且运算符没有优先级，严格按照从右到左的顺序计算。例如表达式1-(2+3)的前缀表达式是- 1 + 2 3。

后缀表达式

将操作符写在两个操作数后面的算术表达式。和前缀表达式一样，后缀表达式没有括号，运算符没有优先级。后缀表达式的求值过程能够严格按照从左到右的顺序进行，有利于计算机处理。如表达式1-(2+3)的后缀表达式是1 2 3 + -。

通过表达式解析树输出前中后缀表达式

给定一个表达式的中缀形式：(7+4)*9，最外层括号中的*优先级最低，作为根结点，(7+4)作为左子树，9作为右子树；然后对于以*为根的左子树(7+4)，+最为根结点，7是左子树，4是右子树。构建的表达式解析树如图1所示。

图1 - 表达式 (7+4)*9 对应的表达式解析树

我们可以通过递归函数来处理整个表达式，从根结点开始，通过取得操作符和两个操作对象的不同顺序来得到相应的前、中、后缀表达式。然后递归地处理其他的子表达式。

前缀表达式：取得优先级最低的根结点中的*,按照顺序之后应该取得其左右子树。对于其左子树，先取得操作符+，然后是两个操作数7、4。最后取得以*为根的右子树9。最终得到的式子为* + 7 4 9 后缀表达式：对于以*为根的树，先取得其左右子树，将操作符放最后。在其左子树中，先取得两个操作数7、4，然后是操作符+。最后取得以*为根的右子树9和操作符*。最终得到的式子为7 4 + 9 *

编程要求

在右侧编辑器中的 Begin-End 区间补充代码，完成prefix()和suffix()函数，正确输出表达式解析树对应的前缀和后缀表达式，表达式解析树由input()输入的全括号表达式所构建。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确的数值，只有所有数据全部计算正确才能通过测试：

测试输入：( ( 7 + 4 ) * 9 ) 预期输出：

前缀表达式: * + 7 4 9
后缀表达式: 7 4 + 9 *

测试输入：( ( 4 * ( 5 - 2 ) ) / ( 6 - 3 ) ) 预期输出：

前缀表达式: / * 4 - 5 2 - 6 3
后缀表达式: 4 5 2 - * 6 3 - /

开始你的任务吧，祝你成功！文章来源地址https://www.toymoban.com/news/detail-725946.html

from parsetree import buildParseTree

'''请在Begin-End之间补充代码, 完成prefix()和suffix()'''
# 前缀表达式
def prefix(parseTree):
    # 一个递归的过程中：先根结点，然后左子树和右子树
    print(parseTree.key, end=' ')
    if parseTree.leftChild:
    # 递归调用该函数打印出左子树的前缀表达式
    # ********** Begin ********** #
        prefix(parseTree.leftChild)
    # ********** End ********** #
    if parseTree.rightChild:
# 递归调用该函数打印出右子树的前缀表达式
# ********** Begin ********** #
        prefix(parseTree.rightChild)
# ********** End ********** #

# 后缀表达式
def suffix(parseTree):
# 一个递归的过程中：先左子树，再右子树，最后根结点
# ********** Begin ********** #
    if parseTree.leftChild or parseTree.rightChild:
        suffix(parseTree.leftChild)
        suffix(parseTree.rightChild)
    print(parseTree.key,end=' ')
# ********** End ********** #
pt = buildParseTree(input())

到了这里，关于头歌实践平台（python数据结构）(1-6)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！