from pythonds.basic.stack import Stack
def infixToPostfix(infixexpr):
# prec字典存储着运算符的优先级
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
# 定义空栈存储运算符出栈和进栈操作结果
openStack = Stack()
# 存储最后的后缀表达式的结果list
postficList = []
# tokenList存储将表达式分割字符后的list,要求表达式中的字符之间必须有空格
tokenList = infixexpr.split()
for token in tokenList:
# 只要分割的字符在A-Z或者阿拉伯数字0-9之间放到postficList
if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
postficList.append(token)
# 左括弧匹配
elif token == '(':
openStack.push(token)
elif token == ')':
toptoken = openStack.pop()
# 非括弧符号匹配
while toptoken != '(':
postficList.append(toptoken)
toptoken = openStack.pop()
else:
# 运算符优先级比较
while (not openStack.isEmpty()) and (prec[openStack.peek()] >= prec[token]):
postficList.append(openStack.pop())
openStack.push(token)
while not openStack.isEmpty():
postficList.append(openStack.pop())
return " ".join(postficList)
if __name__ == '__main__':
print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( ( A * B ) + ( C * D ) )"))
print(infixToPostfix("A + B * C + D"))
print(infixToPostfix("( A + B ) * ( C + D )"))
print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("A + B + C + D"))
根据上面的求解后缀表达式算法，然后我们继续深入，根据表达式求出后缀表达式后在求出表达式的结果，就走完计算机存储体系中关于表达式计算的完整过程。
from pythonds.basic.stack import Stack
def infixToPostfix(infixexpr):
# prec字典存储着运算符的优先级
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
# 定义空栈存储运算符出栈和进栈操作结果
openStack = Stack()
# 存储最后的后缀表达式的结果list
postficList = []
# tokenList存储将表达式分割字符后的list,要求表达式中的字符之间必须有空格
tokenList = infixexpr.split()
for token in tokenList:
# 只要分割的字符在A-Z或者阿拉伯数字0-9之间放到postficList
if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
postficList.append(token)
# 左括弧匹配
elif token == '(':
openStack.push(token)
elif token == ')':
toptoken = openStack.pop()
# 非括弧符号匹配
while toptoken != '(':
postficList.append(toptoken)
toptoken = openStack.pop()
else:
# 运算符优先级比较
while (not openStack.isEmpty()) and (prec[openStack.peek()] >= prec[token]):
postficList.append(openStack.pop())
openStack.push(token)
while not openStack.isEmpty():
postficList.append(openStack.pop())
return " ".join(postficList)
def postficEval(infixexpr):
openStack = Stack()
# 先转换中缀表达式为后缀表达式
tokenList = infixToPostfix(infixexpr).split()
# print(tokenList)
for token in tokenList:
# 遇到操作数就压栈
if token in "0123456789":
openStack.push(int(token))
else:
# 遇到操作运算符就出站，并且计算最近的两个操作数
# 这里因为操作数的相对顺序原因，第一个操作数是栈顶第二个元素
openTop2 = openStack.pop()
openTop1 = openStack.pop()
# 执行计算
result = opMath(token, openTop1, openTop2)
# 返回结果继续压栈
openStack.push(result)
# 直到栈空间只剩下一个操作数，那么就弹出即为最终结果
return openStack.pop()
def opMath(op, op1, op2):
if op == '*':
return op1 * op2
elif op == '/':
return op1 / op2
elif op == '+':
return op1 + op2
else:
return op1 - op2
if __name__ == '__main__':
print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( ( A * B ) + ( C * D ) )"))
print(infixToPostfix("A + B * C + D"))
print(infixToPostfix("( A + B ) * ( C + D )"))
print(infixToPostfix("A * B + C * D"))
print(type(infixToPostfix("A * B + C * D")))
print(len(infixToPostfix("A * B + C * D")))
print(infixToPostfix("A + B + C + D"))
print('=================================')
print(postficEval("3 * ( 2 - 3 )"))
