# -*- coding:utf-8 -*-
# @Time       :2022/1/29 12:15
# @SOFTWARE   :pythonProject1


# 创建结点类
class Node:
    """
        思路：将自定义的类视为结点类，实例对象中包含数据部分和指向下一个结点的next
    """
    def __init__(self,val,next = None):
        self.val = val #存数据
        self.next = next #寻找下一个结点


class LinkList:
    """
        思路: 单链表类，生成对象可以进行增删改查操作，具体操作可以调用具体方法完成
    """
    def __init__(self):
        """
                初始化链表，标记一个头结点，以便于获取后续结点
        """
        self.head = Node(None)
    # 通过list_为链表添加一组结点
    def init_list(self,list_):
        p = self.head  # p作为移动变量
        for item in list_:
            p.next = Node(item)
            p = p.next

    # 遍历链表
    def showlist(self):
        p = self.head.next
        while p is not None:
            print(p.val)
            p = p.next

    # 判断链表是否为空
    def is_empty(self):
        if self.head.next is None:
            return True
        else:
            return False

    # 清空链表
    def clear(self):
        self.head.next = None

    # 增加结点 : 尾部插入 -> 找到最后一个结点
    def append(self,val):
        p = self.head
        while p.next is not None:
            p = p.next
        p.next = Node(val)

    # 头部插入
    def head_insert(self,val):
        Node(val).next = self.head.next
        self.head.next = Node(val)

    # 指定插入位置
    def insert_(self,index,val):
        p = self.head
        for i in range(index):
            if p.next is None:  # 超出位置最大范围
                break
            p = p.next
        Node(val).next = p.next
        p.next = Node(val)


    # 删除结点 : 按索引删除
    def del_Node_index(self,index):
        p = self.head
        s = self.haed.next
        for i in range(index-1):
            if p.next is None:
                break
            p = p.next
            s = s.next
        p.next = s.next

    # 删除结点： 按值删除
    def del_Node_val(self,key):
        p = self.head
        while p.next and p.next.val != key:
            p = p.next
        if p.next is None:
            raise ValueError(" key not in Linklist")
        else:
            p.next = p.next.next

    # 获取结点：根据索引查结点
    def search(self,index):
        p = self.head.next
        for i in range(index):
            if p.next is None:
                raise IndexError("index out of range")
            p = p.next
        return p.val

# -*- coding:utf-8 -*-
# @Time       :2022/1/30 10:54
# @SOFTWARE   :pythonProject1

from LinkList import *

l1 = LinkList()
l2 = LinkList()

l1.init_list([1,5,7,8,10,12,13,19])
l2.init_list([2,3,4,9,16,17,20])

def merge(l1,l2):
    p = l1.head
    q = l2.head.next
    while p.next is not None:
        if p.next.val > q.val:
            p = p.next
        else:
            tmp = p.next
            p.next = q
            p = p.next
            q = tmp
        p.next = q

# -*- coding:utf-8 -*-
# @Time       :2022/1/30 17:07
# @SOFTWARE   :pythonProject1


"""
顺序栈的实现
    思路：
    1.列表即顺序存储
    2.利用列表将其封装，提供方法和接口
"""

# 自定义异常
class StackError(Exception):
    pass


class sstack:

    # 栈的初始化
    def __init__(self):
        # 空列表就是栈的存储空间
        # 将列表的最后一个元素作为栈顶
        self.elems = []

    # 判断是否为空
    def is_empty(self):
        return self.elems == []

        # if len(self.elems) == 0:
        #     return True
        # else:
        #     return False

    # 入栈
    def push(self,val):
        self.elems.append(val)

    # 出栈
    def pop(self):
        if self.is_empty():
            raise StackError("stack is empty")
        return self.elems.pop()

    # 查找栈顶元素
    def top(self):
        if self.is_empty():
            raise StackError("stack is empty")
        return self.elems[-1]


if __name__ == '__main__':
    st = sstack()
    st.push(10)
    st.push(20)
    st.push(30)
    while not st.is_empty():
        print(st.pop())

