栈的计算（入栈出栈顺序是否合法）-代码

1）了解一下栈

栈可以这么理解：

一个分层箱子，只有上面有入口。先进入的值必然会到下面。

而到了向外取值的时候，上面的，也就是后进去的反而先被取了出来，先进入的只能后出。这叫做：“先入后出”。

2）例题。

例如，入栈顺序为a,b,c,d,e，求不合法的出栈顺序：

A. a,b,c,d,e

B. e,d,c,b,a

C. a,b,c,e,d

D. e,c,d,b,a

情况1）全入，那么出栈顺序为:e,d,c,b,a(B选项)，没什么可说的。

情况2）单入。一个一个入，一个一个取。比如，先入一个值a，然后不在入值，而是先把它取出来，再入b，取b,入c,取c,等等。那么，这样的出栈顺序则变成了a,b,c,d,e。（A选项）

情况3）先入一部分，取，再入，再取，等等。这部分情况太多，自己理解地去想想吧。

3）程序实现。

要想教给程序如何判断这么复杂的情况可能有些困难，但让它“穷举”则能体现出其长处。

#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.append(aa)
        else:
            print(f"{aa}不合法。")
            illegal.append(aa)
a=input("进入顺序：")
sp=input("分隔符")
if sp=="":
    a=list(a)
else:
    a=a.split(sp)
print("选项:(本行不输入内容+换行停止输入)")
b=[]
aa=0
while True:
    aa+=1
    z=input(f"{aa}项:")
    if sp!="":
        m=z.split(sp)
    else:
        m=list(z)
    if z!="":
        b.append(m)
    else:
        break
 
islegal(a,b)

先创建一个栈的实体数据类型，再进行穷举分析。

可以来看一下结果：

进入顺序：abcde
分隔符
选项:(本行不输入内容+换行停止输入)
1项:abcde
2项:edcba
3项:abced
4项:ecdba
5项:
['a', 'b', 'c', 'd', 'e']
1合法。
['e', 'd', 'c', 'b', 'a']
2合法。
['a', 'b', 'c', 'e', 'd']
3合法。
['e']
4不合法。

注意，分隔符处可以什么也不输，直接换行，表示每一个字符都是一个单独的值。