Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法

1、栈的定义

栈是一种有次序的数据项集合,在栈中,数据
项的加入和移除都仅发生在同一端,
这一端叫栈“顶top”,另一端叫栈“底base”

2、栈的性质

  • 后进先出LIFO Last in First out:距离栈底越近的数据项,留在栈中的时间就越长,而最新加入栈的数据项会被最先移除。
  • 反转次序:数据进栈和出栈的次序正好相反Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法

3.栈的工作流程

抽象数据类型“栈”是一个有次序的数据集,每个数据项仅从“栈顶”一端加入到数据集中、从数据集中移除,栈具有后进先出LIFO的特性
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法

4.栈的各种操作

  • Stack():创建一个空栈,不包含任何数据项
  • push(item):将item加入栈顶,无返回值
  • pop():将栈顶数据项移除,并返回,栈被修改
  • peek():“窥视”栈顶数据项,返回栈顶的数据项但不移除,栈不被修改
  • isEmpty():返回栈是否为空栈
  • size():返回栈中有多少个数据

例如
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法

5.Python实现栈

将栈定义为python中的类,用列表实现栈

class Stack:
    def __init__(self):
        Stack.items = []
    def push(self, item):
        return self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items) - 1]
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

S = Stack()
print(S.size())
print(S.isEmpty())
S.push(1)
S.push(2)
S.push(3)
print(S.items)
print(S.size())
print(S.isEmpty())
S.pop()
print(S.items)
print(S.peek())
print(S.size())
print(S.isEmpty())

通常在考试中,我们不需要从0写一个栈。直接定义一个栈就用就行了。

S = Stack()
S.push(item)
S.pop()
S.peek()
S.size()
S.isEmpty()

6.栈的应用

6.1简单括号匹配

括号的使用必须平衡,即左右(开闭)括号数量相同。
括号匹配识别算法:
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法
简而言之,左括号入栈,碰到右括号时,左括号出栈,栈为空且便利结束表示匹配成功,其他情况匹配失败。

def parChecking(string):
    s = Stack()
    result = True
    for i in range(len(string)):
        if string[i] == "(":
            s.push("(")
        else:
            if s.isEmpty() == True: # 这表示右括号数量多了,匹配失败
                result = False
            else:
                s.pop()
    if s.isEmpty() == False: # 遍历结束,如果左括号多,栈非空,匹配失败
        result = False
    return result
print(parChecking("()"))
print(parChecking("((())"))

通用的括号匹配算法还包括了中括号和花括号,因此我们还需要加上他们的匹配判断。如果括号类型不匹配就判断为错。

def match(left, right):
    lefts = "([{"
    rights = ")]}"
    return lefts.index(left) == rights.index(right)

def parChecking(string):
    s = Stack()
    result = True
    for i in range(len(string)):
        if string[i] in "([{":
            s.push(string[i])
        else:
            if s.isEmpty() == True: # 这表示右括号数量多了,匹配失败
                result = False
            else:
                top = s.pop()
                if not match(top, string[i]):
                    result = False
    if s.isEmpty() == False: # 遍历结束,如果左括号多,栈非空,匹配失败
        result = False
    return result
print(parChecking("[{()}]"))
print(parChecking("{)"))

6.2 表达式转换

我们平时用的都是中缀表达式,如 A + B。 + 就是运算符。 中缀表达式就是运算符在数字之间,前缀表达式时运算符在数字前面,后缀表达式是运算符在数字后面。
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法
第二行的B * C是子表达式,所以将他们的运算符放在子表达式的前后。
再来看中缀表达式“(A+B)×C”,按照转换的规则,前缀表达式是“×+ABC”,而后缀表达式是“AB+C×”,中缀表达式转换为前缀表达式或者后缀表达式后,括号就没了,更利于计算机计算。

更多的例子
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法

6.2.1中缀表达式转后缀和前缀的方法:

首先引入全括号形式的中缀表达式,后续要用到这个形式。
全括号形式就是把表达式能括的括号全写上。
比如 A + B × C 的全括号形式就是 (A + (B × C)),这种表达式的形式显式表达了计算次序,我们注意到每一对括号,都包含了一组完整的操作符和操作数。

无论表达式多复杂,需要转换成前缀或者后缀,只需要两个步骤:
1.将中缀表达式转换为全括号形式
2.将所有的操作符移动到子表达式所在的左括号(前缀)或者右括号(后缀)处,替代之,再删除所有的括号
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法

6.2.1.1 中缀转后缀

看子表达式 (B × C) 的右括号,如果把操作符×移到右括号的位置,替代它,再删去,左括号,得到 BC×,这个正好把子表达式转换为后缀形式
进一步再把更多的操作符移动到相应的右括号处,替代之,再删去左括号,那么整个表达式就完成了到后缀表达式的转换
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法

6.2.1.1 中缀转前缀

同样的,如果我们把操作符移动到左括号的位置替代之,然后删掉所有的右括号,也就得到了前缀表达式
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法

6.2.3 通用的中缀转后缀算法

中缀表达式 A + B * C,其对应的后缀表达式是 ABC * +

  • 操作数ABC的顺序没有改变。
  • 操作符的出现顺序,在后缀表达式中反转了。
  • 由于 * 的优先级比 + 高,所以后缀表达式中操作符的出现顺序与运算次序一致。

