基本数据结构

第三章 基本数据结构

（1）栈定义及实现

python
# -*- coding: utf-8 -*-#
# -------------------------------------------------------------------------------
# Name:         1_用Python实现栈
# Description:  栈是元素的有序集合，其排序原则被成为LIFO(last-in first-out),即先进后出。基于在集合中的时间来排序。
# Author:       zhaoyaowei
# Date:         2023/2/18 13:15
# -------------------------------------------------------------------------------

# 栈抽象数据类型
"""
1、Stack()：创建1个空栈。无入参，返回1个空栈。
2、push(item)：将1个元素添加至栈的顶端。入参item，无返回值。
3、pop()：将栈顶端元素移除。无入参，返回顶端元素，修改栈内容。
4、peek()：返回栈顶端元素，不移除该元素。无入参，不修改栈内容。
5、isEmpty()：检测栈是否为空。无入参，返回1个布尔值。
6、size()：返回栈中元素的数据。无入参，返回1个整数。
"""


class Stack:
    """
    基于有序集合的Python列表实现栈，假设列表尾部==栈顶端，列表头部==栈底端;
    此外，也可将列表头部==栈顶端，需要修改push()、pop()、peek()方法，见注释部分。
    两种方式性能有差异，其时间复杂度分别为O(1)和O(n)
    """

    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)
        # self.items.insert(0, item)

    def pop(self):
        return self.items.pop()
        # return self.items.pop(0)

    def peek(self):
        return self.items[-1]
        # return self.items[0]

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


if __name__ == '__main__':
    # 栈操作示例
    s = Stack()
    print(s.isEmpty())
    print(s.push(4))
    print(s.push("dog"))
    print(s.peek())
    print(s.push(True))
    print(s.size())
    print(s.isEmpty())
    print(s.push(8.4))
    print(s.pop())
    print(s.size())
    print(s.__dict__)

（2）匹配括号和符号

python
# -*- coding: utf-8 -*-#
# -------------------------------------------------------------------------------
# Name:         2_匹配括号和符号
# Description:  利用栈来实现简单括号匹配、复杂括号匹配
# Author:       zhaoyaowei
# Date:         2023/2/18 15:03
# -------------------------------------------------------------------------------

from pythonds.basic.stack import Stack


def parChecker(n):
    """
    简单括号匹配：
        True:((()))、(()())
        False: (()、()())
    思路：新建1个空栈，从左往右，遇到左括号，将其push压栈，表示稍后需要1个与之匹配都右括号；
        反之，遇到右括号，则调pop移除顶端左括号。只要所有左括号都能遇到与之匹配的右括号，即True。
        若存在任何1个左括号无法找到与之匹配的右括号，则False。若全都匹配，则最终栈应该是空的。
        1、相匹配的右括号与左括号出现的顺序相反（栈）
        2、从左到右，最后打开的左括号必须要匹配最先打开的右括号（次序反转）
        3、当扫描到右括号时，删除栈顶端的左括号，若栈中没有元素返回，则返回True
        4、如果都没有找到，则返回True
    
    :param n: 简单括号字符串
    :return: 布尔值
    """
    s = Stack()
    balanced = True  # 字义平衡，表示匹配成功，2个括号为闭合状态
    index = 0  # 遍历n的下标
    while index < len(n) and balanced:
        i = n[index]
        if i not in ['(', ')']:
            index += 1
            continue  # continue 遇到非括号字符，跳出本次循环；break,终止所有循环
        if i == "（":
            s.push(i)
        else:  # 右括号
            if s.isEmpty():  # 查找有没有左括号，栈是否为空；为空，无左括号，无法闭合匹配
                balanced = False
            else:
                s.pop()  # 删除栈顶端的左括号
        index += 1

    if balanced and s.isEmpty():  # 所有括号匹配，且栈为空
        return True
    return False  # 都没有找到，返回False


def parChecker1(n):
    """
    复杂符号匹配：
        True: {{([][])}()}、[[{{(())}}]]
        False: ([)]、((()]))
    思路：与简单括号相比，区别在于当出现右符号时，必须检测其类型是否与栈顶的左符号类型相匹配（调用辅助函数）。
        若2个符号不匹配，则整个符号串也就不匹配。若处理完成且栈是空的，则说明所有符号正确匹配。
    :param n: 简单括号字符串
    :return: 布尔值
    """
    s = Stack()

    balanced = True
    index = 0
    while index < len(n) and balanced:
        i = n[index]
        if i in "{[(":
            s.push(i)
        else:
            if s.isEmpty():
                balanced = True
            else:
                top = s.pop()
                if not matches(top, i):
                    balanced = False
        index += 1

    if balanced and s.isEmpty():
        return True
    return False


def matches(top, right):
    """
    检测栈顶移除的符号是否与当前的右符号匹配,相同类型
    :param top: 栈顶参数
    :param right:
    :return:
    """
    tops = "{[("
    rights = "}])"

    return tops.find(top) == rights.index(right)


