Python栈的应用之中缀、前缀和后缀表达式

绝地灬酷狼 2022-02-19 08:43 207阅读 0赞

**中缀表达式**：是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4）。与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被电脑解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。  
与前缀或后缀表达式不同的是，中缀表达式中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。如：(a + b) \* c = ((a + b) \* c)， = 后面的表达式称为完全括号表达式。

**前缀表达式**：是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面。如果操作符的元数（arity）是固定的，则语法上不需要括号仍然能被无歧义地解析。如：\* + a b c ，将中缀表达式的 + 移到a+b左侧 ( 的位置，并去除此括号对，再将 \* 移到(a+b) \* c左侧(的位置，并去除此括号对，结果就是前缀表达式。

**后缀表达式**：指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。如：a b + c \*，将中缀表达式的 + 移到a + b右侧 ) 的位置，并去除此括号对，再将 \* 移到(a+b)\*c右侧 ) 的位置，并去除此括号对，结果就是后缀表达式。

下面示例中的3个表达式表达的是同一个意思。  
中缀：(((A + B) \* C) - ((D - E) \* (F + G)))  
前缀：- \* + A B C \* - D E + F G  
后缀：A B + C \* D E - F G + \* -

# 定义栈类
    class Stack(object):
         def __init__(self):							#初始化空栈
             self.items = []
    
         def isEmpty(self):								#是否为空
             return self.items == []
    
         def push(self, item):							#入栈
             self.items.append(item)
    
         def pop(self):									#出栈
             return self.items.pop()
    
         def peek(self):								#查看最后一个元素
             return self.items[len(self.items)-1]
    
         def size(self):								#查看栈的大小
             return len(self.items)

**中缀转后缀**：从左到右遍历中缀表达式，遇到操作数(字母及数字)，则输出；遇到"("，则进栈；遇到")"，则弹出栈顶，若栈顶不为"(“则输出，继续弹出下一个栈顶并比较，直到弹出”("，结束循环；遇到运算符，若栈不为空，且栈顶元素的优先级>=运算符的优先级(表明栈顶元素也是运算符，这2个运算符相邻)，弹出并输出栈顶元素，继续循环比较，直到不符合循环条件，再将该运算符入栈；遍历结束后，若栈仍不为空，则依次弹出并输出，将最终输出连接并返回结果。

1、创建操作符优先级字典(prec)  
2、创建一个名为 opstack 的空栈以保存运算符(opStack)。给输出创建一个空列表(postfixList)。  
3、通过使用字符串方法拆分将输入的中缀字符串转换为标记列表(tokenList)。  
4、从左到右扫描标记列表(for循环)。  
（1）如果标记是操作数，将其附加到输出列表的末尾。  
（2）如果标记是左括号，将其压到 opstack 上。  
（3）如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。  
（4）如果标记是运算符，\*，/，+或 - ，将其压入 opstack。但是，首先删除已经在 opstack 中具有更高或相等优先级的任何运算符，并将它们加到输出列表中。  
5、当输入表达式被完全处理时，检查 opstack(while循环)。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。

# 中缀转后缀(包括字符：26个大写字母、10个数字、(、)、+、-、*、/)
    def infixToPostfix(infix):
        prec = {}										#设置操作符优先级字典
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1
        opStack = Stack() 								#实例化栈类
        postfixList = [] 								#用于保存转换完成后的字符列表
        tokenList = infix.split()						#以空格分割待转换字符串
        for token in tokenList:
            # if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":	#原代码
            if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789":	#如果为字母或数字，则
                postfixList.append(token)						#添加到最终列表
            elif token == '(': 									
                opStack.push(token)								#将"("入栈
            elif token == ')':
                topToken = opStack.pop()						#出栈
                while topToken != '(': 							#若该出栈元素为运算符，则
                    postfixList.append(topToken) 				#因该运算符位于()中，具有更高的优先级，则将运算符添加到最终列表
                    topToken = opStack.pop() 					#继续出栈，直到为与")"对应的"("
            else: 												#如果为运算符，则
            	#若栈不为空，且栈顶元素的优先级>=运算符的优先级(表明栈顶元素也是运算符，这2个运算符相邻)
                while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
                    postfixList.append(opStack.pop())			#将栈顶元素(比当前运算符具有更高优先级)添加到最终列表
                opStack.push(token)								#该运算符入栈
        while not opStack.isEmpty():							#对比完后，栈仍不为空，则
            postfixList.append(opStack.pop())					#将栈内剩余元素添加到最终列表
        return " ".join(postfixList)							#将最终列表组合成最终字符串
    
    print(infixToPostfix("A * B + C * D"))
    print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
    print(infixToPostfix("( A + B * C ) * C - ( D - E ) * ( F + G )"))

**结果为：**

A B * C D * +
    A B + C * D E - F G + * -
    A B C * + C * D E - F G + * -

**中缀转前缀**：从右到左(反转)遍历中缀表达式，遇到操作数(字母及数字)，则输出；遇到")"，则进栈；遇到"("，则弹出栈顶，若栈顶不为")“则输出，继续弹出下一个栈顶并比较，直到弹出”)"，结束循环；遇到运算符，若栈不为空，且栈顶元素的优先级>=运算符的优先级(表明栈顶元素也是运算符，这2个运算符相邻)，弹出并输出栈顶元素，继续循环比较，直到不符合循环条件，再将该运算符入栈；遍历结束后，若栈仍不为空，则依次弹出并输出，将最终输出连接并返回结果。

