java - 三元字符串到 Node 类

Question

我有一个面试问题仍然困扰着我，请帮忙。

您必须用 Java 编写一个带有 String 参数的方法。 该String 应该是三元运算符树 (a?b:c)。所以基本上它可以是这样的:
a？ g?h:j ? u?v:w : p : r?s:t

                            a
                          /   \
                     g?h:j     r?s:t 
                    /     \
               u?v:w       p

Something like that, I hope I even wrote it right, because I am really confused.

Then we have a class Node that has 2 fields: left and right:

class Node {
     char variableName;         
     Node left, right;
}

因此，您必须返回一个 Node ，其中包含该字符串中的所有节点(左、右)。

我希望这是可以理解的。如果您需要更多信息，我会提供，但这里的基本思想是让所有节点正确。我试图使用递归来做到这一点，并且我仍然相信这是正确的。但我不知道如何正确地做到这一点。

Answer 1

这个问题可以用一个非常简单的 recursive descent parser 来解决。问这个问题的目的是看看你是否可以实现一个递归有意义的递归算法，而不是要求你编写一个无聊的递归阶乘来看看你以前是否听说过递归。

这是一种可能的实现:

static class Parser {
    private int pos = 0;
    private String s;
    public Parser(String s) {
        this.s = s;
    }
    private void skipSpace() {
        while (pos != s.length() && Character.isWhitespace(s.charAt(pos))) {
            pos++;
        }
    }
    public Node parse() {
        skipSpace();
        Node res = new Node();
        res.variableName = s.charAt(pos++);
        skipSpace();
        if (pos == s.length()) return res;
        if (s.charAt(pos) == '?') {
            pos++;
            res.left = parse();
            skipSpace();
            if (pos == s.length() || s.charAt(pos) != ':') {
                System.err.println("Syntax error");
                return null;
            }
            pos++;
            res.right = parse();
        }
        return res;
    }
}

public static Node parse(String s) {
    Parser p = new Parser(s);
    return p.parse();
}

Demo.

这个想法是使用 parse() 方法，就像它已经编写一样:首先我们解析变量名称，然后检查它后面是否带有问号。如果是，我们使用问号，从当前位置解析成为左节点的内容，跳过冒号(如果冒号丢失则出错)，最后解析右节点。跳过空格。