Python栈的应⽤之中缀、前缀和后缀表达式
strcpy
中缀表达式：是⼀个通⽤的算术或逻辑公式表⽰⽅法， 操作符是以中缀形式处于操作数的中间（例：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__(lf): #初始化空栈
lf.items = []
def isEmpty(lf): #是否为空
return lf.items == []
def push(lf, item): #⼊栈
lf.items.append(item)
def pop(lf): #出栈
return lf.items.pop()
def peek(lf): #查看最后⼀个元素
return lf.items[len(lf.items)-1]
def size(lf): #查看栈的⼤⼩
return len(lf.items)
中缀转后缀：从左到右遍历中缀表达式，遇到操作数(字母及数字)，则输出；遇到"("，则进栈；遇到")"，则弹出栈顶，若栈顶不为"(“则输出，继续弹出下⼀个栈顶并⽐较，直到弹出”("，结束循环；遇到运算符，若栈不为空，且栈顶元素的优先级>=运算符的优先级(表明栈顶元素也是运算符，这2个运算符相邻)，弹出并输出栈顶元素，继续循环⽐较，直到不符合循环条件，再将该运算符⼊栈；遍历结束后，若栈仍不为空，则依次弹出并输出，将最终输出连接并返回结果。eleanor roovelt
1、创建操作符优先级字典(prec)
2、创建⼀个名为 opstack 的空栈以保存运算符(opStack)。给输出创建⼀个空列表(postfixList)。
3、通过使⽤字符串⽅法拆分将输⼊的中缀字符串转换为标记列表(tokenList)。
4、从左到右扫描标记列表(for循环)。
（1）如果标记是操作数，将其附加到输出列表的末尾。
（2）如果标记是左括号，将其压到 opstack 上。
（3）如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。
（4）如果标记是运算符，*，/，+或 - ，将其压⼊ opstack。但是，⾸先删除已经在 opstack 中具有更⾼或相等优先级的任何运算符，并将它们加到输出列表中。
5、当输⼊表达式被完全处理时，检查 opstack(while循环)。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。
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() #继续出栈，直到为与")"对应的"("
el: #如果为运算符，则
#若栈不为空，且栈顶元素的优先级>=运算符的优先级(表明栈顶元素也是运算符，这2个运算符相邻)
while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
postfixList.append(opStack.pop()) #将栈顶元素(⽐当前运算符具有更⾼优先级)添加到最终列表
opStack.push(token) #该运算符⼊栈
while not opStack.isEmpty(): #对⽐完后，栈仍不为空，则
pool什么意思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个
运算符相邻)，弹出并输出栈顶元素，继续循环⽐较，直到不符合循环条件，再将该运算符⼊栈；遍历结束后，若栈仍不为空，则依次弹出并输出，将最终输出连接并返回结果。
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() #继续出栈，直到为与"("对应的")"
el:
#若栈不为空，且栈顶元素的优先级>=运算符的优先级(表明栈顶元素也是运算符，这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)) #⼊栈
el: #为运算符
operand2 = operandStack.pop() #出栈，为运算符后⾯的数字
operand1 = operandStack.pop() #再出栈，为运算符前⾯的数字
kepler
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
el:
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个数字、(、)、+、-、*、/)
eoa
def prefixEval(prefix):
operandStack = Stack() #实例化栈类
tokenList = prefix.split() #以空格分割待转换字符串
for token in tokenList:
if token in "+-*/": #为运算符
operandStack.push(token) #将运算符⼊栈
el: #为数字
if operandStack.peek() in '+-*/': #当前栈顶为运算符
operandStack.push(token) #将数字⼊栈
el: #当前栈顶为数字
#若栈不为空，且当前栈顶为数字，则⼀直循环计算
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() #栈中最终值为计算结果，返回出栈
personal interests
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
