栈_01_栈的应用:表达式求值

作者: 依依东望_220b | 来源:发表于2019-05-02 12:19 被阅读0次

栈_01_栈的应用:表达式求值
栈
数据结构复习
4 : 栈
大话数据结构 - 栈
数据结构第5节栈 Stack
20. 有效的括号
数据结构入门（三）栈的应用
2017/3/13 周一
数据结构-其他线性结构（栈和队列）

"""
注意，这里只考虑了输入表达式中，参与运算的书都是正数的情况
"""
class Linked_Stack:
    class Node:
        def __init__(self,value,next=None):
            self.value=value
            self.next=next

    """
    LIFO栈的实现(利用链表)
    """
    def __init__(self):
        """
        创建一个空栈
        """
        self._items=None
        self._size=0

    def push(self,value):
        """
        添加一个元素入栈
        :return:
        """
        self._items=self.Node(value,self._items)
        self._size+=1

    def pop(self):
        """
        一个元素出栈
        :return:
        """
        if self.isEmpty():
            raise KeyError("The stack is empty")
        item_value=self._items.value
        self._items=self._items.next
        self._size-=1
        return item_value

    def peek(self):
        if self.isEmpty():
            raise KeyError("The stack is empty")
        item_value=self._items.value
        return item_value

    def isEmpty(self):
        """
        判断栈是否为空
        :return:
        """
        return self._items==None

    def __extensionts(self):
        """
        扩展的功能函数
        :param item:
        :return:
        """
        tempList=[]

        def visitNode(node):
            if not node is None:
                visitNode(node.next)
                tempList.append(node.value)
            return tempList
        visitNode(self._items)
        return tempList

    def __getitem__(self, key):
        """
        支持对容器 self[key] 操作
        :param key:
        :return:
        """
        result_list=self.__extensionts()
        return result_list[key]

    def __iter__(self):
        """
        支持迭代操作
        :return:
        """
        result_list=self.__extensionts()
        return iter(result_list)

    def __str__(self):
        """
        利用list的str实现
        :return:
        """
        result_list=self.__extensionts()
        return str(result_list)

    def size(self):
        """
        返回
        :return:
        """
        return self._size

