ZH奶酪：Python 中缀表达式转换后缀表达式

实现一个可以处理加减乘数运算的中缀表达式转换后缀表达式的程序：

一个输入中缀表达式inOrder

一个输出池pool

一个缓存栈stack

从前至后逐字读取inOrder

首先看一下不包含括号的：

（1）操作数：直接输出到pool

（2）操作符：判断当前操作符与stack[top]操作符的优先级

　　<1>当前操作符优先级高于stack[top]：将当前操作符添加到stack中；

　　<2>当前操作符优先级低于或等于stack[top]：从stack[top]开始出栈，直到stack[top]优先级高于当前操作符，然后将当前操作符入栈；

（3）当inOrder遍历结束，如果stack非空，反转stack，添加到pool尾

 1 __author__ = 'ZhangHe'
 2 def in2post(inOrder):
 3     pool = ''
 4     stack = ''
 5     for i in inOrder:
 6         ret = proc(i,switch(i),stack,pool)
 7         stack = ret['stack']
 8         pool = ret['pool']
 9     if stack != '':
10         stack = stack[::-1]
11     return pool+stack
12 
13 def switch(c):
14     operator1 = '+-'
15     operator2 = '*/'
16     num = 'abcdefg'
17     if c in num:
18         return 0
19     if c in operator1:
20         return 1
21     if c in operator2:
22         return 2
23 def proc(c,op,stack,pool):
24     top = len(stack)-1
25 
26     if op == 0:#abcdefg
27         pool += c
28     if op == 2 or op==1:#*
29         if top == -1:
30             stack += c
31         elif switch(stack[top]) < op:
32             stack += c
33         else:
34             while top != -1 and switch(stack[top]) >= op:
35                 pool += stack[top]
36                 top -= 1
37             if top != -1:
38                 stack = stack[0:top+1]
39             else:
40                 stack = ''
41             stack += c
42     ret = {
43         'stack':stack,
44         'pool':pool
45     }
46     return ret
47 inOrder = 'a+b*c-d*e+f/g'
48 print in2post(inOrder)

当包含括号的时候应该考虑哪些因素呢？

在上个程序的基础上，进一步考虑下边的几点：

（4）加入括号之后，“(”拥有最高优先级，也就是说，遇到“（”就放到stack中就好了；

（5）遇到“）”的操作也比较简单，直接把stack中的元素逐一弹出到pool，直到弹出“（”；

此时需要新的操作符规则：

（5）操作符：判断当前操作符与stack[top]操作符的优先级

　　<1>当前操作符优先级高于stack[top]或者stack[top]==‘（’：将当前操作符添加到stack中；

　　<2>当前操作符优先级低于或等于stack[top]：从stack[top]开始出栈，直到stack[top]优先级高于当前操作符或者stack[top]为“（”，然后将当前操作符入栈；

 1 __author__ = 'ZhangHe'
 2 def in2post(inOrder):
 3     pool = ''
 4     stack = ''
 5     for i in inOrder:
 6         ret = proc(i,switch(i),stack,pool)
 7         stack = ret['stack']
 8         pool = ret['pool']
 9     if stack != '':
10         stack = stack[::-1]
11     return pool+stack
12 
13 def switch(c):
14     operator1 = '+-'
15     operator2 = '*/'
16     operator3 = ')'
17     operator4 = '('
18     num = 'abcdefg'
19     if c in num:
20         return 0
21     if c in operator1:
22         return 1
23     if c in operator2:
24         return 2
25     if c in operator3:
26         return 3
27     if c in operator4:
28         return 4
29 def proc(c,op,stack,pool):
30     top = len(stack)-1
31 
32     if op == 0:#abcdefg
33         pool += c
34     if op == 2 or op==1:#*
35         if top == -1:
36             stack += c
37         elif switch(stack[top]) < op or stack[top] == '(':
38             stack += c
39         else:
40             while top != -1 and switch(stack[top]) >= op and switch(stack[top])<switch(')'):
41                 pool += stack[top]
42                 top -= 1
43             if top != -1:
44                 stack = stack[0:top+1]
45             else:
46                 stack = ''
47             stack += c
48     if op == 3:#)
49         while top!= -1 and stack[top] != '(':
50             pool += stack[top]
51             top -= 1
52         stack = stack[0:top]
53     if op == 4:#(
54         stack += c
55     ret = {
56         'stack':stack,
57         'pool':pool
58     }
59     return ret
60 # inOrder = 'a+b*c-d*e+f/g'
61 inOrder = 'a+b*c+(d*e+f)*g'
62 print in2post(inOrder)

输出：

abc*+de*f+g*+