栈相关问题 – JONY'S WORDPRESS

栈的最小值

该问题是“实现一个空栈存储数值，其支持一般的 $push,pop$ ，以及用于求当前栈中最小值的 $min$ 运算，要求3个运算的时间复杂度都是 $O(1)$ ”。问题要求找最小值的代价是 $O(1)$ ，那只能在 $push,pop$ 的过程中用额外空间维护一些关于最小值的信息。假设栈只有 $push$ 运算，那只需1个额外变量就能记录栈中的最小值，但当存在 $pop$ 运算时，如果最小值元素被 $pop$ 了，那就只能遍历寻找新的最小值，代价就不再是 $O(1)$ 。这里就需要注意到栈的一个性质，即“每次 $pop$ 后栈会回到最后一次 $push$ 前的状态”。这说明如果用一个结构顺序记录每次 $push$ 后的“历史最小值”，那么 $pop$ 后的最小值就是这个结构中的倒数第2条记录，然而倒数第一条记录因为 $pop$ 结束已经没意义了，应从中删除，这又说明这个结构也很适合用栈实现。

下面给出具体程序，其通过和原栈“同步”的另一个栈记录“历史最小值”。由于这两个栈是同步 $push,pop$ 的，所以这个程序 $push,pop$ 也是 $O(1)$ 代价的，而对于 $min$ 运算只需返回“历史最小值”栈的栈顶即可。

class MinStack:
    
    def __init__(self):
        self.arr = []
        self.minArr = []

    def push(self, number):
        self.arr.append(number)
        if self.minArr:
            number = min((number, self.minArr[-1]))
        self.minArr.append(number)

    def pop(self):
        self.minArr.pop()
        return self.arr.pop()

    def min(self):
        return self.minArr[-1]

class MinStack:

def __init__(self):

self.arr = []

self.minArr = []

def push(self, number):

self.arr.append(number)

if self.minArr:

number = min((number, self.minArr[-1]))

self.minArr.append(number)

def pop(self):

self.minArr.pop()

return self.arr.pop()

def min(self):

return self.minArr[-1]

下一个更大的数

该问题是“给定无重复的乱序整数数组，求每个数右边离其最近的更大的数。用程序语言内置map/dict存储“元素”到“结果”的映射，元素没有对应结果时无需存储。要求程序的代价为 $O(n)$ ，前提是假定程序语言内置的map/dict执行写入操作的代价是 $O(1)$ ，对于大多数语言也确实是这样”。利用栈解决该问题的核心步骤如下：

1) 读取数组下一个数并计为 $n$ ；

2) 如果栈为空或栈顶元素小于 $n$ ，就将 $n$ 入栈。然后回到(1)；

3) 循环出栈直到栈空或栈顶元素大于 $n$ ，这些出栈元素对应的解都是 $n$ 。然后回到(1)；

具体程序如下，可以发现这是个嵌套两层的循环，外层的代价是固定的 $O(n)$ ，栈至多执行 $O(n)$ 次入栈，内层虽然有while但由于栈至多执行 $O(n)$ 次出栈，所以 $while$ 的循环次数至多为 $O(n)$ ，所以程序的代价就是 $O(n)$ 。

def f(arr):
    result = {}
    stack = []
    for i in arr:
        while stack and stack[-1] < i:
            result[stack.pop()] = i
        stack.append(i)
    return result

def f(arr):

result = {}

stack = []

for i in arr:

while stack and stack[-1] < i:

result[stack.pop()] = i

stack.append(i)

return result

合法的括号匹配

该问题可描述为“四则运算中常用括号表明运算次序，虽然小括号足够用，但为阅读方便也会用中括号和大括号。这些括号必须成对出现和“左开右闭”，每对括号内都不能有未闭合的其他括号。括号匹配问题要求检查字符串中的小中大括号是否合法，为了简化问题，字符串中不会包含数字和运算符号，仅由“( [ { } ] )”这6种字符组成”。问题的关键在于归纳适合程序实现的判断逻辑，假设有张表 $T$ 记录哪些括号未闭合、以及这些括号的打开顺序，然后分情况讨论：

