栈的最小值
该问题是“实现一个空栈存储数值，其支持一般的\(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 |