В Руководстве по разработке алгоритмов есть два связанных акциза.
В принципе, я знаю, как решить первый акциз, но я не знаю, как решить второй, используя решение первого в качестве подсказки.
Удаление арифметического выражения дерево
Выше показано дерево арифметических выражений. Предположим, что арифметическое выражение дано в виде дерева. Каждый лист является целым числом, а каждый внутренний узел представляет собой одну из стандартных арифметических операций (+, -, ∗, /). Например, выражение 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 (направленный ациклический граф) с удаленными общими подвыражениями. Каждый лист является целым числом, а каждый внутренний узел представляет собой одну из стандартных арифметических операций (+, -, ∗, /). Например, выражение 2 + 3 ∗ 4 + (3 ∗ 4) / 5 представлено DAG на рисунке выше. Приведите алгоритм O (n + m) для оценки такого DAG, где есть n узлов и m ребер в DAG. Подсказка: измените алгоритм для случая дерева, чтобы добиться желаемой эффективности.
Хорошо, в описании есть такая подсказка: Подсказка: измените алгоритм для случая дерева, чтобы достичь желаемой эффективности.
На самом деле, этот намек меня очень сбил с толку. Для типичных вещей, связанных с деревом, мы обычно можем использовать рекурсивное решение. Однако, если это график, первым делом я должен использовать BFS или DFS для его решения. Тогда как я могу связать BFS или DFS с деревом, хотя DFS на самом деле является рекурсивным?