1) 读字符串的下一位字符，如果没有字符则认为匹配成功；

2) 当读到表示打开的“( [ {”时，就在 $T$ 中记录一下；

3) 当读到表示关闭的“} ] )”时，就要去 $T$ 查看最后一次打开的括号是什么，这里分情况讨论：

3.1) 没有最后一次打开的括号或不匹配：该括号没成对出现或内部有未闭合的括号，可判定为不合法；

3.2) 能匹配最后一次打开的括号：这时这对括号已经成功匹配，对问题不再有影响所以删掉 $T$ 中这个括号打开的记录，这时 $T$ 中最后一次打开的括号就是倒数第二次打开的括号，回到步骤(1)；

上面的讨论很容易变成程序，而且非常适合用栈来提供 $T$ 的“功能”，具体程序如下：

def f(string):

    stack = []

    for w in string:
        if w in "([{":
            stack.append(w)
        elif not stack:
            return False
        else:
            if w == ')' and stack[-1] != '(':
                return False
            if w == ']' and stack[-1] != '[':
                return False
            if w == '}' and stack[-1] != '{':
                return False
            stack.pop()

    if stack:
        return False
    return True

def f(string):

stack = []

for w in string:

if w in "([{":

stack.append(w)

elif not stack:

return False

else:

if w == ')' and stack[-1] != '(':

return False

if w == ']' and stack[-1] != '[':

return False

if w == '}' and stack[-1] != '{':

return False

stack.pop()

if stack:

return False

return True

删除不匹配的小括号

该问题可描述为“给定一个字符串，其仅含字符、'(‘、’)’，字符可在任意位置，当小括号不匹配时，至少删掉共多少个左括号或右括号，才能使剩下的所有小括号匹配，并输出其中一种删完后的字符串”。因为字符串中有字符，所以不方便直接把字符串装入栈中，这里用栈存放左右括号的下标。具体流程如下：

1) 初始化 $left,right$ 两个数组，分别存储左括号和右括号， $left$ 会作为栈使用；

2) 读取下一个字符并计为 $x$ ；

3) 如果 $x$ 为左括号，则将 $x$ 的下标入栈 $left$ ，然后回到(2)；

4) 如果 $x$ 为右括号，分两种情况讨论：

4.1) 如果 $left$ 非空，说明成功“关闭”一个左括号， $left$ 出栈一次，然后回到(2)；

4.2) 如果 $left$ 为空，说明右括号前没有“待关闭”的左括号，将当前 $x$ 的下标存入 $right$ ，然后回到(2)；

程序结束时若 $left,right$ 都为空，则说明能够括号本来就是匹配的。否则在原字符串中删掉 $left,right$ 剩余的下标后能正确匹配。这里简单讨论下匹配失败的原因，其可分成3类情况：

1) 左括号多了。对应于 $left$ 非空， $right$ 空的情形；

2) 右括号多了。对应于 $left$ 空， $right$ 非空的情形；

3) 存在一个纵轴，轴左边右括号多了，轴右边左括号多了。对应于 $left,right$ 都非空的情形；

根据这3类情况可确定，至少删掉 $|left|$ 个左括号和 $|right|$ 个右括号才能匹配，而 $left,right$ 记录的下标刚好提供了种删除方案。下面是程序，其时间复杂度是 $O(n)$ ，判断元素是否在Python的set数据类型中的代价是 $O(1)$ 。

def f(s):

    left = []
    right = []

    for i in range(len(s)):

        if s[i] == '(':
            left.append(i)
            
        elif s[i] == ')':
            if left:
                left.pop()
            else:
                right.append(i)
    
    left = set(left)
    right = set(right)
    
    result = []
    for i in range(len(s)):
        if not(i in left or i in right):
            result.append(s[i])

    return ''.join(result)

