前缀、中缀、后缀表达式（逆波兰表达式）

前缀表达式称为波兰表达式，前缀表达式的运算符位于操作符之前

举例说明：（3+4）x 5 – 6 对应的前缀表达式就是- X + 3 4 5 6

中缀表达式转为后缀表达式：

具体步骤：（注意括号不算运算符）

1. 初始化两个栈，其中运算符栈s1和存储中间结果的栈s2
2. 从左到右进行扫描中缀表达式
3. 遇到操作符将其压进s2
4. 遇到运算符，比较其与s1栈顶运算符的优先级：

1. 如果s1为空，或者栈顶运算符为左括号，则直接将此运算符压进栈中
2. 否则，若优先级比栈顶运算符的高，也将运算符压入s1
3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到第一小步中与s1中新的栈顶运算符相比较。

5.遇到括号时：

1. 如果是左括号，直接压入s1中
2. 如果是有括号，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃

6. 重复步骤2至5,直到表达是的最右边

7. 将s1中剩余的运算符依次弹出并压入s2

8. 依次弹出s2中的元素并输出，结果的逆序即中缀表达式对应的后缀表达式

# 中缀表达式 --->  后缀表达式
# 1 + ((2+3)*4) - 5 ---->  1 2 3 + 4 * + 5 -class ArrayStack2:def __init__(self,masSize):self.maxsize = masSizeself.stack = []self.top = -1# 判断栈是不是 满的def isFull(self):return self.top == self.maxsize - 1# 判断栈是不是空的def isEmpty(self):return self.top == -1# 将数据压入栈中def push(self,value):if self.isFull():print("栈已经满了！")returnself.top = self.top + 1self.stack.append(value)# 将栈中的数据进行删除def pop(self):if self.isEmpty():print("栈已经是空的了，没法执行出栈操作!")returnvalue = self.stack.pop()self.top = self.top - 1return value# 显示栈的内容，需要先从栈顶显示数据def showStack(self):if self.isEmpty():print("栈已经是空的了，没法执行显示操作!")returni = self.topwhile i > -1:print("栈中存在的数据：",self.stack[i])i = i -1# 返回运算法的优先级  有程序员决定  优先级使用数字来表示，数字越大优先级越高def priority(self,oper):if (oper == "*" or oper == "/"):return 1elif (oper == "+" or oper == "-"):return 0else:return -1# 判断是不是一个运算法def isOper(self,val):return val == "*" or val == "/" or val == "+" or val =="-"def isyunsuan(self,val):return val == "(" or val == ")"# 进行计算def cal(self,num1,num2,oper):if oper == "+":return num1 + num2elif oper == "-":return num2 - num1 # 注意顺序elif oper == "*":return num1 * num2elif oper == "/":return num2 / num1# 只返回最后的一个元素，但是并不是删除最后 一个元素def peek(self):return self.stack[self.top]class Infixtohouzhui:def __init__(self,expression = "1+((2+3)*4)-5"):self.expression = expressionself.s1 = ArrayStack2(20)self.s2 = []  # 直接使用list比较好self.flag = 0self.index = 0self.data = 1self.keepnum = 0def change(self):while self.index <= len(self.expression) - 1:if self.s1.isOper(self.expression[self.index]) == False and self.s1.isyunsuan(self.expression[self.index]) == False:self.keepnum = self.expression[self.index]while True:if self.index + self.data <= len(self.expression) - 1:if (self.s1.isOper(self.expression[self.index + self.data])) == False and self.s1.isyunsuan(self.expression[self.index + self.data]) == False:self.flag = 1self.keepnum = self.keepnum + self.expression[self.index+self.data]self.data = self.data + 1else:breakelse:breakself.s2.append(self.keepnum)self.keepnum = ""elif self.expression[self.index] == "(":self.s1.push(self.expression[self.index])# 如果是有括号，就将s1中的运算符，压到s2中，知道遇到左括号为止elif (self.expression[self.index]) == ")":while (self.s1.peek())!="(":self.s2.append(self.s1.pop())self.s1.pop() # 将s1中的左括号要删除掉else:# 当s1的栈顶运算符大于新来的运算符 将s1的栈顶运算符放到s2中，然后不停的比较while (self.s1.isEmpty() == False and self.s1.priority(self.s1.peek())>=self.s1.priority(self.expression[self.index])):self.s2.append(self.s1.pop())self.s1.push(self.expression[self.index])if self.flag:self.index = self.index + self.dataself.flag = 0self.data = 1else:self.index = self.index + 1while self.s1.isEmpty() == False:self.s2.append(self.s1.pop())return self.s2if __name__ == '__main__':ll = Infixtohouzhui()print(ll.change())