Stack calculation (whether the order of entering and leaving the stack is legal) - Code

1） Learn about stacks

Stack can be understood as ：

A layered box , Only the top has an entrance . The value entered first must go down .

And when it comes to taking values outside , above , That is, those who went in later were taken out first , Those who enter first can only leave later . It's called ：“ First in, then out ”.

2） Example .

for example , The stack order is a,b,c,d,e, Find the illegal stack order ：

A. a,b,c,d,e

B. e,d,c,b,a

C. a,b,c,e,d

D. e,c,d,b,a

situation 1） All in , Then the stack order is :e,d,c,b,a(B Options ), Nothing to say .

situation 2） Single entry . One by one , Take... One by one . such as , Enter a value first a, And then not in the input value , But take it out first , Enter again b, take b, Enter into c, take c, wait . that , This stack order becomes a,b,c,d,e.（A Options ）

situation 3） Enter a part first , take , Enter again , Retake , wait . There are too many cases in this part , Think about it with your own understanding .

3） Program realization .

It may be difficult to teach a program how to judge such a complex situation , But let it “ Exhausting ” Can reflect its strengths .

#coding=utf-8
class ZHAN(object):
    def __init__(self):
        self.real=[]
    def add(self,other):
        self.real.append(other)
    def remove(self):
        return self.real.pop()
    def size(self):
        return len(self.real)
    def clear(self):
        self.real=[]
    def everything_out(self):
        a=self.real[::-1]
        self.clear()
        return a
    def canout(self):
        try:
            return self.real[-1]
        except IndexError:
            return None
def islegal(lt,choose_list):
    init=ZHAN()
    aa=0
    legal=[]
    illegal=[]
    for i in choose_list:
        aa+=1
        out=[]#8 25 14 87 51 90 6 19 20
        init.clear()
        for j in lt:
            init.add(j)
            try:
                while (i[len(out)]==init.canout()):
                    out.append(init.remove())
            except:
                pass
        print(out)
        if len(out)==len(i):
            print(f"{aa} legal .")
            legal.append(aa)
        else:
            print(f"{aa} illegal .")
            illegal.append(aa)
a=input(" Entry order ：")
sp=input(" Separator ")
if sp=="":
    a=list(a)
else:
    a=a.split(sp)
print(" Options :( This line does not enter content + Line feed stop input )")
b=[]
aa=0
while True:
    aa+=1
    z=input(f"{aa} term :")
    if sp!="":
        m=z.split(sp)
    else:
        m=list(z)
    if z!="":
        b.append(m)
    else:
        break

islegal(a,b)

First create a stack of entity data types , Then make an exhaustive analysis .

Let's take a look at the results ：

 Entry order ：abcde
 Separator 
 Options :( This line does not enter content + Line feed stop input )
1 term :abcde
2 term :edcba
3 term :abced
4 term :ecdba
5 term :
['a', 'b', 'c', 'd', 'e']
1 legal .
['e', 'd', 'c', 'b', 'a']
2 legal .
['a', 'b', 'c', 'e', 'd']
3 legal .
['e']
4 illegal .

Be careful , You can enter nothing at the separator , Line break directly , Indicates that each character is a separate value .