LeetCode 399: Evaluate Division

Question

I'm posting my C++ code for LeetCode's Evaluate Division. If you have time and would like to review, please do so. Thank you!

Problem

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example: Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Accepted C++

class Solution {
public:
 std::vector<double> calcEquation(std::vector<vector<string>> equations, std::vector<double> values, std::vector<vector<string>> const& queries) {
 generate_graph(equations, values);
 std::vector<double> evaluates;
 for (auto& query : queries) {
 std::set<string> visited;
 double accumulated = 1.0;
 bool evaluate = solve_equation(query[0], query[1], accumulated, visited);
 if (evaluate) {
 evaluates.push_back(accumulated);
 } else {
 evaluates.push_back(-1);
 }
 }
 return evaluates;
 }
protected:
 struct Node {
 Node(std::string const parameter, double const evaluate) {
 this -> parameter = parameter;
 this -> evaluate = evaluate;
 }
 std::string parameter;
 double evaluate;
 };
 map<string, vector<Node>> graph;
 void generate_graph(std::vector<vector<string>>& equations, std::vector<double>& values) {
 for (auto const& equation : equations) {
 vector<Node> children;
 graph[equation[0]] = children;
 }
 for (int equation = 0; equation < equations.size(); equation++) {
 Node node(equations[equation][1], values[equation]);
 graph[equations[equation][0]].push_back(node);
 Node node_reverse(equations[equation][0], 1 / values[equation]);
 graph[equations[equation][1]].push_back(node_reverse);
 }
 }
 bool solve_equation(std::string const nominator, std::string const denominator, double& accumulated, std::set<string>& visited) {
 if (nominator == denominator && graph.find(nominator) != graph.end()) {
 return true;
 }
 if (graph.find(nominator) == graph.end() || graph.find(denominator) == graph.end()) {
 return false;
 }
 visited.insert(nominator);
 for (auto& child : graph[nominator]) {
 if (visited.find(child.parameter) == visited.end()) {
 accumulated *= child.evaluate;
 if (child.parameter == denominator) {
 return true;
 }
 if (solve_equation(child.parameter, denominator, accumulated, visited)) {
 return true;
 } else {
 accumulated /= child.evaluate;
 }
 }
 }
 return false;
 }
};

Reference

On LeetCode, there is an instance usually named Solution with one or more public functions which we are not allowed to rename those.

• Question
• Discussion

• Mikael H: Could you maybe put comments on some places in the code? It's not so obvious why it works, at least to me. Especially the different if-cases in the for-loop in solve_equation.
• Quuxplusone: @Emma: I agree somewhat with Mikael, assuming that the tricky part he's talking about is the rewriting of the problem from "solve these math equations" to "do a depth-first search on a graph." Your implementation of the graph algorithm seems appropriate to me, but it's "not obvious why it works" to solve the original problem about solving a collection of simultaneous equations. (Related: Hypothetically, if you had accidentally omitted the bit about node_reverse, would the bug have been "obvious"?)

Answer 1

Seems basically reasonable. Some English nits: You said "nominator and denominator," when the English terms are "numerator and denominator." You also seem to be using the word "evaluate(s)" as a noun (something like "precipitate" in chemistry), when I think the word you meant was more like "value(s)."

---

struct Node {
 Node(std::string const parameter, double const evaluate) {
 this -> parameter = parameter;
 this -> evaluate = evaluate;
 }
 std::string parameter;
 double evaluate;
};

Write this->x, not this -> x, for the same reason you write st.x and not st . x. But in fact, this constructor would be better written as either

struct Node {
 explicit Node(const std::string& p, double v) : parameter(p), value(v) {}
 std::string parameter;
 double value;
};

or simply

struct Node {
 std::string parameter;
 double value;
};

since simple aggregates can already be initialized with e.g. Node{"a", 2}. Notice that I'm passing std::string by const reference, because it is expensive to copy.

You could actually rewrite all of the helper functions and data structures to use C++17 std::string_view instead of std::string, as long as all the stringviews referred to the original long-lived strings from equations and queries which you are appropriately careful not to modify. This would be an "advanced" idea, though, and probably wouldn't even buy you any speed in this case where all your strings seem to be 1 character long.

---

for (auto& query : queries) — Use for (const auto& query : queries) to indicate that the const-qualification is on purpose; or use auto&& in generic code if you just want something that always works. I don't see any reason to use specifically auto& to get a specifically const-qualified result.

---

 if (visited.find(child.parameter) == visited.end()) {
 accumulated *= child.evaluate;
 if (child.parameter == denominator) {
 return true;
 }
 if (solve_equation(child.parameter, denominator, accumulated, visited)) {
 return true;
 } else {
 accumulated /= child.evaluate;
 }
 }

This if-else ladder is indeed confusing. I would write it like this:

 if (visited.find(child.parameter) != visited.end()) {
 // we have already visited this node; skip it
 } else if (child.parameter == denominator) {
 // we've reached our destination node and resolved the query
 accumulated *= child.value;
 return true;
 } else if (solve_equation(child.parameter, denominator, accumulated, visited)) {
 // this node is on a path that resolves the query
 accumulated *= child.value;
 return true;
 } else {
 // this node is not involved in the solution; do nothing
 }

The most confusing part of the original ladder was

 } else {
 accumulated /= child.evaluate;
 }

That line is really just undoing the multiplication hidden at the top of the loop. But the multiplication is done one scope higher than it is undone, which violates most programmers' intuition. It would have been a simple fix to write

 if (visited.find(child.parameter) == visited.end()) {
 accumulated *= child.evaluate;
 if (child.parameter == denominator) {
 return true;
 }
 if (solve_equation(child.parameter, denominator, accumulated, visited)) {
 return true;
 }
 accumulated /= child.evaluate;
 }

thus visually indicating the symmetry between *= and /=.

---

bool solve_equation(std::string const nominator,
 std::string const denominator, double& accumulated,
 std::set<string>& visited)

Consider whether visited should be a data member of class Solution.

Passing by const value is always a bug; you left off the &. If you used west const style, you could use these git grep lines to find such bugs: https://quuxplusone.github.io/blog/2019/01/03/const-is-a-contract/

Consider whether the return type of this function should be std::pair<bool, double>; or, in C++17, std::optional<double>.

Put it all together and you get a C++14 signature like

std::pair<bool, double> solve_equation(const std::string& numerator,
 const std::string& denominator);

or a C++17 signature like

std::optional<double> solve_equation(std::string_view numerator,
 std::string_view denominator);

---

You have methods named both calcEquation and solve_equation. Admittedly, the name calcEquation is just flat wrong; it should be something like solve_equations (plural). But, given that you aren't allowed to change the public name, personally I would go with calcEquation and calcSingleEquation — reusing the same verb instead of a near-synonym, and emphasizing that this function calculates for a single equation, since I don't have the option of adding an s to pluralize the public name.