python实现栈的代码回顾
class Stack(object):
# Stack() 创建一个空的新栈。
def __init__(self):
self.items = []
# push(new_item)将一个新的元素添加到栈顶。
def push(self, new_item):
self.items.append(new_item)
# 返回栈顶元素，但不会弹出它。
def top(self)：
return self.items[-1]
# 弹出并返回栈顶元素
def pop(self):
return self.items.pop()
# 返回栈是否为空。栈空返回true，否则返回false。
def isEmpty(self):
return [] == self.items
# 返回栈的长度，即栈中元素的个数。
def size(self):
return len(self.items)
后缀表达式回顾
后缀表达式是计算机科学中的一种常见的数学表达式形式。相比于人类常用的中缀表达，后缀表达式在没有括号的情况下也不会引起运算顺序上的歧义，这是其最重要的优点。
中缀表达式 → 后缀表达式
A+B → AB+
A+BC → ABC+
(A+B)C → AB+C
(A+B)(C+D) → AB+CD+
A+B+C+D → AB+C+D+
中缀表达式转换为后缀表达式
假设表达式中只有大写字母、数字和运算符，如何将一个中缀表达式转换为后缀表达式？
解决这一问题的要点有如下：
- 大写字母和数字的排列顺序，中缀表达式和后缀表达式是相同的。
- 优先级更高的运算符和靠左的同级别运算符应当更早在后缀表达式中出现。
- 括号相当于更高的一个平台，左括号作为平台的开始，右括号作为平台的结束。
class Stack(object):
# Stack() 创建一个空的新栈。
def __init__(self):
self.items = []
# push(new_item)将一个新的元素添加到栈顶。
def push(self, new_item):
self.items.append(new_item)
# 返回栈顶元素，但不会弹出它。
def top(self):
return self.items[-1]
# 弹出并返回栈顶元素
def pop(self):
return self.items.pop()
# 返回栈是否为空。栈空返回true，否则返回false。
def isEmpty(self):
return [] == self.items
# 返回栈的长度，即栈中元素的个数。
def size(self):
return len(self.items)
# 将中缀表达式变换成后缀表达式
# trans_string为传入的待转换的中缀表达式
# op_rank为运算符的优先级，数字越大，优先级越高
def mid2post(trans_string, op_rank):
post_list = [] #创建一个空列表，用于保存生成中的后缀表达式
stack = Stack() #创建一个新的栈用于保存未被输出的运算符
for checking_char in trans_string: #从左到右，逐个遍历中缀表达式中的字符
if checking_char in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789': #当前字符为字母或数字
post_list.append(checking_char) #将字符接入后缀表达式
elif checking_char == '(': #当前符号为左括号
stack.push(checking_char) #将左括号入栈，代表着后面出现的运算符优先级更高
elif checking_char == ')': #当前符号为右括号
top_char = stack.pop()
while top_char != '(': #弹出元素，接入后缀表达式，直到出现配对的左括号
post_list.append(top_char)
top_char = stack.pop()
else: #符号为运算符
while (not stack.isEmpty()) and (op_rank[stack.top()]>=op_rank[checking_char]): #栈不为空，且栈顶符号优先级不低于当前符号
post_list.append(stack.pop()) #弹出这个更靠前的运算符，并接入后缀表达式
stack.push(checking_char) #将运算符压入栈
while not stack.isEmpty(): #当栈未空
post_list.append(stack.pop()) #弹出所有运算符，并接入后缀表达式
return ''.join(post_list) #将列表转换为字符串并返回
def main():
op_rank = {'*':2, '/':2, '+':1, '-':1, '(':0}
string_list = ['A+B', 'A+B*C', '(A+B)*C', '(A+B)*(C+D)', 'A+B+C+D']
for trans_string in string_list:
print("%s --> %s"%( trans_string, mid2post(trans_string,op_rank)))
print("-----------------")
if __name__ == "__main__":
main()
运行结果如下：
A+B --> AB+
-----------------
A+B*C --> ABC*+
-----------------
(A+B)*C --> AB+C*
-----------------
(A+B)*(C+D) --> AB+CD+*
-----------------
A+B+C+D --> AB+C+D+
-----------------
计算后缀表达式
如何高效的计算后缀表达式？
这一问题同样可以使用栈来解决，而且相比之前的转换问题更加简单。
解决这一问题的要点有如下：
- 每当在输入上看到运算符时，计算两个最近的操作数。
- 操作数的先后次序不能变。
我们以最简单的个位数运算为例，编写代码：
class Stack(object):
# Stack() 创建一个空的新栈。
def __init__(self):
self.items = []
# push(new_item)将一个新的元素添加到栈顶。
def push(self, new_item):
self.items.append(new_item)
# 返回栈顶元素，但不会弹出它。
def top(self):
return self.items[-1]
# 弹出并返回栈顶元素
def pop(self):
return self.items.pop()
# 返回栈是否为空。栈空返回true，否则返回false。
def isEmpty(self):
return [] == self.items
# 返回栈的长度，即栈中元素的个数。
def size(self):
return len(self.items)
# 将中缀表达式变换成后缀表达式
# trans_string为传入的待转换的中缀表达式
# op_rank为运算符的优先级，数字越大，优先级越高
def mid2post(trans_string, op_rank):
post_list = [] #创建一个空列表，用于保存生成中的后缀表达式
stack = Stack() #创建一个新的栈用于保存未被输出的运算符
for checking_char in trans_string: #从左到右，逐个遍历中缀表达式中的字符
if checking_char in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789': #当前字符为字母或数字
post_list.append(checking_char) #将字符接入后缀表达式
elif checking_char == '(': #当前符号为左括号
stack.push(checking_char) #将左括号入栈，代表着后面出现的运算符优先级更高
elif checking_char == ')': #当前符号为右括号
top_char = stack.pop()
while top_char != '(': #弹出元素，接入后缀表达式，直到出现配对的左括号
post_list.append(top_char)
top_char = stack.pop()
else: #符号为运算符
while (not stack.isEmpty()) and (op_rank[stack.top()]>=op_rank[checking_char]): #栈不为空，且栈顶符号优先级不低于当前符号
post_list.append(stack.pop()) #弹出这个更靠前的运算符，并接入后缀表达式
stack.push(checking_char) #将运算符压入栈
while not stack.isEmpty(): #当栈未空
post_list.append(stack.pop()) #弹出所有运算符，并接入后缀表达式
return ''.join(post_list) #将列表转换为字符串并返回
# 将计算后缀表达式
# post_string为传入的待计算的后缀表达式
# op_rank为运算符的优先级，数字越大，优先级越高
def compute_post(post_string):
stack = Stack() #创建一个新的栈用于保存未被输出的运算符
for computing_char in post_string: #从左遍历
if computing_char in '01234567889': #如果当前为数字
stack.push(computing_char) #压入栈
else: #如果为运算符
value_2 = int(stack.pop()) #先弹出后一个操作数
value_1 = int(stack.pop()) #后弹出前一个操作数
if computing_char == '+':
value_3 = value_1 + value_2
elif computing_char == '-':
value_3 = value_1 - value_2
elif computing_char == '*':
value_3 = value_1 * value_2
else:
value_3 = value_1 / value_2
stack.push(value_3) #将运算结果入栈
return stack.pop()
def main():
op_rank = {'*':2, '/':2, '+':1, '-':1, '(':0}
string_list = ['1+2', '1+2*3', '(1+2)*3', '(1+2)*(3+4)', '1+2+3+4']
for trans_string in string_list:
print("%s --> %s --> %d" % (trans_string, mid2post(trans_string,op_rank), compute_post(mid2post(trans_string,op_rank)) ))
print("-----------------")
if __name__ == "__main__":
main()
运行结果为：
1+2 --> 12+ --> 3
-----------------
1+2*3 --> 123*+ --> 7
-----------------
(1+2)*3 --> 12+3* --> 9
-----------------
(1+2)*(3+4) --> 12+34+* --> 21
-----------------
1+2+3+4 --> 12+3+4+ --> 10
-----------------
结果正确。如果需要计算两位数以上的操作数，则需要利用空格等分隔符来对操作数进行分隔。
