根据《Python数据结构和算法分析》和其他网络资料整理而成。

什么是栈？

栈是有序集合，添加操作和移除操作发生在同一端。

栈里面的元素离底端越近，代表在栈中的时间越长，因此栈的底端具有非常重要的意义。新添加的元素将被最先删除。这种排序原则是LIFO(last-in first out),后进先出

例如书本的堆叠

栈的抽象数据类型

栈的抽象数据类型由下面的结构和操作定义。

  • Stack() 创建一个空栈。不需要参数，返回一个空栈。
  • push(item) 将一个元素添加到栈的顶端。需要一个参数item,且无返回值
  • pop() 将顶端的元素删除。不需要参数，但是有返回值。
  • peek() 返回栈顶端的元素。不要参数，也不修改栈的内容。
  • isEmpty()检查栈是否为空。不需要参数，返回一个布尔值。
  • size()返回栈中元素的数目。不需要参数，返回一个整数。

用python实现栈

明确定义栈的抽象数据类型后，我们用Python来实现。抽象数据类型的实现被称为数据结构。

因为栈是元素的集合，所以可以使用Python提供的列表实现。

实现方式一

用列表的头部作为栈的底端，利用pop()和append()方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def push(self,item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items) - 1]
    def size(self):
        return len(self.items)

实现方式二

利用列表的尾部作为栈的底端，所以pop()和append()这组不再使用。应当使用pop(0)和insert(0,item)访问下标为0，也就是第一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack:
    def __init__(self):
        self.items = []

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

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

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

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

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

上述两种实现都可行，但是二者在性能方面肯定是有差异。append和pop()方法的时间复杂度都是O(1),这意味着不论栈中有多少元素，第一种实现中的push和pop都会在恒定的时间内完成。第二种实现的性能受限于栈中的个数，因为insert(0)和pop(0)的时间复杂度是O(n),元素越多时间越慢。

匹配符号

匹配括号

匹配括号是每一个左括号都有与之对应的一个右括号，并且括号对有正确的嵌套关系。下面是正确匹配的括号串。

(()()())

(((())))

下面是不匹配的括号串