class Evaluate:
    """
    利用栈计算
    """
    def expression_splite(self,expression):
        """
        将传入表达式解析为 表达式解析单元列表
        :param expression:
        :return:
        """
        #去除字符串表达式首尾的特殊字符
        expression=expression.strip()
        #表达式解析结果列表
        result=[]

        number_item="" #用于存储拼接出来的数字单元

        #遍历表达式中每一个元素
        for cursor_index in range(0,len(expression)):
            #当前元素的值
            item=expression[cursor_index]

            #如果当前元素为操作符,就将操作符直加入操作符栈
            if item in ["(",")","+","-","*","/"]:
                #如果是开头出现的"(",就只将"("加入结果列表
                if item=="(" and cursor_index==0:
                    result.append(item)
                #如果遇到其他运算符，或者"("，就将他们前面的拼接的数字单元加入结果集合中
                else:
                    #如果当前拼接出来的运算数不为空
                    if number_item!="":
                        #将拼接出来的运算数加入栈
                        result.append(float(number_item))
                        number_item=""
                    #将运算符加入栈
                    result.append(item)
            #如果当前元素是数字，那就拼接数字,与符号
            elif item in ["0","1","2","3","4","5","6","7","8","9","."]:
                number_item+=item
                #如果当前元素是最后一个元素,就将最后一个元素加入结果集中
                if cursor_index==len(expression)-1:
                    result.append(float(number_item))

        #返回 表达式 字符串解析结果
        return result

    def generate_postfix_expression(self,expression):
        """
        将输入的中缀表达式转化为后缀表达式
        :param expression:
        :return:
        """
        #获取表达式列表
        linked_list=self.expression_splite(expression)

        #存储操作符的栈
        oper_stack=Linked_Stack()
        #存储后缀表达式处理结果的栈
        postfix_expression_stack=Linked_Stack()
        #操作符 优先级 列表
        oper_dict={'*':2,'/':2,'+':1,'-':1}

        for item in linked_list:
            #如果当前元素是操作符,处理操作符
            if item in ['(',')','+','-','*','/']:
                #如果当前操作符栈为空，就当前操作符加入操作符栈中
                if oper_stack.isEmpty():
                    oper_stack.push(item)
                #如果当前操作符栈不为空，进行相应处理
                else:
                    #如果当前元素为 '(‘,就将'('如栈
                    if item=='(':
                        oper_stack.push("(")
                    #如果当前元素是右括号,执行出栈操作，并将弹出栈的元素加入后缀表达式栈，知道弹出栈的是左括号，括号不加入后缀表达式栈
                    elif item==")":
                        oper=oper_stack.pop()
                        while oper!="(":
                            postfix_expression_stack.push(oper)
                            oper=oper_stack.pop()
                    #如果当前元素是运算符
                    else:
                        #弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
                        #弹出所有大于等于运算符栈的栈定元素(如果有右括号，则截止到右边括号)出现,并将他们加入
                        oper=oper_stack.peek()
                        while oper!="(" and oper_dict[oper]>=oper_dict[item]:
                            #栈顶元素出栈
                            oper=oper_stack.pop()
                            postfix_expression_stack.push(oper)
                            #获取新的栈顶元素的值
                            oper=oper_stack.peek()
                        #将当前元素item 加入操作符栈中
                        oper_stack.push(item)

            #如果当前元素是数字,就将数字入后缀表达式栈
            else:
                postfix_expression_stack.push(item)

        #处理完成表达式列表中每个元素后，将操作符栈的所有元素出栈并加入 后缀表达式栈
        while not oper_stack.isEmpty():
            oper=oper_stack.pop()
            postfix_expression_stack.push(oper)

        #返回后缀表达式栈
        return postfix_expression_stack


    def calculate_expression(self,expression):
        """
        计算表达式的值
        :param expression:
        :return:
        """

        #获取后缀表达式列表
        postfix_expression_stack=self.generate_postfix_expression(expression)
        #关于后缀表达式栈的缩影
        cursor_postfix_expression=0

        #操作数堆栈
        number_stack=Linked_Stack()

        #处理栈中的每个元素
        while cursor_postfix_expression<postfix_expression_stack.size():
            #获取当前栈索引所指向的栈中元素
            item=postfix_expression_stack[cursor_postfix_expression]
            #如果当前元素是运算符
            if item in ["+","-","*","/"]:
                #将参与运算的两个元素入栈,注意：这里一定要是 Arg_01_item 运算符 Arg_02_item,因为，Arg_02_item是栈顶元素也就是后如栈的(运算符右边的数)，Arg_01_item是先入栈的(运算符左边的数)
                Arg_02_item=number_stack.pop()
                Arg_01_item=number_stack.pop()
                if item=="+":
                    val=Arg_01_item+Arg_02_item
                elif item=="-":
                    val=Arg_01_item-Arg_02_item
                elif item=="*":
                    val=Arg_01_item*Arg_02_item
                elif item=="/":
                    val=Arg_01_item/Arg_02_item
                else:
                    pass
                #将运算后的结果加入运算符栈中
                number_stack.push(val)
            #如果当前元素是数字
            else:
                #就将数字加入运算数栈
                number_stack.push(item)
            #索引自加1
            cursor_postfix_expression+=1

        #返回最终运算结果,也就是运算数栈中的最后一个元素
        return number_stack.pop()

def check_expression_split():
    """
    测试 表达式 元素解析列表
    :return:
    """
    expression_01="((2+18)/12+144/6.89)/90.28"
    expression_list_01=Evaluate().expression_splite(expression_01)
    print(expression_01," >>>>>>>> ",expression_list_01)

    expression_02="89+(89/33.3-12*(3+23)*4)"
    expression_list_02=Evaluate().expression_splite(expression_02)
    print(expression_02," >>>>>>>> ",expression_list_02)

def check_stack():
    """
    测试 链表栈 的运行是否正常
    :return:
    """
    stack_linked=Linked_Stack()

    for _ in range(10,20):
        stack_linked.push(_)
    print("0>>>>>>>>>>:",stack_linked.size())

    print("-----"*10)

    for _ in stack_linked:
        print("1>>>>>>>>>>:",stack_linked.peek())

    print("-----"*10)

    for _ in range(0,10):
        print("1_1>>>>>>>>:",stack_linked[_])

    print("-----"*10)

    for _ in stack_linked:
        print("2>>>>>>>>>>:",_)

    print("-----"*10)

    print("3>>>>>>>>>>>>>:",stack_linked.isEmpty())

    print("-----"*10)

    for _ in range(0,10):
        pop_value=stack_linked.pop()
        print("4>>>>>>>>>>:",pop_value)

    print("-----"*10)

    print("5>>>>>>>>>>:",stack_linked.isEmpty())

