python中序表达式转为后序

1.   先了解后序表达式的计算

ABC*+

对于这样的式子，数字依次入栈，如果遇到操作符，从栈中弹出两个数进行相应的计算，并将结果入栈，接着继续取表达式中的元素，重复该步骤，直到表达式被取完，栈中元素结尾结果。

2.   中序变后序表达式

确保结果列表中原来表达式里优先级高的在后序表达式的靠左侧

方法：

有 1 个结果列表，1 个栈

先将字符串拆成列表

遍历列表：

　　数字放入结果列表，不管何种表达式不影响数字的顺序

　　遇运算符，如果栈中已有运算符优先级大于等于当前运算符，则栈中运算符加入结果列表（同级运算符顺序计算）；运算符入栈

　　最后将栈中运算符依次出栈并加至结果列表的末尾

至此可以解决A*B+C、和A+B*C的问题

下面解决括号改变优先级的问题

在遍历中加一个检测：

左括号入栈；如果读到右括号，则将栈中的元素添加到结果列表中，直到左括号为止

3.   python中栈的使用

使用列表，在尾部添加或移除，取栈顶元素使用mystack[-1]，

判空直接使用名字

import string

def infixToPostfix(infixexpr):

    prec = {}
    prec['*'] = 3
    prec['/'] = 3
    prec['+'] = 2
    prec['-'] = 2
    prec['('] = 1

    opStack = []
    postfixList = []
    tokenList = infixexpr.split()

    for token in tokenList:
        if token in string.ascii_uppercase:#数字
            postfixList.append(token)
        elif token == '(':#左括号入栈
            opStack.append(token)
        elif token == ')':#右括号
            topToken = opStack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        else:
            while opStack and \
                      (prec[opStack[-1]] >= prec[token]):
                postfixList.append(opStack.pop())
            opStack.append(token)
    while opStack:
        postfixList.append(opStack.pop())
    return ' '.join(postfixList)

s = input()
print(infixToPostfix(s))

加入计算功能：

import string

def doMath(op,op1,op2):
    if op == '*':
        return op1*op2
    elif op == '/':
        return op1/op2
    elif op == '+':
        return op1+op2
    else:
        return op1-op2

def infixToPostfix(infixexpr):
    prec = {}
    prec['*'] = 3
    prec['/'] = 3
    prec['+'] = 2
    prec['-'] = 2
    prec['('] = 1

    opStack = []
    postfixList = []
    tokenList = infixexpr.split()
    for token in tokenList:
        if token not in '+-*/()':#数字
            postfixList.append(token)
        elif token == '(':#左括号入栈
            opStack.append(token)
        elif token == ')':#右括号
            topToken = opStack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        else:
            while opStack and \
                      (prec[opStack[-1]] >= prec[token]):
                postfixList.append(opStack.pop())
            opStack.append(token)
    while opStack:
        postfixList.append(opStack.pop())
    return ' '.join(postfixList)

def postfixEval(postfixExpr):
    operandS = []
    tokenList = postfixExpr.split()
    for token in tokenList:
        if token not in '+-*/':
            operandS.append(float(token))
        else:
            operand2 = operandS.pop()
            operand1 = operandS.pop()
            result = doMath(token,operand1,operand2)
            operandS.append(result)
    return operandS.pop()

ch = 'y'
while ch == 'y':
    s = input()
    print(postfixEval(infixToPostfix(s)))
    ch = input('Continue? y/n ')

4.   错误检测和报告

两大函数组合一下，使用异常处理，如果制作后序表达式时出问题，抛出异常，不再计算后面的值