10

The Algorithm Design Manualには、関連する 2 つの節があります。

基本的に、最初の消費税の解き方は知っていますが、最初の消費税の解法をヒントに、2番目の消費税の解き方がわかりません。

算術式木の抜粋

算術式ツリー

上は算術式ツリーです。算術式が木として与えられたとします。各リーフは整数で、各内部ノードは標準の算術演算 (+、−、∗、/) の 1 つです。たとえば、式 2 + 3 ∗ 4 + (3 ∗ 4)/5 は、上の図のツリーで表されます。このような式を評価するための O(n) アルゴリズムを与えてください。ここで、ツリーには n 個のノードがあります。

わかりました、これは難しいことではありません。私の解決策は次のとおりです。

    public float evaluate() {
        return evaluate(root);
    }

    private float evaluate(Node_EX _node) {
        if (_node.left == null || _node.right == null)
            return Float.parseFloat(_node.key);
        String op = _node.key;
        if (op == "+") {
            return evaluate(_node.left) + evaluate(_node.right);
        } else if (op == "-") {
            return evaluate(_node.left) - evaluate(_node.right);
        } else if (op == "*") {
            return evaluate(_node.left) * evaluate(_node.right);
        } else {
            return evaluate(_node.left) / evaluate(_node.right);
        }
    }

結果の式ツリーを解決するために再帰的な方法を使用するだけです。

演算式DAGの抜粋

算術式ダグ

算術式が、共通部分式が削除された DAG (有向非巡回グラフ) として与えられているとします。各リーフは整数で、各内部ノードは標準の算術演算 (+、−、∗、/) の 1 つです。たとえば、式 2 + 3 ∗ 4 + (3 ∗ 4)/5 は、上の図の DAG で表されます。このような DAG を評価するための O(n + m) アルゴリズムを与えます。ここで、DAG には n 個のノードと m 個のエッジがあります。ヒント: 望ましい効率を達成するために、ツリー ケースのアルゴリズムを変更します。

OK、説明に次のようなヒントがあります:ヒント: ツリー ケースのアルゴリズムを変更して、目的の効率を達成します。

実際、私はこのヒントにかなり混乱しています。典型的なツリー関連の場合、通常、再帰を使用して解決できます。ただし、これがグラフの場合、私の最初の直感は、BFS または DFS を使用して解決することです。DFS は実際には再帰的ですが、どうすれば BFS や DFS をツリーに関連付けることができますか?

4

2 に答える 2

13

望ましい効率を達成するために、問題は、既に訪れたツリーの部分を再評価することを避けることを望んでいると私は信じています。DAG 内の一部のサブツリーに到達して評価したら (ツリー内のすべてのノードは、そのノードをルートとするサブツリーを表します)、結果の値を保存して、そのサブツリーに関連付けることができます。次に、再度アクセスすると、その値を事前に計算したかどうかを確認し、再度評価するのではなく、値を取得することができます。

これらの値を格納および取得するにはさまざまな方法があります。単純な方法は、ノードの構造を変更してキャッシュ可能な結果を​​可能にすることです。

于 2012-04-12T10:24:41.943 に答える