# -*- coding:utf-8 -*-
# @Time       :2022/2/3 21:21
# @SOFTWARE   :pythonProject1


'''
 栈的链式存储
  思路:
        1.源于链表就结构
        2.封装栈的操作方法 -> 入栈 出栈 栈空 栈顶元素
        3.链表的开头作为栈顶
'''

# 自定义异常
class StackError(Exception):
    pass

# 结点类
class Node:
    def __init__(self,val,next = None):
        self.val = val
        self.next = next

# 链式栈
class lstack:
    def __init__(self):
        # 标记栈的栈顶位置
        self._top = None

    def is_empty(self):
        return self._top is None

    # 入栈
    def push(self,val):
        self._top = Node(val,self._top)

    # 出栈
    def pop(self):
        if self._top is None:
            raise StackError("stack is empty")
        value = self._top.val
        self._top = self._top.next
        return value

    # 查看栈顶元素
    def top(self):
        if self._top is None:
            raise StackError("stack is empty")
        return self._top.val
if __name__ == '__main__':
    ls = lstack
    ls.push(10)
    ls.push(20)
    ls.push(30)
    print(ls.pop())

# -*- coding:utf-8 -*-
# @Time       :2022/2/3 21:08
# @SOFTWARE   :pythonProject1

# 逆波兰表达式

from sstack import *
st = sstack()
while True:
    exp = input()
    tmp = exp.split(' ')
    for i in tmp:
        if i not in ['+','-','*','/','p']:
            st.push()
        elif i == '+':
            y = st.pop()
            x = st.pop()
            st.push(y+x)
        elif i == '-':
            y = st.pop()
            x = st.pop()
            st.push(y-x)
        elif i == '*':
            y = st.pop()
            x = st.pop()
            st.push(y*x)
        elif i == '/':
            y = st.pop()
            x = st.pop()
            st.push(y/x)
        else:
            print(st.pop())

# -*- coding:utf-8 -*-
# @Time       :2022/2/5 10:28
# @SOFTWARE   :pythonProject1

"""
    一段文字中有（）[] {} ，编写一个接口程序去判断括号是否匹配正确
"""
from lstack import *

text = '(Markdown Preview Enhanced) 使用 [KaTeX] 或者 [MathJax] 来渲染数学表达式。' \
       '{KaTeX 拥有比 [MathJax] 更快的性能，但是它却少了很多 MathJax 拥有的特性}。' \
       '{你可以查看 (KaTeX supported functions/symbols 来了解[KaTeX] )支持那些符号和函数}'

# 将验证条件提前定义好
parens = "()[]{}" # 特殊处理的字符集
left_parens = "([{" # 入栈字符集
# 验证匹配关系
opposite = {'}' : '{',']' : '[' , ')':'('}
ls = lstack() # 存储括号的栈

# 编写生成器，用来遍历字符串，不断地提供括号及其位置
def parent(text):
    # i 遍历字符串的索引位置
    i,text_len = 0,len(text)

    # 开始遍历字符串
    while True:
        while i < text_len and text[i] not in parens:
            i += 1

            # 到字符串结尾了
            if i >= text_len:
                return
            else:
                yield text[i],i
                i += 1
                
                
# 功能函数：判断提供的括号是否匹配 -> 逻辑验证
def ver():
    for pr,i in parent():
        if pr in left_parens:
            ls.push((pr,i))
        elif ls.is_empty() or ls.pop()[0] != opposite[pr]:
            print("Unmatching is found at %d for %s" % (i,pr))
            break
        else:
            if ls.is_empty():
                print("all parenthese are match")
            else:
                d = ls.pop()
                print("Unmatching is found at %d for %s" % (d[1], d[0]))

# -*- coding:utf-8 -*-
# @Time       :2022/2/3 21:55
# @SOFTWARE   :pythonProject1

"""
 队列的顺序存储
    思路：
        1.基于列表完成数据存储
        2.通过封装规定数据操作
        3.先确定队头与队尾
"""

# 自定义队列异常
class QueueeError(Exception):
    pass

