课件下载

描述

在本题中，同学们需要根据课堂中学到的内容，完成以下要求：

1. 根据题目给出的表达式，构造一颗树，并以列表的形式输出。保证表达式合法。
2. 根据题目给出的表达式，输出它的逆波兰表达式。保证表达式合法。
3. 根据题目给出的中序遍历与后序遍历，推导出原树并以列表的形式输出。保证一定能推导出原树。

以上要求并不保证按照难度顺序排列。如果你在实现过程中遇到困难，可以先去完成其他要求。(例如，$q=2$最简单，先只考虑$q=2$的情况)

输入格式

第一行一个正整数 $q$ 表示进行第 $q$ 项询问。询问编号见描述。

如果 $q=1$ 或者 $q=2$, 第二行会输入一个表达式。

如果 $q=3$, 第二行会以列表的形式输入一棵树的中序遍历，第三行会以列表的形式输入一棵树的后序遍历。保证原树的每个节点均以一个字符为节点数据。

输出格式

如果 $q=1$ 或 $q=3$, 输出一个Python的列表，这个列表表示一棵树。

如果 $q=2$, 输出一个逆波兰表达式，并用英文逗号分隔每个数字或运算符。

输入样例

输入数据1

1
3-3^2*2

输出数据1

['-', ['3', [], []], ['*', ['^', ['3', [], []], ['2', [], []]], ['2', [], []]]]

输入数据2

2
1+2*3-4

输出数据2

1,2,3,*,+,4,-

输入数据3

3
['b', 'e', 'd', 'a', 'f', 'c']
['e', 'd', 'b', 'c', 'f', 'a']

输出数据3

['a', ['b', [], ['d', ['e', [], []], []]], ['f', [], ['c', [], []]]]

测试点描述

测试点编号	q	说明
#0	1	所有运算符均为+与-
#1		不存在括号(与)
#2		无特殊说明
#3	2	所有运算符均为+与-
#4		不存在括号(与)
#5		无特殊说明
#6	3	样例数据3
#7		中序与后序遍历长度小于等于100
#8		中序与后序遍历长度小于等于1000
#9		中序与后序遍历长度小于等于10000

此外，对于以上所有测试点，当输入内容为一个表达式时，保证所有数字都是个位数。且当q相同时，测试点较小的编号将会同时满足测试点较大的编号的说明。例如，#0测试点将会同时满足#1与#2测试点的要求。

特别的，在每一个表达式中，我们使用^代替python中的**来表示幂次运算。

提示

你可以用列表表示法来表示如上图所示的一颗树，例如：

tree = ['+', ['-', ['*', ['1', [], []], ['2', [], []]], ['3', [], []]], ['4', [], []]]

在这个树tree中，每个节点都是一个列表。tree的第一个元素tree[0]是根节点的值"+"，第二个元素tree[1]是根节点的左子树， 第三个元素tree[2]是根节点的右子树。以此类推，tree[1][0]是根节点的左子节点的值"-"，tree[1][1]是根节点的左子节点的左子树，tree[1][2]是根节点的左子节点的右子树。特别的，当列表为空时，即代表不存在这个节点。 题目也会要求以列表表示法输出一棵树。

如果有疑惑，可以通过以下方式联系题目作者：

1. 邮箱：zhanghr2022@shanghaitech.edu.cn
2. QQ: 1546169856

你可以在以下Python代码框架的基础上修改并实现你的功能

def expr_to_tree(expr):
    """将表达式转换为树"""
    """你的代码"""
    
    return ['test list']

def expr_to_postfix(expr):
    """将表达式转换为逆波兰表达式"""
    """你的代码"""
    
    return 'test str'

def inorder_postorder_to_tree(inorder, postorder):
    """通过中序遍历与后序遍历，还原并以列表表示法输出这颗树"""
    """你的代码"""
    
    return ['test list']

q=int(input())

#以列表表示法输出一颗树
#输入：一个表达式
if q == 1:
    expr = input()
    tree = expr_to_tree(expr)
    
    #tree的类型应当为list
    assert type(tree) is list
    print(tree)

#输出表达式的逆波兰表达式
#输入：一个表达式
elif q == 2:
    expr = input()
    postfix = expr_to_postfix(expr)
    
    #postfix的类型应当为str
    assert type(postfix) is str
    print(postfix)
    

