基本数据结构 — — 栈

后进先出（右进右出）

假设列表的尾部是栈的顶端

class Stack:

    # 初始化
    def __init__(self):
        self.items = []

    # 检查栈是否为空
    def isEmpty(self):
        return len(self.items) == 0

    # 往栈压数据
    # 先压的在栈底（相当于往列表的左端添加元素）
    # 后压的在栈顶（相当于往列表的右端添加元素）
    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)

    # 打印栈
    def __repr__(self):
        return str(self.items)

【实例】匹配括号 — — 一种括号：'(' 和 ')'

if __name__ == '__main__':
    stack = Stack()
    # line = '()()()()'
    # line = '()))'
    line = '(((())))'
    # line = '))))((('
    for c in line:
        if c == '(':
            stack.push(c)
        elif c == ')':
            if stack.isEmpty():
                print('不匹配')
                break
            else:
                char = stack.pop()
    
    if stack.isEmpty():
        print('匹配')
    else:
        print('不匹配')

【实例】匹配括号 — — 三种括号：'(' 和 ')'、'[' 和 ']'、'{' 和 '}'

if __name__ == '__main__':
    stack2 = Stack()
    # line2 = '[{()}]'
    # line2 = '((()]))'
    # line2 = '([)]'
    line2 = '[{(]})'
    for c in line2:
        if c in '([{':
            stack2.push(c)
        elif c == ')]}':
            if stack2.isEmpty():
                print('不匹配')
                break
            else:
                char = stack2.pop()

    if stack2.isEmpty():
        print('匹配')
    else:
        print('不匹配')

【实例】定义一个通用函数，可求二进制、十进制、十六进制

def convert(num, base):
    ss = '0123456789ABCDEF'
    stack3 = Stack()
    while num > 0:
        k = num % base
        stack3.push(k)
        num = num // base

    while not stack3.isEmpty():
        print(ss[stack3.pop()], end='')

# result = convert(5, 2)
# result1 = convert(233, 10)
result2 = convert(100, 16)

【实例】输入任意表达式（字符串），可计算其值

def infix2postfix(expression):
    # 创建字典，以运算符为键，大小为值（优先级），用于比较后压栈的值是否比栈中的运算符的值（优先级）要小
    dict_ = {}
    dict_['*'] = 3
    dict_['/'] = 3
    dict_['+'] = 2
    dict_['-'] = 2
    dict_['('] = 1

    # 创建栈
    dict_stack = Stack()
    # 创建列表，存放数跟运算符
    dict_num = []
    list_ = exp.split(' ')
    for c in list_:
        if c not in '+-*/()':
            dict_num.append(c)    # 碰到数时先把数放进列表
        else:
            if c == '(':
                dict_stack.push(c)
            elif c == ')':
                while dict_stack.peek() != '(':
                    dict_num.append(dict_stack.pop())    # 当碰到右括号时，查看栈，先把栈中的运算符弹出，放进列表中
                dict_stack.pop()    # 删除')'对应'('
            else:
                # 保证栈不空，判断即将压栈的运算符是否比栈里面的运算符要小
                while not dict_stack.isEmpty() and dict_[c] <= dict_[dict_stack.peek()]:
                    dict_num.append(dict_stack.pop())    # 当即将压栈的运算符是否比栈里面的运算符要小时，把栈里面的运算符弹出，放进列表中
                dict_stack.push(c)    # 把优先级小的运算符添加到栈中

    # 遍历完后，栈中还剩运算符
    while not dict_stack.isEmpty():
        dict_num.append(dict_stack.pop())    # 把栈中剩下的运算符弹出，放到列表中

    return ' '.join(dict_num)    # 用空格作为分隔符把列表元素合并成字符串


def calculate_postfix(expression):
    num_stack = Stack()
    num_list = expression.split()    # 对infix2postfix()返回的字符串进行分割
    # print(num_list)

    for c in num_list:
        if c not in '+-*/':
            num_stack.push(c)
        else:
            right_num = int(num_stack.pop())
            left_num = int(num_stack.pop())
            if c == '+':
                temp_result = left_num + right_num
            if c == '-':
                temp_result = left_num - right_num
            if c == '*':
                temp_result = left_num * right_num
            if c == '/':
                temp_result = left_num / right_num

            num_stack.push(temp_result)

    result = num_stack.pop()
    return result


# exp = 'A + B * C'
# exp = '( A + B ) * ( C + D )'
# exp = '( A + B ) * C'
# exp = '( 9 + 2 ) * 8'
exp = '77 / 7 + ( 10 - 6 ) / 2 - 6'
result = infix2postfix(exp)
print(result)
result2 = calculate_postfix(result)
print(result2)