Python数据结构与算法中的栈详解(3)

Python数据结构与算法中的栈详解(3)

在前两篇文章中,我们介绍了栈的基本概念、实现方式和应用场景。在本篇文章中,将深入探讨栈的一些高级应用,包中缀表达式转后缀表达式、后缀表达式求值和括号匹配等。

中缀表达式转后缀表达

中缀表达式是我们平常使用的表达式,例如3 + 4 * 5。但是,中缀表达式不方便计算机进行计算,因此我们需要将中缀表达式转换为后缀表达式。缀表达式也称为逆波兰表达式,它的计算方式更加方便。例如,上面的中缀表达式可以转换为后缀表达式3 4 5 * +

下面是中缀表达式后缀表达式的算法:

  1. 初始化一个空栈和一个空列表。
  2. 从左到右扫描中缀表达式的每个素。
  3. 如果当前元素是数字,将其添加到输出列表中。
  4. 如果当前元素是左括号,将其压入栈中。
  5. 如果当前元素是右括号,则将栈中的元素弹出并添加到输出列表中,直到遇到左括号。左括号不添加到列表中。
  6. 如果当前元素是运算符,比较其与栈顶运算符的优先级:
  7. 如果栈顶运算符优级较高或相等,则将其弹出并添加到输出列表中,直到栈为空或栈顶运算符优先级较低。
  8. 将当前运算符压入栈中。
  9. 如果中缀表达式扫描完毕,但栈中仍有运算符,将它们依次弹出并添加到输出列表中。
  10. 输出列表中的元素就是后缀表达式。

下面是一个示例,演示如何将中缀表达式3 + 4 * 5转换为后缀表达式:

  1. 初始化一个空栈和一个空列表。
  2. 从左到右描中缀表达式的每个元素。
  3. 3是数字,将其添加到输出列表中。
  4. +是运算符,将其压入栈中。
  5. 4是数字,其添加到输出列表中。
  6. *是运算符,比较其与栈顶运算符的优先级,栈顶运算符+优先级较低,将*压入栈中。
  7. 5是数字,将其添加到输出中。
  8. 中缀表达式扫描完毕,但栈中仍有运算符,将它们依次弹出并添加到输出列表中。栈中只有一个运算符*,其弹出并添加到输出列表中。
  9. 输出列表中的元素就是后缀表达式3 4 5 * +

下面是Python代码实现中缀表达式转后缀表达式:

def infix_to_postfix(infix_expr):
    # 运算符优先级
    prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
    # 初始化一个空栈和空列表
    op_stack = []
    postfix_list = []
    # 将中缀表达式转换为列表
    infix_list = infix_expr.split()

    for token in infix_list:
        if token.isdigit():
            # 如果当前元素是数字,将其添加到输出列表中
            postfix_list.append(token)
        elif token == '(':
            # 如果当前元素是左括号,将其压入栈中
            op_stack.append(token)
        elif token == ')':
            # 如果当前元素是右括号,则将栈中的元素弹出并添加到输出列表中,直到遇到左括号
            top_token =_stack.pop()
            while top_token != '(':
                postfix_list.append(top_token)
                top_token = op_stack.pop()
        else:
            # 如果当前元素是运算符
            while op_stack and prec[op_stack[-1]] >= prec[token]:
                # 比较其与栈顶运算符的优先级
                postfix_list.append(op_stack.pop())
            op_stack.append(token)

    # 将栈中剩余的运算符弹出并添加输出列表中
    while op_stack:
        postfix_list.append(op_stack.pop())

    # 输出列表中的元素就是后缀表达式
    return ' '.join(postfix_list)

后缀表达式求值

后表达式的计算方式更加方便,可以使用栈来实现。下面是后缀表达式求值的算法:

  1. 初始化一个空栈。
  2. 从左到右扫描后缀表达式的每个元素。
    3 如果当前元是数字,将其压入栈中。
  3. 如果当前元素是运算符,弹出栈顶的两个元素,进行运,并将结果压入栈中。
  4. 扫描完毕后,栈中只剩下一个元素,即为后缀表达式的计算结果。

下面是一个示例,演示如何计算后缀表达式3 4 5 * +的值:

  1. 初始化一个空栈。
  2. 从左到右扫描后缀表达式的每个元素。
  3. 3是数字,将压入栈中。
  4. 4是数字,将其压入栈中。
  5. 5是数字,将其压入栈中。
    -*是运算,弹出栈顶的两个元素45,进行运算4 * 5 = 20,并将结果20`压入栈中。
  6. +是运算符,弹出栈顶的两个元素320,进行运算3 + 20 = 23,并将结果23`压入栈中。
  7. 扫描完毕后,栈中只剩下一个元素23,即为后缀表达式的计算结果。

