365新函数：求右括号位置-模拟“栈”操作

shaowu459

Office 365中增加了很多新函数，使用这些新函数可以实现其他编程语言中的部分数据或数组操纵技巧，拓展工作表函数解决问题的新思路。本帖通过一个寻找第n个左括号对应右括号位置的例子来介绍使用工作表函数模拟“栈”操作的一种方法。

本题是之前做的某道题的中间步骤，后来觉得有些意思，就提取出来专门制作了一题。就这个题目来说，有很多朋友提供了多种多样精彩的解法，有兴趣的朋友可以到群里下载公式汇总文件。

本帖主要介绍我自己使用REDUCE函数模仿“栈”的一种做法，该公式不是就这个问题的最优解，仅作为抛砖引玉目的，之前还有一些模仿其他语言编程思路的例题，等以后有机会再发，主要是因为Office 365里新函数做的公式想用文字来解释清楚难度比之前大很多。

shaowu459

首先，来介绍一下什么是栈（以下信息来自网络搜索结果）。栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。




例如，我们可以把序号堆积入栈，然后当符合条件时，从栈顶一个一个移除，相当于后进栈的先移出栈。

shaowu459

在Excel中，可以使用VSTACK函数达到增加栈顶元素的目的，例如将数字5堆积到栈顶：


同样，利用DROP函数可以实现移除栈顶元素的目的：


如果当前栈利只有一个元素，移除这个元素时会产生错误值：


为了避免上述情况的出现，我们可以给栈设置一个初始值，例如0，这样有进栈元素后再移除不会产生错误：

shaowu459

下面，我们来正式说这个题目。相关原数据和描述如下图所示：


简单说，就是找出第n个左括号{对应的右括号}在字符串中的位置。

shaowu459

因为要模拟栈的操作，所以可以先想想一下这个栈的元素构成，为了避免错误，给栈一个初始值0，然后栈顶保留待匹配的{编号，栈底保留累计进栈过的{个数。

然后分几种情况来处理：
1）当字符是{时，将这个{的编号，也即从左到右是第几个}，加入栈顶。例如第一个{入栈时，将1加在栈顶，生成数组{1；0}。那么怎么知道当前这个{是第几个{呢，因为我们维护的栈最底端会记录累计入过栈的{数量，所以要加入栈顶的{的编号就是栈底的数字+1。
2）当字符是{时还有一步要执行，就是将当前的{是第几个加入栈底，也就是将第1步的编号加在数组最下面。例如第一个{入栈时，将1加在栈顶后，将1也加在栈底，生成数组{1；0；1}。当然，这个步骤，也可以不将编号直接堆积在数组下面增加数组长度，可以动态更新数组最后一个值为上述编号，例如将原来的初始值更新成1，然后再将1堆积在上面，形成数组{1；1}，但是公式处理会长一些。每次循环到{的时候，都会这样操作，记录累计有多少个{入过栈。
3）当字符是}时，这个}肯定是和栈顶编号的{匹配的，因为括号之间不交叉。此时，会分两种情况：
第一种情况，当栈顶的编号不等于n时，将栈顶的{编号做出栈处理，意味着这个编号的{有}匹配了。
第二种情况，当栈顶的编号等于n时，意味着当前的}就是和第n个{匹配的}，这时，输出当前}的位置即可。
4）当字符不是{或}，维持栈不变。

shaowu459

举几个简单的例子来说明楼上的解题步骤。


例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的时候，就要将栈顶数字出栈，表示已经有}与之匹配了。

shaowu459

有了上面的基础，下面来看一下公式：

1. =-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，则返回-位置，否则弹出栈顶元素。
                x                                                           其他字符都保持栈不变。
            )
        )
    )
)

alan57

学习学习，曾想用x来循环解，奈何想不出来，正好学习下超人老师的。

shaowu459

使用同样的方法，求出字符串中所有的匹配括号位置。如字符串是“{{a,b}{b,{c,d}}}”。

1. =REDUCE({"左括号","右括号"},ROW(1:99),LAMBDA(x,y,SWITCH(MID(A2,y,1),"{",VSTACK(y,x),"}",VSTACK(DROP(x,1),HSTACK(@x,y)),x)))

复制代码

shaowu459

再来一个模拟栈应用的小题，将一系列连续单元格内容按顺序填充到数组的空位置中。
传统的方法，一般是会用公式统计从上到下空单元格的数量，然后引用D列待填充值。使用模拟栈的方法，可以不用这么做。将待填充值放在栈顶，遇到空单元格，逐个出栈，出栈的同时将栈顶元素堆积到栈底。

1. =REDUCE(+D2:D8,A1:A18,LAMBDA(x,y,IF(y>0,VSTACK(x,y),VSTACK(DROP(x,1),@x))))

复制代码