Python使用栈将中序转后序（代码）

这里使用字母来表示数字

# 从中序表达式到后序表达式的转换
# string模块中定义了一些常用的属性（包含所有数字，字母，可打印的所有ascii码等）
from pythonds.basic import Stack  # 引入栈
import string


def infix_to_postfix(infix_expr):
    prec = {}  # 用字典存优先级
    # precedence优先;优先权
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1

    op_stack = Stack()
    # 实例化一个栈
    postfix_list = []
    # 建一个列表用于存放字母

    # token_list = infix_expr.split()
    token_list = list(infix_expr)
    # 将传入的字符进行切片存入列表

    for token in token_list:  # 依次取出列表的内容
        if token in string.ascii_uppercase:
            # string.ascii_uppercase代表'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
            postfix_list.append(token)  # 将字母加入列表
        elif token == '(':
            op_stack.push(token)  # 入栈
        elif token == ')':
            top_token = op_stack.pop()  # 将最上端出栈同时存入到top_token中
            while top_token != '(':  # 如果没有匹配成功，应该就是运算符
                postfix_list.append(top_token)  # 将运算符加入列表
                top_token = op_stack.pop()  # 再取出最上端出栈同时存入到top_token中
        else:
            while (not op_stack.isEmpty()) and (prec[op_stack.peek()] >= prec[token]):
                # 如果栈内有东西并且栈顶端的优先级大于等于当前读入的token的优先级
                postfix_list.append(op_stack.pop())
                # 将栈内的顶端出栈并且存入列表
            op_stack.push(token)
            # token入栈

    while not op_stack.isEmpty():  # 如果栈不是空的
        postfix_list.append(op_stack.pop())
        # 将栈内的东西出栈添加在列表后面

    return " ".join(postfix_list)  # 将列表各元素用空格拼接


print(infix_to_postfix("(A+B)*(C+D)"))
print(infix_to_postfix("(A+B)*C"))
print(infix_to_postfix("(A+(B+D)*E)*C"))

下面使用数字来实现

from pythonds.basic import Stack


def infix_to_postfix(infix_expr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    op_stack = Stack()
    postfix_list = []

    # tokenList = infixexpr.split()
    token_list = list(infix_expr)
    numb = 0
    for token in token_list:
        if token in "0123456789":
            numb = numb * 10 + int(token)  # 这里针对多位数
        else:
            if numb != 0:
                postfix_list.append(numb)
                numb = 0
            if token == '(':
                op_stack.push(token)
            elif token == ')':
                top_token = op_stack.pop()
                while top_token != '(':
                    postfix_list.append(top_token)
                    top_token = op_stack.pop()
            else:
                while (not op_stack.isEmpty()) and (prec[op_stack.peek()] >= prec[token]):
                    postfix_list.append(op_stack.pop())
                op_stack.push(token)

    while not op_stack.isEmpty():
        postfix_list.append(op_stack.pop())
    # return postfix_list
    return " ".join(postfixList)