中序表达四变为后序表达式
from pythonds.basic import Stackimport 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 >= dict1:
poslist.append(opstack.pop())
opstack.push(token)
while not opstack.isEmpty():
poslist.append(opstack.pop())
return "".join(poslist)
print(hanshu('( ( A+ B ) * D ) * N'))
有哪位大神能解释一下这段代码的实现原理，与逻辑，本人看不懂 这段代码实现的是将中序表达式转化为后序表达式。下面是代码的具体实现原理和逻辑。
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*”。
希望以上解释可以帮助您理解这段代码的实现原理和逻辑。 这段代码实现了将中缀表达式转换为后缀表达式的功能。
程序首先定义一个字典`dict1`，存储了运算符的优先级，包括：乘法、除法、加法、减法和左右括号。然后从输入的中缀表达式中逐个读取字符：
- 如果当前字符是大写字母，则将其加入到后缀表达式的列表中。
- 如果当前字符是左括号，则将其压入到运算符栈中。
- 如果当前字符是右括号，则一次弹出运算符栈中的元素，直到遇到左括号，将这之间的运算符加入到后缀表达式的列表中。
- 如果当前字符是运算符，则如果其优先级小于等于栈顶元素，就将栈顶元素弹出并加入到后缀表达式的列表中，再将当前运算符压入栈中。
当中缀表达式中的所有元素都处理完后，将运算符栈中剩余的运算符弹出，依次加入到后缀表达式的列表中。最后将后缀表达式列表中的元素依次连接成字符串，就得到了后缀表达式。
这个算法的思想是基于运算符优先级来实现的。因为后缀表达式中没有括号，只有运算符和操作数，所以可以通过比较运算符的优先级来确定顺序。具体来说：
- 如果栈为空，则直接将当前运算符压入栈中；
- 否则，将当前运算符与栈顶元素（即优先级最高的运算符）进行比较：
- 如果当前运算符的优先级大于栈顶元素，则将其压入栈中；
- 否则，不断弹出栈顶元素并加入到后缀表达式中，直到栈为空或栈顶元素的优先级小于当前运算符，最后将当前运算符压入栈中。
这样处理后，栈中的运算符就按照优先级从高到低依次排列，即栈底是优先级最高的运算符，栈顶是优先级最低的运算符。从栈中依次弹出这些运算符，就可以得到后缀表达式了。
页:
[1]