算法: 中缀表达式->后缀表达式

解析:

作者:张一极

Date:20200928

定义优先级,括号的优先级最高

使用栈数据结构,分割要处理的字符串

循环遍历每个字符,如果是被处理元素(字母或者数字),则加入输出列表

如果是括号,则括号压栈,如果是反括号,则触发连续弹栈先取出栈顶元素,不断弹栈

直到取到另一个括号,如果不是括号也不是字母数字

则比较其优先级,如果栈顶优先级大于token的优先级

则弹出栈顶元素(先行计算),直到栈顶元素优先级小于token的优先级为止

最后所有字符都遍历一遍过后,检查栈是否为空,将剩余较低优先级的数据弹出.

Code:

x
1
def infixToPostfix(data_to_count):
2
    prec = {}
3
    prec["*"] = 3
4
    prec["/"] = 3
5
    prec["+"] = 2
6
    prec["-"] = 2
7
    prec["("] = 1
8
    data_process = data_to_count.split(" ")
9
    print(data_process)
10
    stack = []
11
    postfixList = []
12
    for token in data_process:
13
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
14
            postfixList.append(token)
15
        elif token=='(':
16
            stack.append(token)
17
        elif token ==')':
18
            top_ele = stack.pop()
19
            while top_ele !='(':
20
                postfixList.append(top_ele)
21
                top_ele = stack.pop()
22
        else:
23
            while (len(stack)!=0) and prec[stack[-1]]>=prec[token]:
24
                postfixList.append(stack.pop())
25
            stack.append(token)
26
    while len(stack)!=0:
27
        postfixList.append(stack.pop())
28
    print(postfixList)
29
infixToPostfix("( A + B ) * C - ( D - E ) + ( F + G )")

Deffence:python-data-structure-cn