全网最详细数据结构----中缀转后缀

举报
是Dream呀 发表于 2022/01/10 22:57:18 2022/01/10
【摘要】 最详细的中缀转后缀 学渣们请就座:(不用看别人,说的就是你!) 大家好,我是Dream。此时此刻我只想说:男神可以迟到,但永远不会缺席!那个男人回来了!!! 最近眼发炎了,非常难受,但这不会阻止我为大...

最详细的中缀转后缀

学渣们请就座:(不用看别人,说的就是你!)在这里插入图片描述
大家好,我是Dream。此时此刻我只想说:男神可以迟到,但永远不会缺席!那个男人回来了!!!在这里插入图片描述

最近眼发炎了,非常难受,但这不会阻止我为大家更新文章的,请把 泪目 打在评论区!!!
在这里插入图片描述

话不多说,今天给大家介绍一下,中缀表达式如何转后缀表达式。
现在,肯定会有学渣问:什么是中缀和后缀表达式呢?

我只想说:你好优秀,请前排就坐~在这里插入图片描述
简单来讲,中缀表达式就是我们学习数学时的各种表达式,
such as:(A+B)*C/(D-E)
什么是后缀表达式呢?就是将运算符移动到字符串后面,但也不是全部移动到后面,当然也是有条件和顺序的。
我们都知道运算符是有优先级的,比如乘号的优先级就高于加号的优先级,那就要在同一运算区域下先移动乘号再移动加号,为什莫说在同一领域下呢,因为我们都知道在运算中少不了括号的存在,那么括号就界定了属不属于同一领域下。
算了,不和你们多BB了,举个例子吧:
A+B : AB+
A+B *C : ABC *+
(A+B) *(C+D) : AB+CD+ *
emmm,我猜你还是不懂应该(仅代表学渣)
在这里插入图片描述
好吧,前两个你应该懂了吧(不懂的同学回家默写三千遍三字经)
那我来讲一下第三个:首先(A+B) *(C+D)可以写作((A+B) *(C+D))没有问题吧,先看第一层括号,第一层括号中只有两个小括号和一个 *,那么好的将最外层右边的括号用乘号替换掉,左边括号删除,即:(A+B) (C+D) *
同理看第二层括号,同样方法,运算符替换掉右边括号,同时删除左边括号,即:AB +(C+D) *----AB +CD+ *得到了最终答案, 是不是very easy?那你会用代码表示吗???哈哈哈,继续!

首先调用栈和string:

from pythonds3.basic import Stack
import string
  
 

定义一个函数:

def infix_to_postfix(infix):
    """将中序表达式转化为后序表达式,核心思想"""

  
 

这里定义了一个栈来储存运算符,一个列表来储存得到的表达式。
最后将得到的列表用join函数合并成一个字符串
当出现括号左时入栈,字符串照常输出在列表中,运算符继续入栈,当出现有括号时运算符出栈,直至遇到最初的左括号才停止出栈!就这样循环往复遍历,直至遍历结束。

in_list = infix.split()  # 将字符串变为列表,注意,输入时需要空格隔开单个元素,例:"1 2 3 * 2 3"
    stack1 = Stack()  # 创建空栈,用于存储遍历字符串列表的括号、操作符
    post_list = []  # 创建空列表,用于存储后序表达式
    priority = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}  # 创建优先级字典
    for elem in in_list:  # 遍历中序表达式
        if elem == '(':  # 为左括号,入栈
            stack1.push(elem)
        elif elem in string.ascii_uppercase:  # 为字符串里的大写字母,加入空的输出列表
            post_list.append(elem)
        elif elem == ')':  # 为右括号,则出栈,添加到输出列表,直到匹配到左括号
            token = stack1.pop()
            while token != '(':
                post_list.append(token)
                token = stack1.pop()
        else:  # 为操作符,则判断栈中是否有更高优先级的操作符,有则出栈,无则添加到列表尾部,
            while (not stack1.is_empty()) and (priority[stack1.peek()] >= priority[elem]):
                post_list.append(stack1.pop())
            stack1.push(elem)  # 若放到列表尾部,则栈永远不会有操作符
    while not stack1.is_empty():  # 若栈不为空,则弹出到后续表达式列表(即优先级低的放最后)
        post_list.append(stack1.pop())

    return ''.join(post_list)  # 将列表连在一起
if __name__ == '__main__':
print(infix_to_postfix("A * B + ( C + D ) * ( E - F )"))
  
 

emmm,这就是今天我和大家分享的东西了。
如果你喜欢的话,就不要吝惜你的一键三连了~
在这里插入图片描述

文章来源: xuyipeng.blog.csdn.net,作者:是Dream呀,版权归原作者所有,如需转载,请联系作者。

原文链接:xuyipeng.blog.csdn.net/article/details/118057813

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。