def f(s):

left = []

right = []

for i in range(len(s)):

if s[i] == '(':

left.append(i)

elif s[i] == ')':

if left:

left.pop()

else:

right.append(i)

left = set(left)

right = set(right)

result = []

for i in range(len(s)):

if not(i in left or i in right):

result.append(s[i])

return ''.join(result)

最长有效小括号

该问题是“给定字符串，其仅由'(‘、’)’组成，求该字符串能正确匹配的最长子串长度”。这个问题是比前面更难一点的匹配问题，这里回到前面讨论的“删除不匹配的小括号”问题，程序结束时若 $left,right$ 中都有记录，那么 $left,right$ 中的下标都是升序的，根据前面讨论过的第3种匹配失败情况， $right$ 中的所有下标都一定小于 $left$ 中的。如果按 $right$ 在左 $left$ 在右边拼接这两个数组得到新数组 $indexs$ ，那么能正确匹配的最长子串的长度是“字符串最左端到 $index[0]$ 下标”、“ $index[-1]$ 下标到字符串最右端”、“ $index$ 相邻两元素”这3类中的最大值，具体程序如下。

def f(s):

    left = []
    right = []

    for i in range(len(s)):

        if s[i] == '(':
            left.append(i)
            
        elif s[i] == ')':
            if left:
                left.pop()
            else:
                right.append(i)
    
    indexs = right + left
    length = 0

    if not indexs:
        length = len(s)
    else:
        for i in range(len(indexs)):
            if i == 0:
                length = indexs[i]
            if i == len(indexs) - 1:
                length = max(length, len(s) - 1 - indexs[i])
            if i > 0:
                length = max(length, indexs[i] - indexs[i-1] - 1)

    return length

def f(s):

left = []

right = []

for i in range(len(s)):

if s[i] == '(':

left.append(i)

elif s[i] == ')':

if left:

left.pop()

else:

right.append(i)

indexs = right + left

length = 0

if not indexs:

length = len(s)

else:

for i in range(len(indexs)):

if i == 0:

length = indexs[i]

if i == len(indexs) - 1:

length = max(length, len(s) - 1 - indexs[i])

if i > 0:

length = max(length, indexs[i] - indexs[i-1] - 1)

return length

小括号的得分

该问题是“给定字符串，其仅由'(‘、’)’组成，其中所有括号都是匹配的。然后定义记分规则，(XXX)的得分为XXX的得分乘2，XXX为空时得1分，比如()得1分，(()()())得6分，(((())))得8分。求给定字符串的得分”。解决这个问题的思路是把“部分得分”也丢到栈中，最后栈中剩下的“部分得分”之和就是总得分，具体步骤如下：

1) 读下一个字符并计为 $i$ ；

2) 如果 $i$ 为”(“，则入栈 $i$ ，回到步骤(1)；

3) 如果 $i$ 为”)”，此时分情况讨论如下：

3.1) 如果栈顶为”(“，此时出栈一次，然后入栈数字1，回到步骤(1)；

3.2) 如果栈顶为数字，则循环出栈直到出栈”(“，前面出栈的元素都是数字，求和乘2后入栈，最后回到步骤(1)；

读完所有字符后程序退出，栈中剩下的元素的和就是得分。这个程序的正确性在于能够让非“直接关闭”的括号之间有数字，关闭这种括号时要先把括号里面的分加起来，最后乘2，这个计算分数的过程和栈内左括号的关闭过程同步。

具体程序如下，虽然内层有while循环，但由于入栈次数为 $n$ ，所以代价是 $O(n)$ 。

def f(s):
    stack = []
    
    for i in s:
        if i == '(':
            stack.append('(')
        else:
            x = 0
            while stack[-1] != '(':
                x += stack.pop()
            stack.pop()
            stack.append(1 if x==0 else 2*x)

    return sum(stack)

def f(s):

stack = []

for i in s:

if i == '(':

stack.append('(')

else:

x = 0

while stack[-1] != '(':

x += stack.pop()

stack.pop()

stack.append(1 if x==0 else 2*x)

return sum(stack)

检查和计算布尔表达式

布尔表达式是数字电路中的基本数学工具。该问题为“给定布尔表达式字符串，计算表达式的值。输入是多个true、false、 and、or组合成的字符串，单词间用一个空格作分隔，字符串首尾无空格。输入不保证合法(比如true true and)，合法时返回字符串的true或false，否则返回字符串error。注意and运算的优先级大于or”。

判定是否合法很简单，能按3个一组读到的是“布尔，运算，布尔”即合法。如果运算优先级一样，可以把单词全部放入栈，按3个一组出栈计算结果，再把结果入栈，循环该过程直到栈只有1个元素，该元素就是计算结果。但由于and优先级更高，这样计算会导致错误结果，考虑到没有括号，可直接把所有and计算出来，最后只剩or就很好办了。具体流程如下：

1) 初始化栈 $s_1,s_2$ ，把所有单词从右到左入栈 $s_1$ ；

