Stack

As before, python doesn't actually have a basic data structure like stack, but we use the basic data structure of list to construct the operation of stack. The basic operations we involved are no different from the previous queue operation functions, but the corresponding function input parameters need to be changed.

a:list
#Push 
a.append()
#Out of stack
a,pop()
#Judge length
len(a)
#Sum
sum(a)

In fact, the data structure of the stack is just a way of description. The real importance is his last in first out idea (LIFO). Don't be too rigid in nouns.

Application of stack

Reverse order output

Example 5.4

operate=int(input())
#How to obtain the overall input of a line as an input use case
oplist=input().split(" ")
for i in range(operate):
    print(int(oplist.pop()),end=" ")

This question is a bit frightening. The core is zero complexity transfer of the sequence is the reverse of this sequence

parenthesis matching

As long as you know the idea of stack, it can be said to be very easy to do. In fact, it is a process of pressing stack, matching and then popping up. If there are parentheses, press the stack, and then match the corresponding parentheses. Pay attention to the idea of using the stack. Sometimes we need to observe the elements at the top of the stack. At this time, it's not too cool to use python's array slice

a:list
#Stack top element view
a[-1]

Example 5.5

inpoutstr=")(rttyy())sss)("
stack=[];result=[]
for num,opr in enumerate(inpoutstr):
    if(opr=="(" or opr==")"):
        if(len(stack)==0):
            stack.append([opr,num])
        elif(stack[-1][0]=="(" and opr==")"):
            stack.pop()
        else:
            stack.append([opr,num])
print(inpoutstr)
for i in range(len(inpoutstr)):
    if i==stack[0][1]:
        flag=stack.pop(0)
        if(flag[0]==")"):
            print("?",end="")
        if(flag[0]=="("):
            print("$",end="")
    else:
        print(" ",end="")

Expression evaluation

This problem is the typical use of stack, because you don't know whether there will be high priority operators after the priority of the expression value you enter, so we must press the stack.
The IDE and its pit on Zhejiang Niuke's Internet should be that their package is not installed and can't be input all the time, but we click the self-test input next to it, which is completely consistent. If we can't input it, how can we do OJ. There are two key points in this question
1. Operators and operands must be put into two stacks separately
2. Don't take it for granted to read the next number, because in fact, when you pop up the operator, you encounter the next operator. At this time, your two operands have been pushed into the stack. (my first illness)
Then python keeps two decimal places

    print("%.2f"%datap)

But in fact, I'll say here, ha, this problem was not done for python players from the beginning. In fact, if you are lazy, you can write the problem of execI() string directly. But here, in order to practice the use of stack, we still need to do it step by step.

datastack=[];caculatestack=[]
while 1:
# for _ in range(2):
    operatestr=input()
    operate=operatestr.split()
    if(operate[0]=="0" and len(operate)==1):
        break
    oplist=[];caculate="$"
    for i in operate:
        a=0
        if(len(oplist)==2 and caculate!="$"):
            result=0
            exec("result="+oplist[1]+caculate+oplist[0])
            datastack.append(str(result))
            oplist=[];caculate="$"
        if(i=="+" or i=="/" or i=="*" or i=="-"):
            if(i=="+" or i=="-"):
                if(len(caculatestack)>0):
                    if(caculatestack[-1]=="*" or caculatestack[-1]=="/"):
                        caculate=caculatestack.pop()
                        data=datastack.pop()
                        oplist.append(data)
                        data = datastack.pop()
                        oplist.append(data)
            caculatestack.append(i)
            #Please pay attention to the stack pressing position here. If you press the stack before judging the conditions, each stack pressing operation will be a new stack updated
        else:
            datastack.append(i)
    while(len(caculatestack)>0):
        caculate=caculatestack.pop()
        data = datastack.pop()
        oplist.append(data)
        data = datastack.pop()
        oplist.append(data)
        if (len(oplist) == 2 and caculate != "$"):
            result = 0
            exec("result=" + oplist[1] + caculate + oplist[0])
            datastack.append(str(result))
            oplist = [];
            caculate = "$"
    datap=float(datastack[0])
    print("%.2f"%datap)
    datastack=[];caculatestack=[]

Unfortunately, we can't look at the time complexity. There should be no overflow (such a small amount of data)
But this code is still very spicy, because I personally prefer the programming idea of using flag bits (poisoned by the hardware idea, so I don't bother to think about some design problems)

task

Exercise 5.1 use of stacks

There's nothing to say about this problem. It's easy to follow the steps

while True:
    stack=[]
    try:
        n = int(input());
        if(n==0):break
        for _ in range(n):
            order=input().split()
            if(order[0]=="A"):
                if(len(stack)>0):
                    print(stack[-1])
                else:
                    print("E")
            if(order[0]=="P"):
                stack.append(order[1])
            if(order[0]=="O"):
                try:
                    stack.pop()
                except:
                    pass
        print("")
    except:
        break;

Exercise 5.2 calculating expressions

This question is the same as that of the computer test of Zhejiang University. Together, he said that there is no space in the expression. It is better to do this. Just go through the corresponding string directly for.
However, operators and operands must be placed in two stacks, which is the top priority to solve this problem.

#-*-coding:utf-8 -*-
datastack=[];caculatestack=[]
while 1:
    operatestr = input()
    oplist=[];caculate="$"
    for i in operatestr:
        a=0
        if(len(oplist)==2 and caculate!="$"):
            result=0
            exec("result="+oplist[1]+caculate+oplist[0])
            datastack.append(str(result))
            oplist=[];caculate="$"
        if(i=="+" or i=="/" or i=="*" or i=="-"):
            if(i=="+" or i=="-"):
                if(len(caculatestack)>0):
                    if(caculatestack[-1]=="*" or caculatestack[-1]=="/"):
                        caculate=caculatestack.pop()
                        data=datastack.pop()
                        oplist.append(data)
                        data = datastack.pop()
                        oplist.append(data)
            caculatestack.append(i)
            #Please pay attention to the stack pressing position here. If you press the stack before judging the conditions, each stack pressing operation will be a new stack updated
        else:
            datastack.append(i)
    while(len(caculatestack)>0):
        caculate=caculatestack.pop()
        data = datastack.pop()
        oplist.append(data)
        data = datastack.pop()
        oplist.append(data)
        if (len(oplist) == 2 and caculate != "$"):
            result = 0
            exec("result=" + oplist[1] + caculate + oplist[0])
            datastack.append(str(result))
            oplist = [];
            caculate = "$"
    datap=float(datastack[0])
#     print(("%.2f"%datap)
    print(datap)
    datastack=[];caculatestack=[]