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:通配符查找、拷贝文件的操作

    在Python中,我们可以使用通配符来查找和拷贝文件。本文将详细介绍如何使用通配符在Python中查找和拷贝文件。 通配符查找文件 在Python中,我们可以使用glob模块来查找文件。glob模块提供了一个函数glob(),它接受一个通配符模式作为参数,并返回匹配该模式的所有文件的列表。 以下是一个示例: import glob files = glob.…

    python 2023年5月14日
    00
  • 浅谈Python的格式化输出

    现在我们来详细讲解Python的格式化输出。 格式化输出的基础 在Python中,我们可以使用内置的print()函数来将内容输出到控制台。输出的内容可以是文本、数字、变量等等。 例如,当我们想要输出一个字符串时,我们可以这样做: print("Hello World!") 这会在控制台上输出字符串 “Hello World!”。 但是在…

    python 2023年6月5日
    00
  • Python专用方法与迭代机制实例分析

    Python专用方法与迭代机制实例分析 1. 什么是Python专用方法? 在Python中,有一些特殊方法(也称为“魔法方法”或“双下划线方法”),用于自定义类的行为和操作。这类方法通常以两个下划线开头,并以两个下划线结束。比如__init__、__str__、__eq__等。 这些方法使用起来很方便,并且可以大大提高代码的灵活性和可读性。比如:如果需要比…

    python 2023年6月6日
    00
  • python matplotlib 绘图 和 dpi对应关系详解

    下面是“python matplotlib 绘图 和 dpi对应关系详解”的完整攻略。 什么是dpi? DPI是dots per inch的缩写,意为每英寸点数,表示每英寸内有多少个像素点。在matplotlib中,dpi通常指的是一个图像的每英寸点数,控制着图片的分辨率。 dpi和图像质量的关系 dpi越高,图像质量越好,图像也会变得更加清晰。但是,同时也…

    python 2023年5月18日
    00
  • python列表元素拼接成字符串的4种方法

    以下是关于“python列表元素拼接成字符串的4种方法”的完整攻略。 方法1:使用join()函数 在Python中,可以使用join()函数将一个列表中的元素拼接成一个字符串。该函数定义在字符串类型中,用法如下: str = separator.join(iterable) 其中,separator为拼接的分隔符,iterable为被拼接的列表对象。下面是…

    python 2023年6月5日
    00
  • Python ValueError: invalid literal for int() with base 10 实用解决方法

    Python中的ValueError异常通常是由于数据类型不匹配,或者输入数据格式错误等原因引起的。其中,invalid literal for int() with base 10错误表示给int()函数传递了无效参数。本篇攻略将针对此错误进行详细讲解,提供实用解决方法,希望能帮助您排除类似问题。 什么是PythonValueError: invalid …

    python 2023年5月13日
    00
  • 如何在Python中进行双向方差分析

    双向方差分析是用于检验两种因素对于因变量的影响是否相互作用的一种统计方法。在Python中,我们可以使用 statsmodels 库对数据进行双向方差分析。下面是进行双向方差分析的详细攻略,包含两条示例说明。 步骤1:导入所需的库 在进行双向方差分析之前,需要导入所需的Python库,包括pandas、statsmodels.formula.api等。 im…

    python-answer 2023年3月25日
    00
  • python实现模拟器爬取抖音评论数据的示例代码

    下面是Python实现模拟器爬取抖音评论数据的完整攻略。 1. 环境准备 1.1 安装Python 首先需要在本地电脑上安装Python,并配置好环境变量。可以到Python 官网下载最新的稳定版本,并按照向导进行安装。 1.2 安装浏览器驱动 抓取抖音评论数据需要用到浏览器模拟器,所以还需要安装对应的浏览器驱动。这里以Chrome为例,大家可以到Chrom…

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