调用栈也是栈

- hack

又到了秋招的季节,刷题的时候遇到了一道有趣的题,简化如下:

看到括号,第一反应当然是用栈。先想了一会有没有只扫描一遍字符串的做法,但是很可惜没想出来。最后想了一个先构造树,再在树上遍历的做法,解答如下。

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class NBString {
    public static void main(String[] args) {
        String s = "(()())()";
        NBNode root = buildTree(s);
        System.out.println(getNode(root) - 1);
    }

    public static NBNode buildTree(String s){
        NBNode root = new NBNode(null);
        char[] chars = s.toCharArray();
        Stack<NBNode> stack = new Stack<>();

        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];

            if(c=='('){
                NBNode father;
                if(stack.isEmpty()){
                    father = root;
                } else {
                    father = stack.peek();
                }

                NBNode newNode = new NBNode(father);
                father.child.add(newNode);
                stack.push(newNode);

            } else if (c==')'){
                stack.pop();
            }
        }

        return root;

    }

    public static int getNode(NBNode node){
        if(node==null) return 1;
        int layerProd = 1;
        for (NBNode NBNode : node.child) {
            layerProd *= getNode(NBNode);
        }
        return layerProd + 1;
    }

}

class NBNode {
    NBNode head;
    List<NBNode> child;

    public NBNode(NBNode _head){
        head = _head;
        child = new LinkedList<>();
    }
    
}

但是如果换个角度来看,其实题目描述的 NB 串,可以被视为是一个简单的类型定义,语法大致如下。然后要做的,就是把输入数据视作代码,构造抽象语法树,然后在语法树上操作得到结果了。

NBString = "" | "(" NBString ")" | NBString NBString

如果 OJ 提供了类似于 Haskell 之类内置支持模式匹配的语言,那么就很简单了:把输入 tokenize,写一个 calc 函数,然后直接按照题目要求写匹配规则和返回值就好了。伪代码如下。

calc :: NBString -> Int
calc = match str
	case "": return 1
	case "(" sub ")": return 1 + calc sub
	case sub1 sub2: return calc sub1 * calc sub 2

然而现实并没有这么美好。但是难道就应该就此放弃吗?未必。实际上编程语言内的调用栈,也是一个栈,或者说语言本身就提供了我们所期望的解析语法树的功能。高人指点之下,可以用以下的 hack 来实现:

def f(x=1):
    return x+1

s = "(()())()"
s = s.replace("(","f(").replace(")f(",")*f(")
print(eval(s))

上文代码所做的,实际上就是把输入串,替换成了一系列函数调用,并添加了符合题目要求的函数体。最后只需要直接调用 Python 内置的 eval,就可以得到正确的答案了。