用Python实现从中序表达式到后序表达式的转换

我不是女神ヾ 2023-07-11 08:47 23阅读 0赞

> 《Python数据结构与算法分析》（第二版）

中序表达式：( A \* B ) + ( C \* D )  
后序表达式：A B \* C D \* +

*1. 假设中序表达式是一个以空格分隔的标记串，其中，运算符标记有、/、+和-，括号有(和)，操作数标记有A、B、C等。下面的步骤会生成一个后序标记串。*\*

1.  创建用于保存运算符的空栈opStack，以及一个用于保存结果的空列表。
2.  使用字符串方法split将输入的中序表达式转换成一个列表。
3.  从左到右扫描标记列表。

*  如果标记是操作数，将其添加到结果列表的末尾。
 *  如果标记是左括号，将其压入opStack栈中。
 *  如果标记是右括号，反复从opStack栈中移除元素，直到移除对应的左括号。将从栈中取出的每一个运算符都添加到结果列表的末尾。
 *  如果标记是运算符，将其压入opStack栈中。但是，在这之前，需要先从栈中取出优先级更高或相同的运算符，并将它们添加到结果列表的末尾。

4.当处理完输入表达式以后，检查opStack。将其中所有残留的运算符全部添加到结果列表的末尾。

# !/user/bin/env python
    # coding:utf-8
    from pyStack import Stack
    import string
    
    
    def infixToPostfix(infixexpr):
        prec = {}
        #左括号优先级最低
        prec['('] = 1
        prec['+'] = 2
        prec['-'] = 2
        prec['*'] = 3
        prec['/'] = 3
    
        opStack = Stack()
        postfixList = []
    
        tokenList = infixexpr.split()
    
        for token in tokenList:
            # string.ascii_uppercase是string模块中一个包含所有大写字母的字符串
            if token in string.ascii_uppercase:
                postfixList.append(token)
            elif token == '(':
                opStack.push(token)
            elif token == ')':
                topToken = opStack.pop()
                while topToken != '(':
                    postfixList.append(topToken)
                    topToken = opStack.pop()
            else:
                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)

*2.实现后序表达式的计算：假设后序表达式是一个以空格分隔的标记串且输入的表达式没有错误。其中运算符有、/、+和-，操作数为整数。*\*

1.  创建空栈operandStack
2.  使用字符串方法将输入的后序表达式转换成一个列表
3.  从左到右扫描这个标记列表。

*  如果标记是操作数，将其转换成整数并压入operandStack栈中。
 *  如果标记是运算符，从operandStack栈中取出两个操作数。第一次取出右操作数，第二次取出左操作数。进行相应的算术运算，然后将运算结果压入operandStack栈中。（***由于除号是不可交换的运算符，因此必须保证操作数的顺序没有颠倒***）

1.  当处理完输入表达式是，栈中的值就是结果，并进行相应运算。

def postfixEval(postfixExpr):
        operandStack = Stack()
    
        tokenList = postfixExpr.split()
    
        for token in tokenList:
            if number(token):
                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
    
    
    def number(num):
        numStr = str(num)
        isNumber = True
    
        for i in numStr:
            if i not in "0123456789-":
                isNumber = False
                break
    
        return isNumber
    
    
    print(postfixEval("-10 -8 + 3 6 + /"))