#通过中序遍历与后序遍历，还原并以列表表示法输出这颗树
#输入：中序遍历与后序遍历
elif q == 3:
    inorder = eval(input())
    postorder = eval(input())
    tree = inorder_postorder_to_tree(inorder, postorder)
    
    #tree的类型应当为list
    assert type(tree) is list
    print(tree)

STD

inited:bool = False
def expr_to_tree(expr):
    """将表达式转换为树"""
    flag:bool = False                                                   #flag用于判断是否已经进行过转换。如果已经进行过转换，就不再进行转换。
    ans:list = list(expr)                                               #将expr转换为列表，列表中的每个元素为一个字符，一个数字或一棵树
    global inited                                                       #inited用于判断是否已经进行过转换。如果已经进行过转换，就不再进行转换。
    if inited == False:                                                 #如果还没有进行过转换，就将数字初始化为只有一个根节点的树。
        inited = True
        for i in range(len(ans)):                                       #由于数字在表达式树中是叶子节点，因此将数字初始化为只有一个根节点的树
                if str(ans[i]) in '1234567890':
                    ans = ans[:i] + [[ans[i], [], []]] + ans[i+1:]
    while len(ans) > 1:                                                 #将表达式转换为树。当ans的长度为1时，所有表达式已经转换为树，结束循环。
        flag = False                                                    #每次循环开始时，将flag置为False。
        for i in range(len(ans)):                                       #当ans中存在括号时，先将括号内的表达式转换为树。
            if type(ans[i]) == str:
                if ans[i] == '(':                                       #如果遇到括号，就截取表达式，直到遇到右括号。将截取的表达式作为参数传入expr_to_tree。
                    j = i                                               #从i处的括号开始截取
                    while j < len(ans):                                 #防止越界，j < len(ans)
                        if type(ans[j]) == str:
                            if ans[j] == ')':                           #遇到右括号就停止截取，将截取的表达式转换为树。
                                ans = ans[:i] + [expr_to_tree(ans[i+1:j])] + ans[j+1:]
                                flag = True
                                break
                        j += 1                                          #不是右括号，就继续循环。
                    break
        if flag == False:                                               #如果已经进行过转换，就不再进行转换。
            for i in range(len(ans)):
                if type(ans[i]) == str:
                    if ans[i] in '^':                                   #从优先级最高的幂次运算"^"开始，将表达式转换为树。
                        ans = ans[:i-1] + [[ans[i], ans[i-1], ans[i+1]]] + ans[i+2:]
                        flag = True
                        break
                
        if flag == False:                                               #如果已经进行过转换，就不再进行转换。
            for i in range(len(ans)):
                if type(ans[i]) == str:
                    if ans[i] in '*/':                                  #从优先级次高的乘除运算"*"和"/"开始，将表达式转换为树。
                        ans = ans[:i-1] + [[ans[i], ans[i-1], ans[i+1]]] + ans[i+2:]
                        flag = True
                        break
                    
        if flag == False:                                               #如果已经进行过转换，就不再进行转换。
            for i in range(len(ans)):
                if type(ans[i]) == str:
                    if ans[i] in '+-':                                  #从优先级最低的加减运算"+"和"-"开始，将表达式转换为树。
                        ans = ans[:i-1] + [[ans[i], ans[i-1], ans[i+1]]] + ans[i+2:]
                        flag = True
                        break
    return ans[0]                                                       #当ans的长度为1时，所有表达式已经转换为树，返回ans[0]。
    
    

