【Python】中缀表达式转后缀表达式（逆波兰表达式RPN）及后缀表达式计算方法

爱被打了一巴掌 2022-05-23 12:00 307阅读 0赞

### 逆波兰表达式RPN ###

逆波兰表达式Reverse Polish Notation，又叫后缀表达式。  
习惯上，二元运算符总是置于与之相关的两个运算对象之间，即中缀表达式。波兰逻辑学家J.Lukasiewicz于1929年提出了运算符都置于其运算对象之后，故称为后缀表达式。  
如：  
中缀表达式：a+(b-c)\*d  
后缀表达式：abc-d\*+

#### 中缀表达式转后缀表达式，Python代码如下： ####

def convert_to_suffix_expression(s):
        """
        中缀表达式转后缀表达式
        :param s: 中缀表达式
        :return: 后缀表达式
        """
        # 设置操作符优先级，数字越大优先级越高
        kv = {
       '+': 1, '-': 1, '*': 2, '/': 2, '(': 0, ')': 3}
        li = []  # 用来当栈存放操作符
        result = ''  # 返回结果
        for i in s:
            if i == '+' or i == '-' or i == '*' or i == '/' or i == '(' or i == ')':
                if i == '(':
                    li.append(i)
                elif i == ')':
                    while len(li) > 0 and li[-1] != '(':
                        p = li.pop()
                        result += p
                    li.pop()  # 弹出左括号
                elif len(li) == 0 or kv[li[-1]] < kv[i]:
                    li.append(i)
                else:
                    result += i
            else:
                result += i
    
        while len(li) > 0:
            result += li.pop()
    
        return result
    
    
    if __name__ == '__main__':
        s = 'a+(b-c)*d'  # 中缀表达式
        result = convert_to_suffix_expression(s)
        print(result)

输出结果：abc-d\*+

#### 逆波兰表达式的计算方法，Python代码如下： ####

# 逆波兰表达式的计算方法
    # abc-d*+
    # 若当前字符是操作数，则压栈
    # 若当前字符是操作符，则弹出栈中的两个操作数，计算后仍然压入栈中
    # 若某次操作，栈内无法弹出两个操作数，则表达式有误。
    def reverse_polish_notation(s, kv):
        """
        逆波兰表达式计算
        :param s: 逆波兰表达式
        :param kv: 参数对应的数值
        :return: 计算结果
        """
        li = []  # 用来当栈存放操作数
        for i in s:
            if i == '+' or i == '-' or i == '*' or i == '/':
                if len(li) < 2:
                    print("表达式有误")
                    return
                b = float(li.pop())
                a = float(li.pop())
                c = 0
                if i == '+':
                    c = a + b
                elif i == '-':
                    c = a - b
                elif i == '*':
                    c = a * b
                elif i == '/':
                    if b == 0:
                        print("被除数不能为0")
                        return
                    c = a / b
                li.append(c)
            else:  # 操作数压栈
                li.append(kv[i])
    
        if len(li) != 1:
            print("表达式有误")
            return
        return li[0]
    
    
    if __name__ == '__main__':
        s = 'abc-d*+'  # 后缀表达式
        kv = {
       'a': 1, 'b': 2, 'c': 3, 'd': 4}  # 参数对应的数值
        result = reverse_polish_notation(s, kv)
        print(result)

输出结果：-3.0