Python栈的应用：中序表达式转前序表达式

# 定义运算符优先级
precedence = {
    '^': 3,
    '*': 2,
    '/': 2,
    '+': 1,
    '-': 1,
    '(': 0
}

# 将中序表达式转换为前序表达式
def infix_to_prefix(expression):
    stack = []
    prefix = ''
    # 倒序遍历中序表达式
    for char in reversed(expression):
        if char in precedence:
            # 弹出栈顶两个元素
            if len(stack) >= 2:
                op1 = stack.pop()
                op2 = stack.pop()
                # 将操作符和元素组成一个新的字符串
                new_str = char + op2 + op1
                # 将新的字符串压入栈中
                stack.append(new_str)
            else:
                return 'Invalid infix expression!'
        elif char == ')':
            # 将右括号压入栈中
            stack.append(char)
        elif char == '(':
            # 弹出栈中的左括号和与之匹配的右括号
            while stack[-1] != ')':
                prefix += stack.pop()
            stack.pop()
        else:
            # 将操作数压入栈中
            stack.append(char)
    # 将剩余的元素弹出栈并加入到前缀表达式中
    while len(stack) > 0:
        prefix += stack.pop()
    return prefix

# 测试代码
expression = 'pidancode.com*(5+5)-5'
print(infix_to_prefix(expression))
# 输出: -*pidancode.com+5 5 5

expression = '(A+(B*C))*D'
print(infix_to_prefix(expression))
# 输出: *+A*BCD

-*pidancode.com+5 5 5
*+A*BCD