if __name__ == '__main__':
    s = "([)]"
    print(parChecker1(s))

（3）十进制转任意进制

python
# -*- coding: utf-8 -*-#
# -------------------------------------------------------------------------------
# Name:         3_十进制转任意进制
# Description:  利用栈的反转特性进行进制的转换，值除以基数，余数进栈，结果出栈
# Author:       zhaoyaowei
# Date:         2023/2/18 17:14
# -------------------------------------------------------------------------------
from pythonds import Stack


def baseConverter(dec_number, base):
    """
    十进制转换为二进制、八进制、十六进制等,基础超过十时，不能再直接使用余数，可采用digits存储对应余数位置上的数字
    :param dec_number: 十进制数值，大于0
    :param base: 进制基础，十进制、二进制、16进制等
    :return: 转换后的base进制数字串
    """
    digits = "0123456789ABCDEF"

    s = Stack()

    while dec_number > 0:
        rem = dec_number % base
        s.push(rem)
        dec_number = dec_number // base
        print(s.peek())

    new_str = ""
    while not s.isEmpty():
        new_str = new_str + digits[s.pop()]
    return new_str


# 附：
# （1）python内置进制转换方法：
num = 20
print(f"十进制 {num} 转 二进制 = {bin(num)}")
print(f"十进制 {num} 转 八进制 = {oct(num)}")
print(f"十进制 {num} 转 十六进制 = {hex(num)}")
num1 = 0b10100
num2 = 0o24
num3 = 0x14
int("0b10100", 2)  # 使用int("String",num)解决，string为其他进制的表示，num为该进制具体进制数
print(f"二进制 {num1}、八进制 {num2}、十六进制 {num3} 转 十进制 分别 = {int(num1)}, {int(num2)}, {int(num3)}")
print(f"二进制 {num1} 分别转八进制 、十六进制 = {oct(num1)}, {hex(num1)}")
# （2）进制转换算法
# 二进制-->十进制:
# 例如将二进制的0b101011转换为十进制的步骤如下：
# 第0位 1 x 2^0 = 1；
# 第1位 1 x 2^1 = 2；
# 第2位 0 x 2^2 = 0；
# 第3位 1 x 2^3 = 8；
# 第4位 0 x 2^4 = 0；
# 第5位 1 x 2^5 = 32；
# 把结果值相加1+2+0+8+0+32=43，即0b101011=43
# 八进制-->十进制:
# 例如将八进制的0o34转换为十进制的步骤如下：
# 第0位 4 x 8^0 = 4；
# 第1位 3 x 8^1 = 24；
# 把结果值相加，4+24=28，即0o34=28
# 十六进制-->十进制
# 例如将十六进制的0x3c转换为十进制的步骤如下：
# 第0位 c x 16^0 = 12；
# 第1位 3 x 16^1 = 48；
# 把结果值相加，12+48=60，即0x3c=60
# 十进制-->二进制
# 例如将十进制的56转换为二制的步骤如下：
# 将商56除以2，商28余数为0；
# 将商28除以2，商14余数为0；
# 将商14除以2，商7余数为0；
# 将商7除以2，商3余数为1；
# 将商3除以2，商1余数为1；
# 将商1除以2，商0余数为1；
# 因为最后一位是经过多次除以2才得到的，因此它是最高位，读数字从最后的余数向前读，111000，所以56=ob111000。
if __name__ == '__main__':
    print(baseConverter(1888, 10))

（4）前序、中序和后序表达式

python
# -*- coding: utf-8 -*-#
# -------------------------------------------------------------------------------
# Name:         4_前序、中序和后序表达式
# Description:  计算运算符和操作数的不同相对位置的表达式，其中中序需要()来消除歧义。
# 前序和后序表达式中的运算顺序完全由运算符的位置决定。
# 任意复杂的中序表达式转前序或者后序：1、写成完全括号表达式 2、括号内的运算符移动到左（右）括号，并去掉右（左）括号即可。
# Author:       zhaoyaowei
# Date:         2023/3/4 17:49
# -------------------------------------------------------------------------------

from pythonds.basic import Stack
import string


def infixToPostfix(infixexpr):
    """
    用Python实现从中序到后序表达式的转换
    解题思路：转换过程中，由于运算符右侧的操作数还未出现，需要先保存。其次运算符之间有不同的优先级，需要反转。
            综上，使用栈来处理。
    解题步骤：
        （1）创建1个保存运算符的空栈opstack,以及1个用于保存结果的空列表
        （2）假设中序表达式以空格分割，使用split转换成标记列表
        （3）从左往右，扫描此标记列表
            a. 如果标记是操作数，将其添加制结果列表的末尾
            b. 如果标记是左括号，将其压入opstack栈
            c. 如果标记是右括号，反复从opstack栈中移除元素，直至遇到对应的左括号。
    :param infixexpr:
    :return:
    """