def expr_to_postfix(expr):
    """将表达式转换为逆波兰表达式"""
    flag:bool = False                                                   #flag用于判断是否已经进行过转换。如果已经进行过转换，就不再进行转换。
    ans:list = list(expr)                                               #将expr转换为列表，列表中的每个元素为一个字符或一个数字
    while len(ans) > 1:                                                 #将表达式转换为逆波兰表达式。当ans的长度为1时，所有表达式已经转换为逆波兰表达式，结束循环。
        flag = False                                                    #每次循环开始时，将flag置为False。
        for i in range(len(ans)):
            if ans[i] == '(':                                           #如果遇到括号，就截取表达式，直到遇到右括号。将截取的表达式作为参数传入expr_to_postfix。
                j = i                                                   #从i处的括号开始截取
                while j < len(ans):                                     #防止越界，j < len(ans)
                    if ans[j] == ')':                                   #遇到右括号就停止截取，将截取的表达式转换为逆波兰表达式。
                        ans = ans[:i] + [expr_to_postfix(ans[i+1:j])] + ans[j+1:]   
                        flag = True
                        break
                    j += 1                                              #不是右括号，就继续循环。
                break
            
        if flag == False:                                               #如果已经进行过转换，就不再进行转换。
            for i in range(len(ans)):
                if ans[i] in '^':                                       #从优先级最高的幂次运算"^"开始，将表达式转换为逆波兰表达式。
                    ans = ans[:i-1] + [ans[i-1] + ',' + ans[i+1] + ',' + ans[i]] + ans[i+2:]
                    flag = True
                    break
                
        if flag == False:                                               #如果已经进行过转换，就不再进行转换。
            for i in range(len(ans)):
                if ans[i] in '*/':                                      #从优先级次高的乘除运算"*"和"/"开始，将表达式转换为逆波兰表达式。
                    ans = ans[:i-1] + [ans[i-1] + ',' + ans[i+1] + ',' + ans[i]] + ans[i+2:]
                    flag = True
                    break
                
        if flag == False:                                               #如果已经进行过转换，就不再进行转换。
            for i in range(len(ans)):
                if ans[i] in '+-':                                      #从优先级最低的加减运算"+"和"-"开始，将表达式转换为逆波兰表达式。
                    ans = ans[:i-1] + [ans[i-1] + ',' + ans[i+1] + ',' + ans[i]] + ans[i+2:]
                    flag = True
                    break
    return ans[0]
        
    

def inorder_postorder_to_tree(inorder, postorder):
    """通过中序遍历与后序遍历，还原树"""
    if inorder == []:
        return []
    root = postorder[-1]                                                #后序遍历的最后一个元素为根节点
    for i in range(len(inorder)):
        if inorder[i] == root:                                          #在中序遍历中找到根节点的位置，将中序遍历与后序遍历分为左子树与右子树
                                                                        #将左子树与右子树分别作为参数传入inorder_postorder_to_tree，递归还原树。
            return [root, inorder_postorder_to_tree(inorder[:i], postorder[:i]), inorder_postorder_to_tree(inorder[i+1:], postorder[i:-1])]
                                                                        #退出循环，说明根节点在中序遍历中的位置为最后一个元素，即根节点没有左子树。
    return [root, inorder_postorder_to_tree(inorder[:-1], postorder[:-1]), []]
    

q=int(input())

#以列表表示法输出一颗树
#输入：一个表达式
if q == 1:
    expr = input()
    tree = expr_to_tree(expr)
    
    #tree的类型应当为list
    assert type(tree) is list
    print(tree)

#输出表达式的逆波兰表达式
#输入：一个表达式
elif q == 2:
    expr = input()
    postfix = expr_to_postfix(expr)
    
    #postfix的类型应当为str
    assert type(postfix) is str
    print(postfix)
    

#通过中序遍历与后序遍历，还原并以列表表示法输出这颗树
#输入：中序遍历与后序遍历
elif q == 3:
    inorder = eval(input())
    postorder = eval(input())
    tree = inorder_postorder_to_tree(inorder, postorder)
    
    #tree的类型应当为list
    assert type(tree) is list
    print(tree)

背景

（以下内容与本题无直接关系）

在课程中，我们学习了表达式树。事实上，树可以应用在很多领域。

例如，同学们将会在数学的概率与统计模块学习到的“树状图”，就是一种利用树这种数据结构来枚举可能状况的方式（你可以向你的数学老师请教更多有关知识^ω^）。此外，在Windows操作系统中，你可以在文件资源管理器的侧边栏里，通过逐层点击文件夹的形式找到你所需要的文件，这也是一种树的应用（在这里，什么相当于树的根？什么相当于树的叶子节点？什么相当于树的中间节点？）。你也可以打开你任意一个科目的教材，翻到目录。目录中有章节，有小节。这样的层次结构同样也体现了树的应用。可以说，树在生活中随处可见。

又：我们在课堂中给出的有关树的定义并不准确。事实上，在学习了有关图的知识后，应当这样定义树：树是一个仅有n个节点与n-1条边的单连通图。通过这个定义，我们便可以认为单个节点也可以构成一棵树，同时可以推导出我们在课堂中给出的定义，即树中的任意两个节点间有且仅有一条路径（试试如何推导？）。

课件下载