PTA习题：表达式转换----请设计程序将中缀表达式转换为后缀表达式。（用python编写）

给一个PTA题目链接
由于个人学业不得不做一些PTA作业，突然发现这道PTA题比较经典，于是打算写篇博客来记录一下，写的不好请多多担待QAQ。
注：下面你有可能碰到一个概念–标准输出流，它可以理解为屏幕，终端

题目描述：

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。

输出格式:

在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +

题解：

先贴代码：

s = '(' + input().strip() + ') '
opt = []
grate = {
    '-': 2, '+': 2,
    '*': 3, '/': 3,
    '(': 1, ')': 1
}
ans = ''
while True:
    if not s: break #输入结束，退出循环
    if s[0] == ' ':pass #若是空格则直接跳过
    elif s[0] == '(':
        opt.append(s[0]) #左括号入栈
        if s[1] == '-': #对操作数前面符号的判断，若是则输出
            ans += '-'
            s = s[1:]
        elif s[1] == '+':#可能为首的操作数前面会有一个‘+’号,若是则直接跳过
            s = s[1:]
    elif s[0] == ')':
        while opt[-1] != '(':  #输出左括号后所有的操作符
            ans += opt[-1] + ' '
            opt = opt[:-1]
        opt = opt[:-1] #弹出左括号
    elif s[0].isdigit(): #对操作数的判断
        data = ''
        while s[0].isdigit() or s[0] == '.': #可能为浮点数（即小数）
            data += s[0]
            s = s[1:]
        ans += data + ' '
        continue
    else: #对除括号以外操作符的判断
        while grate[s[0]] <= grate[opt[-1]]:
            ans += opt[-1] + ' '
            opt = opt[:-1]
        opt.append(s[0]) #操作符入栈
    s = s[1:]
ans = ans.strip()
print(ans, end='')

说明：这里我直接把要输出的内容写入到了ans变量里面，免得再写多余的部分来弄一些乱七八糟的输出格式问题，输出时直接对ans进行格式一下就OK了

好了，开始讲解

中缀表达式转后缀即逆波兰表达式，需要 两 三 个步骤：

1. 遇到操作数直接输出
2. 栈顶运算符可运算时输出栈顶运算符（这里我们也是用栈来储存运算符，然后来判断输出）
3. 重复以上步骤直至输入结束

第一步很简单，直接输出，我们都懂。但要说明的是，这个输出既可以是定向到标准输出流，还可以是一个队列，一个栈。第三步也好理解，就是外加一个循环嘛。接下来我们来重点讲解第二步。

那么，什么时候运算符可运算呢？我们首先需要确定运算符优先级¹，准确的说应该是运算符输出优先级²。运算符输入不需要优先级，它们到最后总是要入栈的，但我们需要对括号进行特判，这个是例外，并且它涉及到了操作数的前面的正负问题。完成优先级排序后，我们就有了运算符的出栈依据。当栈顶运算符优先级比将要入栈的运算符优先级要高时，我们就可以弹出（即输出）该栈顶运算符。

而对括号的那部分我们还需要进行详细的解释：

1. 我们知道，操作数前面可能有正负号来影响你，但我们还应该知道，除了式子开头以外，只有括号里面的表达式才有可能出现操作数前面的正负号。 那么我们可以很自然的将操作数的正负号放入到左括号的判断逻辑中。那么，如果我们在整个式子外加一对括号的话，我们连开头的正负号都可以归入到左括号的判断逻辑里面了。
2. 接下来是对括号出入栈的说明³： 当碰到左括号了直接入栈，不论栈顶操作符的优先级多大；当碰到右括号时输出所有的运算符，直到碰到了左括号，然后弹出左括号但不输出到标准输出流中。

细节

接下来走一下代码逻辑的一些细节，我们就结束了。

• 把要输出的内容写入到了ans变量里面，免得再写多余的部分处理输出格式问题，输出时直接对ans进行格式化
• 我们在式子整体的外面加了一对括号，便于判断
• 我们把操作数前正负号的判断放入了左括号的判断逻辑中
• 操作数可能有浮点数，请注意我们对数字判断的那一部分

---

1. 你当然可以不进行优先级排序，用大量的if语句来替代，然后让你的代码量骤增 ↩︎

2. 这里使用了一个字典来作为优先级比较依据 ↩︎

3. 出栈可以代表是输出到标准输出流中 ↩︎

转载：https://blog.csdn.net/San__Qi/article/details/101907175