4

これは、私が使用している解析済み xml ファイルの例であり、それをタブでツリー形式にします

commandList

  assign
    variable
      #text[a]
    expression-int
      #text[1]

  assign
    variable
      #text[b]
    expression-int
      #text[2]

  assign
    variable
      #text[c]
    expression-operation
      operator
        #text[OP_SET]
      arguments
        expression-variable
          variable
            #text[a]
        expression-variable
          variable
            #text[b]

  assign
    variable
      #text[d]
    expression-operation
      operator
        #text[OP_SET]
      arguments
        expression-operation
          operator
            #text[OP_TUPLE]
          arguments
            expression-int
              #text[1]
            expression-int
              #text[2]
        expression-operation
          operator
            #text[OP_TUPLE]
          arguments
            expression-int
              #text[3]
            expression-int
              #text[4]

この入力が理解するのが難しくないことを願っています。XML ファイルから解析されない場合、通常は次のようになります。

a := 1;
b := 2;
c := {1,2};
d := {(1,2),(3,4)};

等...

すべての割り当てペア (つまり、値と変数) はハッシュマップに格納されるため、その変数によって値を検索し、後の式で使用できます。文法に従って式を解決するために、再帰的降下評価器 (だと思いますか?) を使用します。

私は過去 24 時間にわたってあらゆる種類のものをグーグル検索し、基本的な算術演算 (2 + 3 * 8 など) の多くのツリー評価器を見てきましたが、それが私の特定の場合にどのように機能するかを確認できませんでした。木。

私がこれまでに書いたコードは、変数名 (a、b、c、d、e など) を見つけるのと同じくらい簡単ですが、正しい値を提供する再帰をコーディングする方法を考え始めることはできません。ハッシュマップ。

public void evaluate(Node node){
    HashMap<String, String> assignments = new HashMap<String, String>();
    NodeList assignment = node.getChildNodes();
    for (int i=0; i < assignment.getLength(); i++){ //1 to 13
        Node assign = assignment.item(i);
        Node variable = this.getChild(assign, 0);
        Node varValNode = this.getChild(variable, 0);
        String varVal = varValNode.getNodeValue();

        Node expression = this.getChild(assign, 1);

私のツリーのドキュメント、ノード、およびノー​​ドリスト クラスは、時間を大幅に節約できると思われる「getChild」メソッドを許可していないという点で珍しいものです。これがなぜなのか誰か知っていますか？

ここで本当にランダムな問題があり、それが理にかなっていることを願っています。ご不明な点がございましたら、お気軽にお問い合わせください。できる限り最善を尽くします。この問題を解決してくれる人を探しているわけではありませんが、この再帰アルゴリズムのコーディング方法を決定する方法を教えてくれるだけです。

編集：また、私が上に置いた2番目の「入力」は実際には出力でした。それはこうあるべきだった：

a := 1;
b := 2;
c := @set(a,b);
d := @set(@tuple(1,2),@tuple(3,4));
4

1 に答える 1

1

すべての値が整数型であると仮定して、HashMap<string,Integer>変数値を格納するためのを作成し、それをevaluateメソッドに渡す必要があります。

public static void main(String[] args) {
    NodeList commandList = ... // get your XML from somewhere
    Map<string,Integer> vars = new HashMap<string,Integer>();
    for (Node node : commandList) {
        evaluate(node, vars);
    }
    // At this point, vars contains values of all variables assigned in commands
    // from the command list
}

評価は比較的簡単になるはずです。

private static Integer evaluate(Node node, Map<string,Integer> vars) {
    if (node is an assignment) {
        String varName = ... // get variable name from node
        Node expr = ... // get the node representing expression being assigned
        Integer value = evaluate(expr, vars);
        vars.put(varName, value);
        return value;
    }
    if (node is a variable reference) {
        String varName = ... // get variable name from node
        return vars.get(varName);
    }
    if (node is an integer constant) {
        String constVal = ... // Get the representation from XML
        return Integer.decode(constVal);
    }
    if (node is a binary expression) {
        Node lhs = ... // Get the left-hand side expression from the node
        Node rhs = ... // Get the right-hand side expression from the node
        Integer lhsVal = evaluate(lhs, vars); 
        Integer rhsVal = evaluate(rhs, vars);
        if (operator is plus) {
            return new Integer(((int)lhsVal) + ((int)rhsVal));
        }
        if (operator is minus) {
            return new Integer(((int)lhsVal) - ((int)rhsVal));
        }
        if (operator is multiply) {
            return new Integer(((int)lhsVal) * ((int)rhsVal));
        }
        if (operator is divide) {
            return new Integer(((int)lhsVal) / ((int)rhsVal));
        }
        // ... and so on
    }
    // ... and so on
}
于 2012-02-09T17:03:06.740 に答える