algorithm - 如何解析某类配置文件

Question

最近遇到一道面试题。我被要求编写用于表达式评估的代码。表达式格式如下所示:

   B=10;
   A={
      A=100;
      B=BDE;
      C=C;
      D={
         A=windows;
         B=mac;
      C={
         A=redhat;
         B=ubuntu;
        };
   };
   A+={
       A=200;
       E=1000;
      };

为了表示表达式的键，使用句点分隔的方法。例如A.B表示Map A中的元素B，A.B的值为BDE；同样，A.D.C.A的值是redhat。表示的字符串称为“路径表达式”。

配置还支持附加和覆盖操作。对于上面的例子，我们使用+=操作追加或覆盖了Map A中的值，此时A.A的值为200，A.E的值为1000；

现在，给定一个配置字符串和配置的关键路径，我需要根据配置字符串返回配置值。

规则

1) 键名和他的值只包含字母(A-Z,a-z)和数字(0-9)，没有其他字符；

2) 如果找不到值或表达式指向映射，请输出“N/A”

3) 如果找到值，请输出值。输出值时没有空格。

输入输出

输入分为三部分。第一行有两个整数，分别表示配线数(M)和表达式数(N)。

M<=100，N<=100。接下来的 M 行是配置，最后 N 行是表达式。每个配置行包含一个或多个配置。每行长度小于 1000。

输入:

2 2

A={A=1;B=2;C=3;E={A=100;};};

A+={D=4;E={B=10;C=D;};};

A.E.B

B.D.E

输出

A.E.B=10

B.D.E=N/A

我的想法

我正在考虑使用 N 叉树来表示表达式。例如，表达式:A = {A = 1;D = 1;B = {C = 1,D = {D = 1,F = 2};};};可以表示为:

                            (A,-)
                         /    |    \
                      (A,1) (D,1)  (B,-)
                                  /    \
                                (C,1)   (D,-)
                                       /    \
                                     (D,1)  (F,2)

因为N-nary tree可以表示为二叉树。因此，所有附加或搜索操作都将是二叉树的插入或搜索操作。看来这种方法行得通。但我想知道是否有更好的方法来解决这个问题？

Answer 1

我正在考虑将所有 child 放在一个 HashMap 中(因为这是面试官喜欢的)

Node{
    String val;
    HashMap<String, Node> children;
    Node(int val){
        this.val = val;
        children = new HashMap<String, Node>();
    }
}