下面是Python代码实现后缀表达式求值:

def postfix_eval(postfix_expr):
    # 初始化一个空栈
    operand_stack = []
    # 将后缀表达式转换为列表    postfix_list = postfix_expr.split()

    for token in postfix_list:
        if token.isdigit():
            # 如果当前元素是数字,将其压入栈中
            operand_stack.append(int(token))
        else:
            # 如果当前元素是运算符,弹出栈顶的两个元素,进行运算,并将结果压入栈中
            operand2 = operand_stack.pop()
            operand1 = operand_stack.pop()
            result = do_math(token, operand1, operand2)
            operand_stack.append(result)

    # 栈中只剩下一个元素,即为后缀表达式的计算结果
    return operand_stack.pop()

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

括号匹配

括号匹配是栈的一个经典应用。我们可以使用栈来判断一个字符串中的括号是否匹配。下面是括号匹配的算法:

  1. 初始化一个空栈。
  2. 从左到右扫描字符串中的每个字符。
  3. 如果当前字符是左括号,将其压入栈中。
    4.当前字符是右括号,弹出栈顶元素。如果栈顶元素不是相应的左括号,则括号不匹配。
  4. 扫描完毕,如果栈为空,则括号匹配。

下面是一个示例,演示如何判断字符串((()))中的括号是否匹配:

  1. 初始化一个空栈。
  2. 从左到右扫描字符串中的每个字符。
  3. (是左括号,将其压入栈中。
  4. (是左括号,将其压入栈中。
  5. (是左括号,将其压入栈中。
  6. )是右括号,弹出栈顶元素(
  7. )是右括号,弹出栈顶元素(
  8. 是右括号,弹出栈顶元素(`。
  9. 扫描完毕后,如果栈为空,则括号匹配。

下是Python代码实现括号匹配:

def par_checker(symbol_string):
    # 初始化一个空栈
    s = Stack()

    for symbol in symbol_string        if symbol == '(':
            # 如果当前字符是左括号,将其压入栈中
            s.push(symbol)
        else:
            # 如果当前字符是右括号,弹出栈顶元素。如果栈顶元素不是相应的左号,则括号不匹配
            if s.is_empty():
                return False
            else:
                s.pop()

    # 扫描完毕后,如果栈为空,则括号匹配
    return s.is_empty()

示例说明

下面是两个示例,演示如何使用栈实现中缀表达式转后缀表达式和后缀表达式求值:

示例1:中缀表达式转后缀表达式

def infix_to_postfix(infix_expr):
    # 运算符优先级
    prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
    # 初始化一个空栈和一个空列表
    op_stack = []
    postfix_list = []
    # 将中缀表达式转换为列表
    infix_list = infix_expr.split()

    for token in infix_list:
        if token.isdigit():
            # 如果当前元素是数字,将其添加到输出列表中
            postfix_list.append(token)
        elif token == '(':
            # 如果当前元素是左括号,将其压入栈中
            op_stack.append(token)
        elif token == ')':
            # 如果当前元素是右括号,则将栈中的元素弹出并添加到列表中,直到遇到左括号
            top_token = op_stack.pop()
            while top_token != '(':
                postfix_list.append(top_token)
                top_token = op_stack.pop()
        else:
            # 如果当前元素是运算符
            while op_stack and prec[op_stack[-1]] >= prec[token]:
                # 比较其与栈顶运算符的优先级
                postfix_list.append(op_stack.pop())
            op_stack.append(token)

    # 将栈中剩余的运算符弹出并添加到输出列表中
    while op_stack:
        postfix_list.append(op_stack.pop())

    # 输出列表中的元素就是后缀表达式
    return ' '.join(postfix_list)

infix_expr = '3 + 4 * 5'
postfix_expr = infix_to_postfix(infix_expr)
print(postfix_expr)  # 输出:3 4 5 * +

在个示例中,我们使用栈实现了中缀表达式转后缀表达式。我们将中缀表达式3 + 4 * 5转换为后缀表达式3 4 5 * +

示例2:后缀表达式求

def postfix_eval(postfix_expr):
    # 初始化一个空栈
    operand_stack = []
    # 将后缀表达式转换为列表
    postfix_list = postfix_expr.split()

    for token in postfix_list:
        if token.isdigit():
            # 如果当前元素是数字,将其压入栈中
            operand_stack.append(int(token))
        else:
            # 如果当前元素是运算符,弹出栈顶的两个元素,进行运算,并将结果压入栈中
            operand2 = operand_stack.pop()
            operand1 = operand_stack.pop()
            result = do_math(token, operand1, operand2)
            operand_stack.append(result)

    # 栈中只剩下一个元素,即为后缀表达式的计算结果
    return operand_stack.pop()

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

postfix_expr = '3 4 5 * +'
result = postfix_eval(post_expr)
print(result)  # 输出:23

在这个示例中,我们使用栈实现了后缀表达式求值。我们计算后缀表达式3 45 * +的值,结果为23

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python数据结构与算法中的栈详解(3) - Python技术站

(0)
上一篇 2023年5月14日
下一篇 2023年5月14日

相关文章

  • Python中利用Scipy包的SIFT方法进行图片识别的实例教程

    Python中利用Scipy包的SIFT方法进行图片识别是一项比较具有参考意义的技术。下面,我将会详细介绍如何进行这项操作,包括步骤、代码示例以及注意事项等。 步骤 Python中利用Scipy包的SIFT方法进行图片识别的主要步骤如下: 导入必要的包和模块,包括cv2、scipy等; 读取原始图像; 对图像进行预处理,包括去噪、灰度化、裁剪等操作; 使用S…

    python 2023年5月18日
    00
  • python提取页面内url列表的方法

    在本攻略中,我们将介绍如何使用Python提取页面内的URL列表。我们将提供两个示例,演示如何使用正则表达式和BeautifulSoup库提取URL列表。 步骤1:获取页面内容 在开始之前,我们需要获取目标页面的内容。我们可以使用Python的requests库或者Scrapy框架来获取页面内容。在本攻略中,我们将使用requests库来获取页面内容。 im…

    python 2023年5月15日
    00
  • 19个Python Sklearn中超实用的隐藏功能分享

    关于“19个Python Sklearn中超实用的隐藏功能分享”的完整攻略 1. 背景介绍 Sklearn是Python科学计算中一个非常重要的库,它集成了各种机器学习算法,同时还提供了许多辅助工具,用于数据的预处理、模型选择和评估。本攻略主要分享Sklearn中的一些隐藏功能,帮助大家更好的使用和理解这个库。 2. 隐藏功能介绍 2.1. 随机森林的fea…

    python 2023年6月3日
    00
  • python向量化与for循环耗时对比分析

    针对这个话题,我给出一份完整的攻略,供参考。 一、背景介绍 在使用Python进行科学计算的过程中,常常涉及数据的向量化运算(向量化表示可以同时操作整个向量的计算)。而在Python中,想要实现向量化操作,通常使用NumPy库,它提供高性能的多维数组对象以及相关计算工具。 而在NumPy中,可以使用矩阵和向量的运算,使得代码看起来更加简洁、方便,也能够提高代…

    python 2023年6月3日
    00
  • Python的加密模块md5、sha、crypt使用实例

    Python的加密模块md5、sha、crypt使用实例 本文将给出Python中三种加密模块:md5、sha、crypt 的使用实例,分别介绍各自的作用、使用方法和实例应用。 md5模块 md5模块是Python的一个常用的加密模块,主要用于数据校验、数字签名等场景。 md5加密模块常用于生成摘要值,可以将任意一种消息数据(不论大小)传输为一种长度固定的算…

    python 2023年6月3日
    00
  • python简单获取数组元素个数的方法

    当我们在使用Python编程时,经常会遇到需要获取数组中元素的数量的情况。这里列举了三种获取数组元素数量的方法。 方法1: len()函数 在Python中,可以使用内置函数len()来获取数组/列表的元素个数。 # 示例1:使用len()函数获取列表的元素个数 my_list = [1, 2, 3, 4, 5] list_length = len(my_l…

    python 2023年6月5日
    00
  • Python实现批量文件整理的示例代码

    Python实现批量文件整理是一种非常实用的技能,能够帮助我们在日常使用中提高文件整理的效率。下面我将为大家提供一份Python实现批量文件整理的示例代码,希望能对大家有所帮助。 什么是批量文件整理? 批量文件整理是指将多个文件按照一定的规则进行分类、重命名、复制、删除等操作的过程。批量文件整理可以通过手动操作来完成,但是当文件数量较大时,手动操作无疑会十分…

    python 2023年6月5日
    00
  • Python制作一个随机抽奖小工具的实现

    接下来我将为你详细讲解“Python制作一个随机抽奖小工具的实现”的完整攻略,包含以下步骤: 第一步:安装必要的库 安装random库:pip install random 第二步:准备数据 假设我们要从以下5名学生中进行抽奖:张三、李四、王五、赵六、钱七。 我们需要将这5名学生的信息存储在一个列表中,代码如下: students = ["张三&q…

    python 2023年5月20日
    00
合作推广
合作推广
分享本页
返回顶部