2) 若 $s_1$ 有大于等于3个元素，取出3个判断其是否是“布尔，运算，布尔”，不是就返回error，否则分情况讨论：

2.1) 若这3个元素包含and，则进行计算并把计算结果入栈 $s_1$ ；

2.2) 若这3个元素包含or，则将前2个入栈 $s_2$ ，最后1个入栈 $s_1$ ；

3) 若 $s_1$ 仅有1个元素，判断这个元素是否为“布尔”，如果不是就返回error，否则其出栈并入栈 $s_2$ ，这时 $s_2$ 是计算完所有and的布尔表达式，其只会有or，可以用前面的方法直接计算出表达式的值；

程序实现如下，其相当于遍历两次，所以时间复杂度为 $O(n)$ 。

isBool = lambda x: x == 'true' or x == 'false'
isAnd = lambda x: x == 'and'
isOr = lambda x: x == 'or'
isOpt = lambda x: isAnd(x) or isOr(x)
isExpr = lambda x,y,z: isBool(x) and isOpt(y) and isBool(z)

def compute(a, o, b):
    a = a == 'true'
    b = b == 'true'
    o = (a and b) if isAnd(o) else (a or b)
    o = 'true' if o else 'false'
    return o

def f(s):

    s1 = s.split(' ')
    s1.reverse()
    s2 = []

    while s1:
        if len(s1) >= 3:
            a,b,c = s1.pop(),s1.pop(),s1.pop()
            if not isExpr(a, b, c):
                return "error"
            if isAnd(b):
                s1.append(compute(a, b, c))
            else:
                s2.append(a), s2.append(b), s1.append(c)
        elif len(s1) == 1:
            if not isBool(s1[0]):
                return "error"
            s2.append(s1.pop())

    while s2:
        if len(s2) == 1:
            return s2.pop()
        a,b,c = s2.pop(),s2.pop(),s2.pop()
        s2.append(compute(a,b,c))

    return "error"

isBool = lambda x: x == 'true' or x == 'false'

isAnd = lambda x: x == 'and'

isOr = lambda x: x == 'or'

isOpt = lambda x: isAnd(x) or isOr(x)

isExpr = lambda x,y,z: isBool(x) and isOpt(y) and isBool(z)

def compute(a, o, b):

a = a == 'true'

b = b == 'true'

o = (a and b) if isAnd(o) else (a or b)

o = 'true' if o else 'false'

return o

def f(s):

s1 = s.split(' ')

s1.reverse()

s2 = []

while s1:

if len(s1) >= 3:

a,b,c = s1.pop(),s1.pop(),s1.pop()

if not isExpr(a, b, c):

return "error"

if isAnd(b):

s1.append(compute(a, b, c))

else:

s2.append(a), s2.append(b), s1.append(c)

elif len(s1) == 1:

if not isBool(s1[0]):

return "error"

s2.append(s1.pop())

while s2:

if len(s2) == 1:

return s2.pop()

a,b,c = s2.pop(),s2.pop(),s2.pop()

s2.append(compute(a,b,c))

return "error"

计算逆波兰式

逆波兰式又叫后缀表达式，是把二元运算写成“操作数，操作数，运算符”的表达式。人们更习惯使用“操作数，运算符，操作数”形式的中缀表达式，比如算术表达式。如无特殊说明，一般直接把算术表达式的逆波兰记法直接称为逆波兰式。例如算术表达式“(2+10)*3”对应的逆波兰式是“2 10 + 3 *”，可发现括号在逆波兰式中无意义。手算逆波兰式时可从左到右读，读到算符就将其和前两个数运算，并把结果放回。该过程容易用栈模拟，事实上逆波兰式比算术表达式更“适合计算机”。程序如下，输入是字符串数组形式的合法逆波兰式，只含+-*/和整数，比如[’10’,’-30′,’-‘]。

def f(arr):
    
    stack = []

    for i in arr:
        if i in ('+','-','*','/'):
            b,a = stack.pop(), stack.pop()
            if i == '+':
                stack.append(a+b)
            if i == '-':
                stack.append(a-b)
            if i == '*':
                stack.append(a*b)
            if i == '/':
                stack.append(a//b)
        else:
            stack.append(int(i))

    return stack.pop()

def f(arr):

stack = []

for i in arr:

if i in ('+','-','*','/'):

b,a = stack.pop(), stack.pop()

if i == '+':

stack.append(a+b)

if i == '-':

stack.append(a-b)

if i == '*':

stack.append(a*b)

if i == '/':

stack.append(a//b)

else:

stack.append(int(i))

return stack.pop()

中缀表达式转换为逆波兰式(调度场算法)

广义上中缀表达式可包含任意多种二元运算和优先级，只要运算能写作“<操作数, 运算符, 操作数>”的，比如布尔表达式就是中缀表达式。但本文为方便还是用“小括号整数四则运算表达式”讨论，为了有2个以上的优先级，再加上幂算符x^y表示x的y次方，优先级高于乘除。这里规定输入为形如[(, 2,-,-3, ), /, 11,^,2]的字符串数组，需注意这里唯一的运算规则是“括号内最优先，高优先级优先，同优先级左边优先”，不能下意识的默认使用算术表达式中的交换律、分配律等，因为一般的二元运算不一定满足。换句话说，计算结果一样的逆波兰式不一定算“原式的逆波兰式”。

调度场算法(Shunting Yard Algo)是该问题的标准算法，由著名荷兰计算机科学家Dijkstra提出，其得名于火车站用轨道作“栈”管理车厢次序的方法。上图是该算法流程的一个具体例子，有输入、符号栈、输出3个结构，为了方便描述把它们都当成栈，并分别计为 $s_1,s_2,s_3$ ，栈顶分别在左端，上端，右端。并且把逆波兰式递归定义成“1个逆波兰式是空、1个数、1个<子逆波兰式1, 子逆波兰式2, 算符>”。这里具体分析下步骤，就用上图的例子：

1) $s_1$ 出栈A，此时 $s_2$ 为空， $s_1$ 栈顶为+，说明之前没有运算会作用于A，能确定这个新逆波兰式1是“<A, 待定子式2, +>”的结构，子式2无法确定，因为不知道后面+的是什么(后面如果是X*Y就是+X*Y，如果是X-Y才是+X)。可以把A入栈 $s_3$ 作为确定的结果，但把+从 $s_1$ 出栈并入栈 $s_2$ ，为了等子式1确定方可入栈 $s_3$ ；

2) $s_1$ 出栈B，此时 $s_2$ 栈顶是+， $s_1$ 栈顶为*，说明之前没有比*更高优先级的运算会作用于B，子式2也只能确定是“<B，待定子式3，*>”的结构，式1就是“<A，B，待定子式3，*，+>”，子式3无法确定，因为不知道后面*的是什么。可以把B入栈 $s_3$ 作为确定的结果，但把*从 $s_1$ 出栈并入栈 $s_2$ ，为了等子式1确定方可入栈 $s_3$ ；