def check_postfix_expression():
    """
    检查后缀表达式的输出结果
    :return:
    """
    expression_01="(2+18)/12"
    expression_list_01=Evaluate().generate_postfix_expression(expression_01)
    print(expression_01," >>>>>>>> ",expression_list_01)

    expression_02="((2+18)/12+144/6.89)/90.28"
    expression_list_02=Evaluate().generate_postfix_expression(expression_02)
    print(expression_02," >>>>>>>> ",expression_list_02)

    expression_03="89+(89/33.3-12*(3+23)*4)"
    expression_list_03=Evaluate().generate_postfix_expression(expression_03)
    print(expression_03," >>>>>>>> ",expression_list_03)

def check_calculation():
    """
    检查计算的结果(运用后缀表达式)
    :return:
    """
    expression_01="(2+18)/12"
    expression_list_01=Evaluate().generate_postfix_expression(expression_01)
    val=Evaluate().calculate_expression(expression_01)
    print(expression_01,"=",eval(expression_01)," >>>>>>>> ",expression_list_01,"=",val)

    expression_02="((2+18)/12+144/6.89)/90.28"
    expression_list_02=Evaluate().generate_postfix_expression(expression_02)
    val=Evaluate().calculate_expression(expression_02)
    print(expression_02,"=",eval(expression_02)," >>>>>>>> ",expression_list_02,"=",val)

    expression_03="89+(89/33.3-12*(3+23)*4)"
    expression_list_03=Evaluate().generate_postfix_expression(expression_03)
    val=Evaluate().calculate_expression(expression_03)
    print(expression_03,"=",eval(expression_03)," >>>>>>>> ",expression_list_03,"=",val)


if __name__=="__main__":
    check_expression_split()
    print("-"*1000)
    check_stack()
    print("-"*1000)
    check_postfix_expression()
    print("-"*1000)
    check_calculation()
“”“
输出结果
((2+18)/12+144/6.89)/90.28  >>>>>>>>  ['(', '(', 2.0, '+', 18.0, ')', '/', 12.0, '+', 144.0, '/', 6.89, ')', '/', 90.28]
89+(89/33.3-12*(3+23)*4)  >>>>>>>>  [89.0, '+', '(', 89.0, '/', 33.3, '-', 12.0, '*', '(', 3.0, '+', 23.0, ')', '*', 4.0, ')']
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0>>>>>>>>>>: 10
--------------------------------------------------
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
1>>>>>>>>>>: 19
--------------------------------------------------
1_1>>>>>>>>: 10
1_1>>>>>>>>: 11
1_1>>>>>>>>: 12
1_1>>>>>>>>: 13
1_1>>>>>>>>: 14
1_1>>>>>>>>: 15
1_1>>>>>>>>: 16
1_1>>>>>>>>: 17
1_1>>>>>>>>: 18
1_1>>>>>>>>: 19
--------------------------------------------------
2>>>>>>>>>>: 10
2>>>>>>>>>>: 11
2>>>>>>>>>>: 12
2>>>>>>>>>>: 13
2>>>>>>>>>>: 14
2>>>>>>>>>>: 15
2>>>>>>>>>>: 16
2>>>>>>>>>>: 17
2>>>>>>>>>>: 18
2>>>>>>>>>>: 19
--------------------------------------------------
3>>>>>>>>>>>>>: False
--------------------------------------------------
4>>>>>>>>>>: 19
4>>>>>>>>>>: 18
4>>>>>>>>>>: 17
4>>>>>>>>>>: 16
4>>>>>>>>>>: 15
4>>>>>>>>>>: 14
4>>>>>>>>>>: 13
4>>>>>>>>>>: 12
4>>>>>>>>>>: 11
4>>>>>>>>>>: 10
--------------------------------------------------
5>>>>>>>>>>: True
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(2+18)/12  >>>>>>>>  [2.0, 18.0, '+', 12.0, '/']
((2+18)/12+144/6.89)/90.28  >>>>>>>>  [2.0, 18.0, '+', 12.0, '/', 144.0, 6.89, '/', '+', 90.28, '/']
89+(89/33.3-12*(3+23)*4)  >>>>>>>>  [89.0, 89.0, 33.3, '/', 12.0, 3.0, 23.0, '+', '*', 4.0, '*', '-', '+']
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(2+18)/12 = 1.6666666666666667  >>>>>>>>  [2.0, 18.0, '+', 12.0, '/'] = 1.6666666666666667
((2+18)/12+144/6.89)/90.28 = 0.24996147019035977  >>>>>>>>  [2.0, 18.0, '+', 12.0, '/', 144.0, 6.89, '/', '+', 90.28, '/'] = 0.24996147019035977
89+(89/33.3-12*(3+23)*4) = -1156.3273273273273  >>>>>>>>  [89.0, 89.0, 33.3, '/', 12.0, 3.0, 23.0, '+', '*', 4.0, '*', '-', '+'] = -1156.3273273273273
”“”