Microsoft 365中增加了很多新函数,使用这些新函数可以实现其他编程语言中的部分数据或数组操纵技巧,拓展工作表函数解决问题的新思路。本文通过一个寻找第n个左括号对应右括号位置的例子来介绍使用工作表函数模拟“栈”操作的一种方法。
一、什么是“栈”
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
例如,我们可以把序号堆积入栈,然后当符合条件时,从栈顶一个一个移除,相当于后进栈的先移出栈。
二、Excel工作表函数模拟入栈和出栈操作
在Excel中,可以使用VSTACK函数达到增加栈顶元素的目的,例如将数字5堆积到栈顶:
同样,利用DROP函数可以实现移除栈顶元素的目的:
如果当前栈里只有一个元素,移除这个元素时会产生错误值:
为了避免上述情况的出现,我们可以给栈设置一个初始值,例如0,这样有进栈元素后再移除不会产生错误:
三、求括号位置题目描述
下面,我们来正式说这个题目。相关原数据和描述如下图所示:
简单说,就是找出字符串中第n个左括号{对应的右括号}的位置。
四、解题思路分析
因为要模拟栈的操作,所以可以先想想一下这个栈的元素构成,为了避免错误,给栈一个初始值0,然后栈顶保留待匹配的{编号,栈底保留累计进过栈的{个数。
然后分几种情况来处理:
1)当字符是{时,将这个{的编号,也即从左到右是第几个},加入栈顶。例如第一个{入栈时,将1加在栈顶,生成数组{1;0}。那么怎么知道当前这个{是第几个{呢,因为我们维护的栈最底端会记录累计入过栈的{数量,所以要加入栈顶的{的编号就是栈底的数字+1。
2)当字符是{时还有一步要执行,就是将当前的{是第几个加入栈底,也就是将第1步的编号加在数组最下面。例如第一个{入栈时,将1加在栈顶后,将1也加在栈底,生成数组{1;0;1}。当然,这个步骤,也可以不将编号直接堆积在数组下面增加数组长度,可以动态更新数组最后一个值为上述编号,例如将原来的初始值更新成1,然后再将1堆积在上面,形成数组{1;1},但是公式处理会长一些。每次循环到{的时候,都会这样操作,记录累计有多少个{入过栈。
3)当字符是}时,这个}肯定是和栈顶编号的{匹配的,因为括号之间不交叉。此时,会分两种情况:
第一种情况,当栈顶的编号不等于n时,将栈顶的{编号做出栈处理,意味着这个编号的{有}匹配了。
第二种情况,当栈顶的编号等于n时,意味着当前的}就是和第n个{匹配的},这时,输出当前}的位置即可。
4)当字符不是{或},维持栈不变。
举几个简单的例子来说明楼上的解题步骤。
例1:字符串为“{}{a,{b,c}}”,n=1,结果返回2。
第一个字符是{,因此编号1入栈,栈底也变成1。第二个字符是},此时因为栈顶的编号是1,等于n,所以这个}就是和第一个{对应的},因此返回当前}的位置2。
例2:字符串为“{{}}{{a,b},{b,c}}”,n=2,结果返回3。
第一个字符是{,因此编号1入栈,数组变成{1;0;1}。第二个字符是{,因此编号2入栈,数组变成{2;1;0;1;2}。第3个字符是},此时因为栈顶的编号是2,等于n,所以这个}就是和第一个{对应的},因此返回当前}的位置3。
例3:字符串为“{}{}{{a,b}{c,{d,e}}}”,n=4,结果返回10。
步骤和前面一样,只不过当栈顶不等于n的时候,就要将栈顶数字出栈,表示已经有}与之匹配了。
五、具体公式及简要说明
有了上面的基础,我们就可以写出以下公式:
=-REDUCE(0,ROW($1:99),LAMBDA(x,y,IF(@x<0,x,SWITCH(MID(A2,y,1),"{",VSTACK(MAX(x)+1,x,MAX(x)+1),"}",IF(@x=B2,-y,DROP(x,1)),x))))
公式简要说明如下:
=-REDUCE(
0, 栈底初始值设置为0
ROW($1:99), 每个字符的位置
LAMBDA(x, y,
IF(
@x < 0, 返回结果位置后,将位置变成负数,判断如果是负数就保持x不变。
x,
SWITCH(
MID(A2, y, 1), 遍历每个字符
"{", VSTACK(MAX(x) + 1, x, MAX(x) + 1), 如果字符是{,栈顶和栈底都增加当前{的编号
"}", IF(@x = B2, -y, DROP(x, 1)), 如果字符是},如果栈顶=n,则返回位置的负数(即-y),否则弹出栈顶元素。
x 如果是其他字符,都保持栈不变。
)
)
)
)
图文作者:超人