3) $s_1$ 出栈C，此时 $s_2$ 栈顶是*， $s_1$ 栈顶为-，说明*要优先计算，子式2确定是“<B，C，*>”，把C入栈 $s_3$ ，再把*从 $s_2$ 出栈并入栈 $s_3$ 。此时不代表式1也确定了，此时 $s_2$ 栈顶是+，由于-+优先级一样且+在左，所以+要优先计算，子式1确定是“<A，B，C，*，+>”，把+从 $s_2$ 出栈并入栈 $s_3$ 。然后开启新逆波兰式4为“<子式1，待定子式5，->”，把-入栈 $s_2$ ，为了等子式5确定方入栈 $s_3$ ；

4) $s_1$ 出栈D，此时 $s_2$ 栈顶是-， $s_1$ 为空，说明这步只能给-计算，子式5确定为D，所以把D入栈 $s_3$ ，把-从 $s_2$ 出栈并入栈 $s_3$ ，最后得到“<子式1，D，->”即“<A，B，C，*，+，D，->”；

算法之所以设立专门存符号的栈 $s_2$ ，是因为符号在逆波兰式末端，当“递归”解析完“子逆波兰式”后，可直接把符号出栈，把“子逆波兰式”夹在中间即可。这个逻辑显然能推广到任意多个优先级的情况。

最后分析怎么处理括号，最简单的方法是直接把括号当成“子中缀表达式”并对其递归上述步骤，但这里还是考虑修改一些上述逻辑使其直接支持括号，当读到左括号“(”时首先要避免括号左边的运算符( $s_2$ 栈顶)对括号的影响，一种方法是把”(“当成一个优先级极高的算符压入栈 $s_2$ ，这样做之后，括号内第一个数会按上述(2)的步骤走下去，就跟解析一个新的中缀表达式一样。之后读到右括号“)”时，要当成解析完一整个中缀表达式那样，把 $s_2$ 循环的出栈并入栈 $s_3$ ，直到遇到之前放入的左括号“(”后将其出栈丢弃。这样就等效于把一个括号中的内容变成一个逆波兰式并放在 $s_1$ 正确的位置上。

具体程序如下，由于 $s_1$ 中每个元素至多有2次出栈、2次入栈，所以时间复杂度是 $O(n)$ 。

def f(arr):

    p = { 
        '+': 1, 
        '-': 1, 
        '*': 2, 
        '/': 2, 
        '^': 3, 
    }

    s1, s2, s3 = [i for i in reversed(arr)], [], []

    while s1:
        if s1[-1] in p:
            if s2 and s2[-1] in p and p[s2[-1]] >= p[s1[-1]]:
                s3.append(s2.pop())
            else:
                s2.append(s1.pop())
        elif s1[-1] == '(':
            s2.append(s1.pop())
        elif s1[-1] == ')':
            s1.pop()
            while s2:
                x = s2.pop()
                if x == '(':
                    break
                s3.append(x)
        else:
            s3.append(s1.pop())
    
    while s2:
        s3.append(s2.pop())
    
    return s3

def f(arr):

p = {

'+': 1,

'-': 1,

'*': 2,

'/': 2,

'^': 3,

}

s1, s2, s3 = [i for i in reversed(arr)], [], []

while s1:

if s1[-1] in p:

if s2 and s2[-1] in p and p[s2[-1]] >= p[s1[-1]]:

s3.append(s2.pop())

else:

s2.append(s1.pop())

elif s1[-1] == '(':

s2.append(s1.pop())

elif s1[-1] == ')':

s1.pop()

while s2:

x = s2.pop()

if x == '(':

break

s3.append(x)

else:

s3.append(s1.pop())

while s2:

s3.append(s2.pop())

return s3

发表评论 取消回复

发表评论取消回复