在中缀表达式转换为后缀形式的处理过程中,操作符比操作数要晚输出。因为在后缀表达式中,都是先写两个操作数再写他们的运算符号。
所以在扫描到对应的第二个操作数之前,需要把操作符先保存起来。
在中缀表达式转换为后缀形式的处理过程中,操作符比操作数要晚输出。所以在扫描到对应的第二个操作数之前,需要把操作符先保存起来。
这种反转特性,使得我们考虑用栈来保存暂时未处理操作符

对于 (A + B) × C 这个式子来说,它的后缀形式是 AB + C ×
这里+的输出比要早,主要是因为括号使得+的优先级提升,高于括号之外的 ×。

回顾刚刚所讲的内容,中缀转后缀就是把全括号形式的中缀表达式的右括号换成操作符。
所以遇到左括号,要标记下,其后出现的操作符优先级提升了,一旦扫描到对应的右括号,就可以马上输出这个操作符。

总之,在从左到右扫描逐个字符扫描中缀表达式的过程中,采用一个来暂存未处理的操作符。

这样,栈顶的操作符就是最近暂存进去的,当遇到一个新的操作符,就需要跟栈顶的操作符比较下优先级,再行处理。

算法流程:

  1. 创建空栈opstack用于暂存操作符,空表postfixList用于保存后缀表达式
  2. 将中缀表达式转换为token列表
  3. 从左到右扫描中缀表达式token列表
    如果单词是操作数,则直接添加到后缀表达式列表的末尾
    如果单词是左括号“(”,则压入opstack栈顶
    如果单词是右括号“)”,则反复弹出opstack栈顶操作符,加入到输出列表末尾,直到碰到左括号
    如果单词是操作符“*/±”,则压入opstack栈顶
    •但在压入之前,要比较其与栈顶操作符的优先级
    •如果栈顶的高于或等于它,就要反复弹出栈顶操作符,加入到输出列表末尾
    •直到栈顶的操作符优先级低于它
  4. 中缀表达式列表扫描结束后 ,把opstack栈中的所有剩余操作符依次弹出,添加到输出列表末尾
  5. 把输出列表再用join方法合并成后缀表达式字符串,算法结束。
    例如
    Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法
def infixToPostfix(infixexpr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1 # 到此为止是在标记各操作符的优先级
    tokenList = infixexpr.split() # 将中缀表达式的各token分割为列表
    opStack = Stack() # 用于暂存操作符
    postfixList = () # 用于保存输出结果
    for token in tokenList: # 遍历整个表达式
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "123456789":
            postfixList.append(token) # 遇到操作符时直接输出操作符
        elif token == "(":
            opStack.push("token")
        elif token == ")":
            topToken = opStack.pop()
            while topToken != "(":
                postfixList.append(topToken)
                topToken = opStack.pop()
            else:
                while (not opStack.isEmpty()) and \
                        (prec[opStack.peek()] >= prec[token]):
                            postfixList.append(opStack.pop())
                opStack.push(token)
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return "".join(postfixList)

print(infixToPostfix("(A+B)*C"))

6.2.4 后缀表达式求值

扫描后缀表达式,操作符在操作数后面,所以暂存操作数。在碰到操作符的时候,再将暂存的两个操作数进行实际的计算。仍然是栈的特性:操作符只作用于离它最近的两个操作数。

例如
“4 5 6 * +”,我们先扫描到4、5两个操作数,还不知道对这两个操作数能做什么计算,需要继续扫描后面的符号才能知道,继续扫描,又碰到操作数6,还是不能知道如何计算,继续暂存入栈。直到“*”,现在知道是栈顶两个操作数5、6做乘法。
弹出两个操作数,计算得到结果30。注意:先弹出的是右操作数后弹出的是左操作数,这个对于-/很重要!
为了继续后续的计算,需要把这个中间结果30压入栈顶。
继续扫描后面的符号
当所有操作符都处理完毕,栈中只留下1个操作数,就是表达式的值
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法
Python数据结构5:栈,代码实现栈,括号匹配算法,中缀表达式转后缀表达式算法,后缀表达式求值算法
算法流程重点

  1. 创建空栈operandStack用于暂存操作数
  2. 将后缀表达式用split方法解析为token的列表
  3. 从左到右扫描单词列表
  • 如果单词是一个操作数,将单词转换为整数int,压入operandStack栈顶
  • 如果单词是一个操作符(*/±),就开始求值,从栈顶弹出2个操作数,先弹出的是右操作数,后弹出的是左操作数,计算后将值重新压入栈顶
  1. 单词列表扫描结束后,表达式的值就在栈顶
  2. 弹出栈顶的值,返回。
class Stack:
    def __init__(self):
        Stack.items = []
    def push(self, item):
        return self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items) - 1]
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

def doMath(op, op1, op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

def postfixEval(postfixexpr):
    operandStack = Stack()
    tokenList = postfixexpr.split()
    for token in tokenList:
        if token in "0123456789":
            operandStack.push(int(token))
        else:
            operand2 = operandStack.pop()
            operand1 = operandStack.pop()
            result = doMath(token, operand1, operand2)
            operandStack.push(result)
    return operandStack.pop()

print(postfixEval("456*+"))

参考文献

本文的知识来源于B站视频 【慕课+课堂实录】数据结构与算法Python版-北京大学-陈斌-字幕校对-【完结!】,是对陈斌老师课程的复习总结

上一篇:spring-logger spring中日志配置


下一篇:PyQt5基础学习-QSplitter(Qt.Horizontal)(水平拖动控件宽度) 1QSplitter().setSizes([设置拖动控件的宽度])