笔者是python初学者，如有不妥，请各位指教，多谢大家。写博客不仅仅是为了记录自己的学习过程，还想向大家学习高超的cs技术。
栈的特点很简单 ----> 后进先出，实现过程中，只要遵守该特点即可，其他都是语言特性。
笔者用一个python定义栈的节点，节点（node）包括 元素（elem）和下一个元素（next）
class Node(object): def __init__(self , elem): self.elem = elem self.next = None栈（Stack）的本身，笔者用了也用了一个类进行表示，其属性包括：栈的大小（size）、栈顶位置（top）、存储栈元素的结构（stack）
import random class Stack(object): def __init__(self , size = 0): self.size = size # 堆栈的大小 self.stack = [] # 列表表示栈 self.top = -1 # 栈顶位置 def empty(self): return self.top == -1 def full(self): return self.top + 1 >= self.size def length(self): return self.size def getElementCount(self): return self.top + 1 def getTop(self): if self.empty() is False: return self.stack[self.top] def pop(self): if self.empty() is True: print("maybe this stack is empty,pop error , please check the stack you init") return temp_mum = self.stack.pop() print("pop the element is ->",temp_num) # 这行代码是打印的代码，在下面的应用中已经进行了注释 self.top -= 1 def push_many(self,num): if isinstance(num,list) is False: print("premeters is error , please check yourself") return if len(num) + self.top + 1 > self.size: # 如果这个列表元素的总数加上现在的数目大于栈的大小，则该列表不能插入栈中 print("this list is too long") return for i in num: self.push(i) print("push_many is right") # 这行代码是打印的代码，在下面的应用中已经进行了注释 def push(self,elem): if self.full() is True: print("maybe this stack is full,push ",elem," error ,please check the stack you init") return self.top = self.top + 1 print(self.top ,"\t" ,self.size,"\t",elem) # 这行代码是打印的代码，在下面的应用中已经进行了注释 self.stack.append(elem) def show(self): if self.empty() is True: print("maybe this stack is empty,show error , please check the stack you init") return i = self.top while i >= 0: print(self.stack[i]) i -= 1测试代码如下：
if __name__ == "__main__": stack_temp = Stack(12) stack_temp.push(12) print(stack_temp.empty()) stack_temp.pop() print(stack_temp.length() ,"<----->",stack_temp.getElementCount()) stack_temp.show() print("positon\t","size\t","push_element") for i in range(12): temp = random.randint(12 , 220) stack_temp.push(temp) print("===============show the stack================") stack_temp.show()
运行结果：
中缀表达式转换为后缀表达式的步骤如下：
给出待处理的字符串，对给出的字符串进行预处理，进而形成相应的列表遍历整个列表，判断当前元素是否为运算符，如果是运算符，则进行第3步，否则跳入第6步判断运算符栈是否为空，如果为空，则将当前的运算符压入栈中，否则进行第4步判断当前字符是否是 ‘）‘，如果是的话，则将运算符栈中的栈顶元素压入结果列表中，直到碰见与之对应的’(’结束，跳到第2步，进行下一轮遍历。算出当前字符的优先级x_elem 和运算符栈栈顶元素的优先级x_top，如果x_top 小于x_elem，则将当前的字符压入运算符栈中，否则，将运算符栈栈顶元素压入到结果列表中，直到x_top 小于 x_elem。然后再将当前字符压入运算符栈中。跳到第2步，进行下一轮遍历。将当前元素加入到结果列表中，跳到第2步，进行下一轮遍历。如果运算符栈还没有为空，则将栈中的所有元素依次压入结果列表中。完成代码如下：
def get_core(str_temp):# 设定相应的优先级 if str_temp == '+' or str_temp == '-': return 1 elif str_temp =='*' or str_temp == '/': return 2 elif str_temp == '(' or str_temp == ')': return 4 else: print(str , " is not defined") def judge_tool(str_temp):# 判断是否是运算符 if str_temp in ('-','+','*','/','(',')'): return True return False def middle2Final(str_temp): #将中缀表达式转换成后缀表达式 if isinstance(str_temp , str) is False: #如果参数不是字符串，则不满足程序要求，退出程序 print("type error") exit() stack_tool = Stack(100) #定义运算符栈 ''' 在将字符串转换成列表后，第一：会有相应的空格（这是参数自身带来的空格）；第二：会把多位数分离掉，因为在将字符串转换成列表的过程中， 它是以一个字符作为一个列表元素的方式，所以，会对多位数进行切割，例如 666 会切割成 ['6','6','6'],我们得将其再次拼接 对数据的处理有两种 1、将传过来的参数中的空格进行切除 2、对转换来的列表进行拼接 ''' #===========================以下是对数据的处理======================================= list_temp = list(str_temp) # 去空格前的表达式 list_operate = [] # 去空格后的表达式 result_list = [] # 结果列表 for ele in list_temp: #去掉字符中的空格 if ele != ' ': list_operate.append(ele) list_t = [] # 处理好的表达式 str_temp_num = '' # 暂存拼接好的数据 for ele in list_operate: if judge_tool(ele) is True: if str_temp_num != '':#因可能会有两个相邻的运算符，所以会存在 '' 的情况，我们得过滤掉这种情况 list_t.append(str_temp_num) str_temp_num = '' list_t.append(ele) continue str_temp_num += ele if str_temp_num != '': list_t.append(str_temp_num) #===========================以上是对数据的处理======================================= #==================以下是中缀表达式转换成后缀表达式的过程============================= string = "" # 用字符串记录中缀转换成后缀的结果，该变量只是为了从感性上能容易看出结果而已，没有实际意义 flag = False for ele in list_t: if judge_tool(ele) is True:# 所读的字符为运算符 if stack_tool.empty() is True:# 如果栈中没有运算符，则将当前的运算符压入栈中即可 stack_tool.push(ele) continue if ele == ')': # 如果当前的运算符为 ) ,则将运算符栈中的所有运算符输出，遇见 ( #print("enter here") while stack_tool.empty() is False: top_element_temp = stack_tool.getTop() if top_element_temp == '(': flag = True #print(top_element_temp+"======================") stack_tool.pop() break string = string + top_element_temp result_list.append(top_element_temp) stack_tool.pop() #stack_tool.show() #print("-------------------------") continue x_top = get_core(stack_tool.getTop()) # 栈顶运算符的优先级 x_elem = get_core(ele) # 当前运算符的优先级 if x_top < x_elem: #如果栈顶元素的优先级小于当前元素的优先级 stack_tool.push(ele) else: while x_elem <= get_core(stack_tool.getTop()) and stack_tool.getTop() != '(': # print(stack_tool.getTop()) string = string + stack_tool.getTop() result_list.append(stack_tool.getTop()) stack_tool.pop() if stack_tool.empty() is True: break stack_tool.push(ele) #print('=========================') #stack_tool.show() #print('=========================') else: string = string + ele result_list.append(ele) while stack_tool.empty() is False: # 如果堆栈中还有数据，则依次弹出即可 string = string + stack_tool.getTop() result_list.append(stack_tool.getTop()) stack_tool.pop() #==================以上是中缀表达式转换成后缀表达式的过程============================= #=========================以下是简单的格式检查过程==================================== if flag is False: print("the statement of computation is error,expect for '('") return if '(' in string: # 如果堆栈中还有(，则表示没有) 跟(进行匹配， print("the statement of computation is error,expect for '('") return print(string) return result_list
后缀表达式值的运算代码如下：
def calculate(expression): # 给出后缀表达时，计算出表达式的值 if isinstance(expression,list) is False: print("premeters is error , please check yourself") return cal_stack = Stack(100) temp_num1 = 0 temp_num2 = 0 for elem in expression: if judge_tool(elem) is True: if cal_stack.empty() is True: print("this expression is error ,pleace check it") return temp_num1 = int(cal_stack.getTop()) cal_stack.pop() if cal_stack.empty() is True: print("this expression is error ,pleace check it") return temp_num2 = int(cal_stack.getTop()) cal_stack.pop() if elem == '*': cal_stack.push(temp_num2 * temp_num1) elif elem == '/': if temp_num2 == 0: print("this expression is error, please check it") return cal_stack.push(temp_num1 / temp_num2) elif elem == '-': cal_stack.push(temp_num1 - temp_num2) elif elem == '+': cal_stack.push(temp_num1 + temp_num2) else: print("have no this operation , please check it because you are maybe error") else: cal_stack.push(elem) return cal_stack.getTop()测试代码如下：
if __name__ == "__main__": expression = middle2Final("12 + 2* (3+(4*2+3)*2)") print(expression) print(calculate(expression)) #middle2Final("a + b + c+d-e+f*g")运行结果如下：
注意：这几个代码式一起用的，后面所用到的栈都是前面定义的栈，后缀表达式计算需要将中缀表达式转换成后缀表达式
