中序表达四变为后序表达式

davidmou

from pythonds.basic import Stack
import string

def hanshu(n):
    dict1 = {}
    dict1["*"] = 3
    dict1["/"] = 3
    dict1["+"] = 2
    dict1["-"] = 2
    dict1["("] = 1

    opstack = Stack()
    poslist = []

    tokenlist = n.split()
    for token in tokenlist:
        if token in string.ascii_uppercase:
            poslist.append(token)

        elif token == "(":
            opstack.push(token)

        elif token == ")":
            toptoken = opstack.pop()
            while toptoken != "(":
                poslist.append(toptoken)
                toptoken = opstack.pop()
        else:
            while not (opstack.isEmpty()) and dict1[opstack.peek()] >= dict1[token]:
                poslist.append(opstack.pop())
            opstack.push(token)

    while not opstack.isEmpty():
        poslist.append(opstack.pop())

    return "".join(poslist)


print(hanshu('( ( A  + B ) * D ) * N'))

有哪位大神能解释一下这段代码的实现原理，与逻辑，本人看不懂

isdkz

这段代码实现的是将中序表达式转化为后序表达式。下面是代码的具体实现原理和逻辑。

1. 定义一个字典dict1，用于存储操作符的优先级，其中"*"和"/"的优先级最高，"+"和"-"的优先级次之，"("的优先级最低。

2. 定义一个栈opstack和一个列表poslist，用于存储操作符和操作数。

3. 将中序表达式转化为tokenlist，然后遍历tokenlist。

4. 如果token是一个大写字母，则将其添加到poslist中。

5. 如果token是"("，则将其压入opstack中。

6. 如果token是")"，则将opstack中的操作符弹出，直到遇到"("，将这些操作符添加到poslist中。

7. 如果token是操作符，则将opstack中的操作符弹出，直到遇到优先级比当前操作符低的操作符，然后将当前操作符压入opstack中。

8. 遍历完tokenlist后，将opstack中的操作符全部弹出，添加到poslist中。

9. 最后将poslist中的元素连接起来，得到后序表达式。

例如，对于中序表达式"( ( A + B ) * D ) * N"，按照上述步骤，得到的后序表达式为"AB+D*N*”。

希望以上解释可以帮助您理解这段代码的实现原理和逻辑。

Mike_python小

这段代码实现了将中缀表达式转换为后缀表达式的功能。

程序首先定义一个字典`dict1`，存储了运算符的优先级，包括：乘法、除法、加法、减法和左右括号。然后从输入的中缀表达式中逐个读取字符：

- 如果当前字符是大写字母，则将其加入到后缀表达式的列表中。
- 如果当前字符是左括号，则将其压入到运算符栈中。
- 如果当前字符是右括号，则一次弹出运算符栈中的元素，直到遇到左括号，将这之间的运算符加入到后缀表达式的列表中。
- 如果当前字符是运算符，则如果其优先级小于等于栈顶元素，就将栈顶元素弹出并加入到后缀表达式的列表中，再将当前运算符压入栈中。

当中缀表达式中的所有元素都处理完后，将运算符栈中剩余的运算符弹出，依次加入到后缀表达式的列表中。最后将后缀表达式列表中的元素依次连接成字符串，就得到了后缀表达式。

这个算法的思想是基于运算符优先级来实现的。因为后缀表达式中没有括号，只有运算符和操作数，所以可以通过比较运算符的优先级来确定顺序。具体来说：

- 如果栈为空，则直接将当前运算符压入栈中；
- 否则，将当前运算符与栈顶元素（即优先级最高的运算符）进行比较：
  - 如果当前运算符的优先级大于栈顶元素，则将其压入栈中；
  - 否则，不断弹出栈顶元素并加入到后缀表达式中，直到栈为空或栈顶元素的优先级小于当前运算符，最后将当前运算符压入栈中。

这样处理后，栈中的运算符就按照优先级从高到低依次排列，即栈底是优先级最高的运算符，栈顶是优先级最低的运算符。从栈中依次弹出这些运算符，就可以得到后缀表达式了。