# 队列操作
class Squeue:
    # 初始化
    def __init__(self):
        self._elems = []


    # 判断队列是否为空
    def is_empty(self):
        return self._elems == []

    # 入队 -> 列表尾部为队尾
    def enqueue(self,val):
        self._elems.append(val)

    # 出队 -> 列表的第一个元素
    def dequeue(self):
        if not self._elems:
            raise QueueeError("queue is empty")
        return self._elems.pop(0)

if __name__ == '__main__':
    sq = Squeue()
    sq.enqueue(10)
    sq.enqueue(20)
    sq.enqueue(30)
    while not sq.is_empty():
        print(sq.dequeue())

#  ##########队列反转############

    for i in range(10):
        sq.enqueue(i)

    from sstack import *
    st = sstack()
    while not sq.is_empty():
        st.push(sq.dequeue())
    while not st.is_empty():
        sq.enqueue(st.pop())
    while not sq.is_empty():
        print(sq.dequeue())

# -*- coding:utf-8 -*-
# @Time       :2022/2/3 22:55
# @SOFTWARE   :pythonProject1


'''
    链式队列
        思路：
            1. 基于链表构建队列模型
            2. 链表的开端作为队头，结尾位置作为队尾
            3. 单独定义队尾标记 避免每次插入数据遍历
            4. 队头和队尾重叠时，队列为空
'''

# 自定义队列异常
class QueueeError(Exception):
    pass

# 结点类
class Node:
    def __init__(self,val,next = None):
        self.val = val
        self.next = next

# 队列操作
class Lqueue:
    def __init__(self):
        # 定义队头和队尾的变量
        self.front = self.rear = Node(None)

    # 判空
    def is_empty(self):
        return self.front == self.rear

    # 入队操作 -> rear动
    def enqueue(self,val):
        self.rear.next = Node(val)
        self.rear = self.rear.next

    # 出队 -> front动
    def dequeur(self):
        if self.front == self.rear:
            raise QueueeError
        # 认为front指向的结点已经出队
        self.front = self.front.next
        return self.front.val

# -*- coding:utf-8 -*-
# @Time       :2022/2/5 11:49
# @SOFTWARE   :pythonProject1

from squeue import *
# 利用顺序队列实现树的层次遍历
"""
    二叉树的简单实践
        思路：
            1.使用链式存储, 一个Node表示一个结点
            2.结点使用两个属性变量表示树的左右子树，即左连接和右连接
"""
# 二叉树结点
class Node:
    # 初始化结点
    def __init__(self,val,right = None,left = None):
        self.val = val
        self.right = right
        self.left = left

# 二叉树遍历类
class Bitree:
    def __init__(self,root = None):
        self.root = root

    # 先序遍历
    def preorder(self,node):
        if node is None:    # 中止条件
            return
        print(node.val,end="")
        self.preorder(node.left)
        self.preorder(node.right)


    # 中序遍历
    def inorder(self,node):
        if node is None:
            return
        self.inorder(node.left)
        print(node.val,end="")
        self.inorder(node.right)

    # 后续遍历
    def postorder(self,node):
        if node is None:
            return
        self.postorder(node.left)
        self.postorder(node.right)
        print(node.val,end = "")

    def levelorder(self,node):
        sq = Squeue()
        sq.enqueue(node)
        while not sq.is_empty():
            ndoe = sq.dequeue()
            print(node.val,end = "")
            if node.left:
                sq.dequeue(node.left)
            if node.right:
                sq.dequeue(node.right)

if __name__ == '__main__':
        #  B F G D I H E C A -> 根据后续遍历构建二叉树
    b = Node('B')
    f = Node('F')
    g = Node('G')
    d = Node('D',f,g)
    i = Node('I')
    h = Node('H')
    e = Node('E',i,h)
    c = Node('C',d,e)
    a = Node('A',b,c)   # 根节点

    # 将a作为根节点
    bt = Bitree(a)
    bt.preorder(bt.root)
    print()
    bt.inorder(bt.root)
    print()
    bt.postorder(bt.root)