((()

((())

我们编写一个算法，它从左到右读取一个括号串，然后判断其中的括号是否匹配。为了解决这个问题，需要注意到一个很重要的现象。。当从左到右处理括号时，最右边的无匹配左括号 必须与接下来遇到的第一个右括号相匹配。并且，在第一个位置的左括号可能要 等到处理至最后一个位置的右括号时才能完成匹配。相匹配的右括号与左括号出现的顺序相反。 这一规律暗示着能够运用栈来解决括号匹配问题

一旦认识到用栈来保存括号是合理的，算法编写起来就会十分容易。由一个空栈开始，从左 往右依次处理括号。如果遇到左括号，便通过 push 操作将其加入栈中，以此表示稍后需要有一 个与之匹配的右括号。反之，如果遇到右括号，就调用 pop 操作。只要栈中的所有左括号都能 遇到与之匹配的右括号，那么整个括号串就是匹配的；如果栈中有任何一个左括号找不到与之匹 配的右括号，则括号串就是不匹配的。在处理完匹配的括号串之后，栈应该是空的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 括号匹配
def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index += 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

匹配符号

对于匹配括号的升级，例如:

[[(‘’)]]

[{)’]

各类左右符号的组合，在以上的代码增加[],{}的处理即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 符号匹配

def parChecker(symbolString):
    i = 1
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "{[(":
            s.push(symbol)

        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()

                if not matches(top,symbol):
                    balanced = False
        index += 1

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

def matches(left,right):

    lefts = "([{"
    rights = ")]}"
    return lefts.index(left) == rights.index(right)

进制转换

十进制—>二进制

十进制转换的二进制的方法是不断除以二，直至商为0。然后把各余数倒序连起来，例如：

100/2 = 50…0

50/2 =25…0

25/2 = 12…1

12/2 = 6…0

6/2 = 3…0

3/2 = 1…1

1/2 = 0…1

所以最终结果为1100100

最终程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Stack:
    def __init__(self):
        self.items = []
    def push(self,item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def isEmpty(self):
        return self.items == []
    def peek(self):
        return self.items[len(self.items)-1]
    def size(self):
        return len(self.items)
    def printf(self):
        print(self.items)

def divide_to_2(num):
    s = Stack()
    binStr = ""
    while num > 0:
        s.push(num % 2)
        num = num // 2
    while not s.isEmpty():
        binStr = binStr + str(s.pop())
    return binStr

num = int(input('输入数字:'))
print(divide_to_2(num))

十进制— > 任意进制

1
2
3
4
5
6
7
8
9
10
11
12
def divide_to_base(num,base):
    s = Stack()
    baseStr = ""
    while num > 0:
        s.push(num % base)
        num = num // base
    while not s.isEmpty():
        baseStr = baseStr + str(s.pop())
    return baseStr

num,base = map(int,input('输入数字和目的进制:').split())
print(divide_to_base(num,base))

Python的进制转换

考虑到语法特性，Python 对于进制转换的函数，已经做好的封装。

十进制—>其他进制

  1. 十进制—>二进制：bin(999)

  2. 十进制—>八进制：oct(999)

  3. 十进制—>二进制：hex(999)

其他进制—>十进制

  1. 二进制—>十进制：int("10",2)
  2. 八进制转十进制: int("0o13",8) (前缀可以不写)
  3. 十六进制—>十进制: int("0xaa",16) (前缀可不写)

前序、中序和后序表达式

中序表达式 前序表达式 后序表达式
A + B + A B A B +

下面是中缀表达式转换成其他表达式的方法:

判断回文字符串

回文字符串是什么?

例如xyx,hgfkfgh这类从左往右读等于从右往左读的字符串。

对于回文字符串的判断，我们有以下步骤：

  1. 获取字符串的长度
  2. 字符串如果是回文串，那中间是对称的，求中间节点mid
  3. 把mid节点之前的字符全部压入栈
  4. mid之前的字符依次出栈，与mid之后的字符一一匹配

例题:后缀表达式的值

链接:信息学奥赛一本通T1331-后缀表达式的值 - C语言网 (dotcpp.com)

解题思路：
1.从左到右扫描后缀表达式的每一个字符。
2.如果读入的字符是数字，将其转化为整数，并将其压入栈中。
3.如果读入的字符是运算符，则从栈中取出两个运算数，进行计算，并将结果压入栈中。
4.重复上述过程，直到读完整个后缀表达式为止。
5.最后，栈中只剩下一个数字，即为后缀表达式的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
inStr = (input())
Str = inStr.split(' ')
Str1 = Str[:-1]
len1 = len(Str1)
Str2 = list(Str[-1])
Str = Str1 + Str2
S = ' '.join(Str)
# print(S)

class Stack:

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

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

    def push(self, item):
        self.__items.append(item)

    def peek(self):
        if not self.is_empty():
            return self.__items[-1]
        else:
            return None

    def pop(self):
        if not self.is_empty():
            return self.__items.pop()
        else:
            return None

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


def calc_postfix_expression(postfix_expression):
    op_stack = Stack()
    expression_list = postfix_expression.split()

    for token in expression_list:
        if token.isdigit():
            op_stack.push(int(token))
        else:
            if token == '@':
                break
            op = token
            op2 = op_stack.pop()
            op1 = op_stack.pop()
            result = do_math(op, op1, op2)
            op_stack.push(result)

    return op_stack.pop()


def do_math(op, op1, op2):
    if op == "+":
        return op1 + op2
    elif op == "-":
        return op1 - op2
    elif op == "*":
        return op1 * op2
    elif op == "/":
        if op2 == 0:
            return "error"
        return op1 / op2


if __name__ == '__main__':
    print(calc_postfix_expression(S))