栈的最小值
该问题是“实现一个空栈存储数值,其支持一般的\(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\)运算只需返回“历史最小值”栈的栈顶即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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)\)。
1 2 3 4 5 6 7 8 | 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\)的“功能”,具体程序如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | 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)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | 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类中的最大值,具体程序如下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | 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)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | 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′,’-‘]。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | 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 |