java - 递归解析路径

Question

我正在尝试解决这样的问题 -

给定键值映射的映射

["Intro",  "Hello My Name is %S% and I am x %Y old"]
["S", "Tom %N"]
["N", "Johnson"]
["Y", "Year"]

现在解析一个字符串 提供您的％Intro％S

我很难知道解决这个问题的最佳和优化方法是什么。我可以想到简单的递归，但我不知道这是否是最好的方法。我也在努力理解问题的时间复杂度。请注意，这可以达到任何深度。

我做了什么

 String resolve(String s, HashMap<String, String> m) {
        String[] st = s.split(" ");
        for(String word : st) {
            if(m.get(word) != null) {
                word = m.get(word);
            }
            if(word.contains("%")) {
                String p = resolve(parse(word), m);
                m.put(word, p);
            }
        }

        StringBuilder b = new StringBuilder();
        for(String word : st) {
            if(st.contains("%")) {
                b.append(m.get(word) + " ");
            } else {
                b.append(word + " ");
            }
        }
        return b.toString();
    }

Answer 1

如果您有很多表达式和依赖项，并且必须经常更新和获取值，则需要 dependency graph

(为简单起见，变量声明为 "My %var% is ..." 而不是 "My %var is ..." )

让下个Var包含变量的类(您的 [name, expr] )

@Getter
@Setter
@AllArgsConstructor
static class Var {
    String name;
    String[] parts; // Const1,  Var1, Const2,   Var2, ...
                    // Hello... `S`   and I am  `Y`   old ...
    String computed;

    Stream<String> getUsedVarNames() {
        // we are interested only in Var# not Const# then
        // we traverse the odd indexes
        return IntStream
           // for i=1,2,3,...,N/2-1
           .range(1, parts.length / 2)
           // get the var `2*i-1` that is 1,3,5,...
           .mapToObj(i -> parts[2 * i - 1]);
    }

    void updateValue(Map<String, Var> vars) {
        System.out.println("          Computing: " + name);
        // update the value is concat all
        //    Const1 + Var1 + Const2 + Var2, ...
        // then
        computed = IntStream
                // for i=0,1,2,...,N-1
                .range(0, parts.length)
                // if is even (i%2==0) take the Const-i
                // if is odd           take the Var-i value
                .mapToObj(i -> i % 2 == 0 ? parts[i] : vars.get(parts[i]).getComputed())
                // and concatenate all
                .collect(joining());
    }
}

哪里

• name是变量名称 S , N ，...
• parts是常数"Hello My..."位置 0、2、4、... 和变量名称 "S"在位置 1、3、5...(为了简单起见)
• computed是最后计算的值
• getUsedVarNames获取使用的变量名称(1、3、5、...位置)
• updateValue重新计算computed给定变量映射的值。

然后，基本依赖图管理基本上是

static class Graph {
    Map<String, Var> vars = new HashMap<>();
    Map<String, Set<String>> deps = new HashMap<>();

    String value(String name) {
        return vars.get(name).getComputed();
    }

    String add(String name, String expr) {
        remove(name);

        Var current = new Var(name, expr.split("%"), null);

        // add current dependencies
        current.getUsedVarNames().forEach(dep -> deps.get(dep).add(name));

        // add var
        vars.put(name, current);
        if(!deps.containsKey(name))
            deps.put(name, new HashSet<>());

        // compute
        updateDeps(name);

        return current.getComputed();
    }

    private void updateDeps(String name) {
        vars.get(name).updateValue(vars);
        deps.get(name).forEach(this::updateDeps);
    }

    void remove(String name) {
        if (vars.containsKey(name)) {
            vars.get(name).getUsedVarNames().forEach(dep -> deps.get(dep).remove(name));
            vars.remove(name);
        }
    }
}

哪里

• vars varName => the var .
• deps map parentVars => where are used .
• value只需获取 var 名称的计算值即可。
• add删除 var(如果存在)并设置依赖项。
• updateDeps走deps图更新依赖关系。
• remove删除 var 和依赖项。

然后，作为示例，您可以编写

Graph g = new Graph();

System.out.println(g.add("Y", "Year"));
System.out.println(g.add("N", "Johnson"));
System.out.println(g.add("S", "Tom %N%"));
System.out.println(g.add("Intro", "Hello My Name is %S% and I am x %Y% old"));

// if you change `S` only two expression are recomputed (the updated `S` and their dependencies)
System.out.println(g.add("S", "Peter %N%"));

System.out.println(g.value("Intro"));

带输出

          Computing: Y
Year
          Computing: N
Johnson
          Computing: S
Tom Johnson
          Computing: Intro
Hello My Name is Tom Johnson and I am x Year old
          Computing: S
          Computing: Intro
Peter Johnson
Hello My Name is Peter Johnson and I am x Year old

仅重新计算所需的表达式。

这是一个非常基本的依赖关系图管理(即，如果 var 不存在，你会得到一个 null)

(旁白，完整的示例代码)

package com.computermind.sandbox.algorithms;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.Setter;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import static java.util.stream.Collectors.joining;

public class DependencyGraph {

    public static void main(String... args) {

    Graph g = new Graph();

    System.out.println(g.add("Y", "Year"));
    System.out.println(g.add("N", "Johnson"));
    System.out.println(g.add("S", "Tom %N%"));
    System.out.println(g.add("Intro", "Hello My Name is %S% and I am x %Y% old"));

    // if you change `S` only two expression are recomputed (the updated `S` and their dependencies)
    System.out.println(g.add("S", "Peter %N%"));

    System.out.println(g.value("Intro"));

    }

    @Getter
    @Setter
    @AllArgsConstructor
    static class Var {
        String name;
        String[] parts;
        String computed;

        Stream<String> getUsedVarNames() {
            return IntStream.range(1, parts.length / 2).mapToObj(i -> parts[2 * i - 1]);
        }

        void updateValue(Map<String, Var> vars) {
            System.out.println("          Computing: " + name);
            computed = IntStream.range(0, parts.length)
                    .mapToObj(i -> i % 2 == 0 ? parts[i] : vars.get(parts[i]).getComputed())
                    .collect(joining());
        }
    }

    static class Graph {
        Map<String, Var> vars = new HashMap<>();
        Map<String, Set<String>> deps = new HashMap<>();

        String value(String name) {
            System.out.println("          Computing: " + name);
            return vars.get(name).getComputed();
        }

        String add(String name, String expr) {
            remove(name);

            Var current = new Var(name, expr.split("%"), null);

            // add current dependencies
            current.getUsedVarNames().forEach(dep -> deps.get(dep).add(name));

            // add var
            vars.put(name, current);
            if(!deps.containsKey(name))
                deps.put(name, new HashSet<>());

            // compute
            updateDeps(name);

            return current.getComputed();
        }

        private void updateDeps(String name) {
            vars.get(name).updateValue(vars);
            deps.get(name).forEach(this::updateDeps);
        }

        void remove(String name) {
            // remove current dependencies
            if (vars.containsKey(name)) {
                vars.get(name).getUsedVarNames().forEach(dep -> deps.get(dep).remove(name));
                vars.remove(name);
            }
        }
    }
}