数据结构之栈的应用---逆波兰式的转换及计算(Python)

Tyrant 2019年04月04日 •  Python 数据结构 411 •  0
本文最后修改于 205 天前,部分内容可能已经过时!

基本概念

  • 逆波兰式:用比较通俗的语言来讲,就是将多项式的操作数和符号重新排列,操作数在前,符号在后
  • 栈:这种数据结构是一种特殊的线性表,只能在一头进行插入和删除,所以有着先进后出的特点

算法实现

  • 中缀式转逆波兰式

需要一个符号栈,初始为空,遍历多项式的每项,如果是数字,记录进结果,如果是符号,判断当前符号和栈顶符号的优先级(括号 < + - < * /),如果优先级大于栈顶符号,则进栈;如果优先级小于栈顶符号,栈顶出栈,如果出栈的不是括号,记录至结果中,直至栈顶优先级小于当前符号,而后符号进栈,直至遍历完整个表达式,最后将符号栈中的符号出栈记录至结果

  • 计算逆波兰式

需要一个结果栈,初始为空,遍历逆波兰式,如果是数字,进栈,遇到符号,出栈两个操作数,进行计算并将计算结果进栈,直至遍历完成,此时栈顶为表达式结果

代码实现

stack.py

import readline
import time
expression = input("请输入表达式(每个字符用空格隔开):")
expression = expression.split()

def get_Reverse_Polish_Notation(expression):
    '''转化逆波兰式'''
    stack = list()
    result = list()
    symbol = ['(', ')', '+', '-', '*', '/']
    value = {
        '(':1,
        ')':1,
        '+':2,
        '-':2,
        '*':3,
        '/':3,
    }
    for i in expression:
        #如果元素是数字,直接进栈
        if i.isdigit():
            result.append(i)
        #如果元素是符号,进入判断
        if i in symbol:
            #如果栈不为空,则判断符号优先级
            if stack:
                #判断如果符号优先级不高于栈顶符号优先级,则出栈,直至优先级大于栈顶符号
                if value[i] <= value[stack[-1]] and i != '(':
                    #如果符号为右括号,则进行匹配左括号
                    if i == ')':
                        while stack[-1] != '(':
                            result.append(stack.pop())
                        stack.pop()
                    #如果不是右括号,则进行出栈操作,直到大于栈顶符号为止
                    else:
                        while True:
                            result.append(stack.pop())
                            if stack:
                                if value[i] > value[stack[-1]] :
                                    stack.append(i)
                                    break
                            else:
                                    stack.append(i)
                                    break

                #如果大于栈顶符号,直接进栈
                else:
                    stack.append(i)
            #如果初始栈为空,则直接进栈第一个符号
            else:
                stack.append(i)
    #遍历完整个表达式,将栈中剩余的符号出栈
    while stack:
        result.append(stack.pop())
    #返回结果列表
    return result

def count_result(result):
    '''计算逆波兰式'''
    stack = list()
    #遍历逆波兰式,如果是数字,直接进栈,如果是符号,则出栈两个操作数,计算出结果入栈
    for i in result:
        if i.isdigit():
            stack.append(i)
        else:
            if i == '+':
                temp = float(stack[-2]) + float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
            elif i == '-':
                temp = float(stack[-2]) - float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
            elif i == '*':
                temp = float(stack[-2]) * float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
            elif i == '/':
                temp = float(stack[-2]) / float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
    return float(stack[-1])
Tags:数据结构
上一篇
打赏
下一篇

添加新评论