# 中缀转前缀(包括字符：26个大写字母、10个数字、(、)、+、-、*、/)
    def infixToPrefix(infix):
    	prec = {}												#设置操作符优先级字典
    	prec['*'] = 3
    	prec['/'] = 3
    	prec['+'] = 2
    	prec['-'] = 2
    	prec[')'] = 1
    	opStack = Stack()										#实例化栈类
    	prefixList = []											#用于保存转换完成后的字符列表
    	tokenList = infix[::-1].split()							#以空格分割待转换的反转字符串
    	for token in tokenList:
    		if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789':	#如果为字母或数字，则
    			prefixList.append(token)						#添加到最终列表
    		elif token == ')':
    			opStack.push(token)								#将")"入栈
    		elif token == '(':
    			topToken = opStack.pop()						#出栈
    			while topToken != ')':							#若该出栈元素为运算符，则
    				prefixList.append(topToken)					#因该运算符位于()中，具有更高的优先级，则将运算符添加到最终列表
    				topToken = opStack.pop()					#继续出栈，直到为与"("对应的")"
    		else:
    			#若栈不为空，且栈顶元素的优先级>=运算符的优先级(表明栈顶元素也是运算符，这2个运算符相邻)
    			while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
    				prefixList.append(opStack.pop())			#将栈顶元素(比当前运算符具有更高优先级)添加到最终列表
    			opStack.push(token)								#该运算符入栈
    	while not opStack.isEmpty():							#对比完后，栈仍不为空，则
    		prefixList.append(opStack.pop())					#将栈内剩余元素添加到最终列表
    	return " ".join(prefixList)								#将最终列表组合成最终字符串
    
    print(infixToPrefix("A * B + C * D")[::-1])
    print(infixToPrefix("( A + B ) * C - ( D - E ) * ( F + G )")[::-1])
    print(infixToPrefix("( A + B * C ) * C - ( D - E ) * ( F + G )")[::-1])

**结果为：**

+ * A B * C D
    - * + A B C * - D E + F G
    - * + A * B C C * - D E + F G

**计算后缀**：从左到右遍历后缀表达式，遇到操作数(数字)，放进栈，遇到操作符(运算符)，栈顶两个数出栈，进行运算，运算结果放进栈，直到读完后缀表达式。

1、创建一个名为 operandStack 的空栈。  
2、拆分字符串转换为标记列表(tokenList)。  
3、从左到右扫描标记列表(for循环)。  
（1）如果标记是操作数，将其从字符串转换为整数，并将值压到operandStack。  
（2）如果标记是运算符\*，/，+或-，它将需要两个操作数。弹出operandStack 两次。 第一个弹出的是第二个操作数，第二个弹出的是第一个操作数。执行算术运算后，将结果压到操作数栈中。  
4、当输入的表达式被完全处理后，结果就在栈上，弹出 operandStack 并返回值。

# 后缀表达式求值(包括字符：10个数字、(、)、+、-、*、/)
    def postfixEval(postfix):
        operandStack = Stack()									#实例化栈类
        tokenList = postfix.split()								#以空格分割待转换字符串
        for token in tokenList:
            if token in "0123456789":							#为数字
                operandStack.push(int(token))					#入栈
            else:												#为运算符
                operand2 = operandStack.pop()					#出栈，为运算符后面的数字
                operand1 = operandStack.pop()					#再出栈，为运算符前面的数字
                result = doMath(token,operand1,operand2)		#进行计算
                operandStack.push(result)						#值入栈并进行下一步
        return operandStack.pop()								#栈中最终值为计算结果，返回出栈
    
    # 计算函数
    def doMath(op, op1, op2):
        if op == "*":
            return op1 * op2
        elif op == "/":
            return op1 / op2
        elif op == "+":
            return op1 + op2
        else:
            return op1 - op2
    
    print(postfixEval('7 8 + 3 2 + /'))
    print(postfixEval("7 8 * 3 2 * +"))
    print(postfixEval("7 8 + 3 * 2 9 - 1 5 + * -"))
    print(postfixEval("7 8 3 * + 3 * 2 9 - 1 5 + * -"))

**结果为：**

3.0
    62
    87
    135

**计算前缀**：从左到右遍历前缀表达式，遇到操作符(运算符)，放进栈；遇到操作数(数字)，查看栈顶，栈顶为操作符，则放进栈，栈顶为操作数，则取出栈顶操作数和操作符(取出2次)，进行运算，运算结果作为操作数，继续循环判断栈顶的情况，直到不符合循环条件，再将操作数入栈，最终得出结果。

# 前缀表达式求值(包括字符：10个数字、(、)、+、-、*、/)
    def prefixEval(prefix):
        operandStack = Stack()									#实例化栈类
        tokenList = prefix.split()								#以空格分割待转换字符串
        for token in tokenList:
        	if token in "+-*/":									#为运算符
        		operandStack.push(token)						#将运算符入栈
        	else:												#为数字
        		if operandStack.peek() in '+-*/':				#当前栈顶为运算符
        			operandStack.push(token)					#将数字入栈
        		else:											#当前栈顶为数字
        			#若栈不为空，且当前栈顶为数字，则一直循环计算
        			while (not operandStack.isEmpty()) and (not operandStack.peek() in '+-*/'):
    	    			shu = operandStack.pop()				#出栈，为运算符前面的数字
    	    			fu = operandStack.pop()					#出栈，为运算符
    	    			token = doMath(fu, int(shu), int(token))#计算
    	    		operandStack.push(str(token))				#值入栈并进行下一步
        return operandStack.pop()								#栈中最终值为计算结果，返回出栈
    
    print(prefixEval('/ + 7 8 + 3 2'))
    print(prefixEval('+ * 7 8 * 3 2'))			
    print(prefixEval('- * + 7 8 3 * - 2 9 + 1 5'))	
    print(prefixEval('- * + 7 * 8 3 3 * - 2 9 + 1 5'))

**结果为：**

3.0
    62
    87
    135