基本概念

  • 逆波兰式：用比较通俗的语言来讲，就是将多项式的操作数和符号重新排列，操作数在前，符号在后
  • 栈：这种数据结构是一种特殊的线性表，只能在一头进行插入和删除，所以有着先进后出的特点

算法实现

  • 中缀式转逆波兰式

需要一个符号栈，初始为空，遍历多项式的每项，如果是数字，记录进结果，如果是符号，判断当前符号和栈顶符号的优先级（括号 < + - < * /），如果优先级大于栈顶符号，则进栈；如果优先级小于栈顶符号，栈顶出栈，如果出栈的不是括号，记录至结果中，直至栈顶优先级小于当前符号，而后符号进栈，直至遍历完整个表达式，最后将符号栈中的符号出栈记录至结果

  • 计算逆波兰式

需要一个结果栈，初始为空，遍历逆波兰式，如果是数字，进栈，遇到符号，出栈两个操作数，进行计算并将计算结果进栈，直至遍历完成，此时栈顶为表达式结果

代码实现

stack.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import readline
import time
expression = input("请输入表达式(每个字符用空格隔开):")
expression = expression.split()

def get_Reverse_Polish_Notation(expression):
    '''转化逆波兰式'''
    stack = list()
    result = list()
    symbol = ['(', ')', '+', '-', '*', '/']
    value = {
        '(':1,
        ')':1,
        '+':2,
        '-':2,
        '*':3,
        '/':3,
    }
    for i in expression:
        #如果元素是数字,直接进栈
        if i.isdigit():
            result.append(i)
        #如果元素是符号,进入判断
        if i in symbol:
            #如果栈不为空,则判断符号优先级
            if stack:
                #判断如果符号优先级不高于栈顶符号优先级,则出栈,直至优先级大于栈顶符号
                if value[i] <= value[stack[-1]] and i != '(':
                    #如果符号为右括号,则进行匹配左括号
                    if i == ')':
                        while stack[-1] != '(':
                            result.append(stack.pop())
                        stack.pop()
                    #如果不是右括号,则进行出栈操作,直到大于栈顶符号为止
                    else:
                        while True:
                            result.append(stack.pop())
                            if stack:
                                if value[i] > value[stack[-1]] :
                                    stack.append(i)
                                    break
                            else:
                                    stack.append(i)
                                    break

                #如果大于栈顶符号,直接进栈
                else:
                    stack.append(i)
            #如果初始栈为空,则直接进栈第一个符号
            else:
                stack.append(i)
    #遍历完整个表达式,将栈中剩余的符号出栈
    while stack:
        result.append(stack.pop())
    #返回结果列表
    return result

def count_result(result):
    '''计算逆波兰式'''
    stack = list()
    #遍历逆波兰式,如果是数字,直接进栈,如果是符号,则出栈两个操作数,计算出结果入栈
    for i in result:
        if i.isdigit():
            stack.append(i)
        else:
            if i == '+':
                temp = float(stack[-2]) + float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
            elif i == '-':
                temp = float(stack[-2]) - float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
            elif i == '*':
                temp = float(stack[-2]) * float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
            elif i == '/':
                temp = float(stack[-2]) / float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
    return float(stack[-1])