Simple linear equation solver

Question

In working on a review for Solve a set of "restricted" linear equations efficiently, I decided to reimplement from scratch using the method I proposed in my answer.

The application

I won't repeat the entire specification here, but in a nutshell, this program is intended to solve a very restricted system of linear equations. In particular, each equation is specified to be of the following format:

var = var|value [+ var|value]*

Each var is composed of one or more letters (only) and each value is composed of digits (only) and fit into unsigned int type (note that this differs slightly from the original, which made the assumption of unsigned long but this does not pose a material difference here).

So, the equation y = x + 3 or foo = bar + baz are acceptable, but y = x - 3 ory = x - 7 or bar + baz = foo are not.

The program is to solve all linear equations and report the values for each variable in lexicographic order.

Further, the input is guaranteed to be correctly formatted and not to be cyclic or unsolvable.

My questions

I'm interested in ideas about class design and implementation, but not in error checking of the input (because it's guaranteed to be correctly formatted and not cyclic or unsolvable).

In particular, here are some possible nits:

1. there's not much input error checking (yes, I know; see above)
2. the value of the variable could overflow and wrap
3. the name or value classifier only looks at the first character

Funny business

Originally, I was confused because the compiler I'm using (g++ (gcc) version 6.3.1) reported a peculiar warning that puzzled me, although the program compiles and runs correctly. Specifically, I had to compile the code with the -fpermissive flag, as per the following warning message:

../src/alt.cpp: In function ‘std::set<Variable, std::less<void> > solve(std::istream&)’:
../src/alt.cpp:98:51: warning: passing ‘const Variable’ as ‘this’ argument discards qualifiers [-fpermissive]
             unsolved |= eq.replaceKnowns(equations);
                                                   ^
../src/alt.cpp:63:10: note:   in call to ‘bool Variable::replaceKnowns(std::set<Variable, std::less<void> >&)’
     bool replaceKnowns(std::set<Variable, std::less<>> &equations) {
          ^~~~~~~~~~~~~

The reason is that all iterators for std::set are const, (hat tip to @Incomputable) so to accomodate, I've made the dependencies and value member data items mutable and made the replaceKnowns function const. So the question now is: clever move or horrible hack?

The code

#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <cctype>
#include <functional>

class Variable {
public:
    friend std::ostream &operator<<(std::ostream &out, const Variable &var) {
        out << var.name << " = ";
        for (const auto &vname: var.dependencies) {
            out << vname << " + ";
        }
        return out << var.value;
    }
    friend std::istream &operator>>(std::istream &in, Variable &var) {
        Variable v{};
        std::swap(var, v);
        std::string line;
        if (std::getline(in, line)) {
            std::stringstream buff{line};
            std::string token;
            enum states {varname, equals, depOrConst, plus, error} state = varname;
            while (buff >> token) {
                switch (state) {
                    case varname:
                        var.name = token;
                        state = equals;
                        break;
                    case equals:
                        state = (token == "=") ? depOrConst : error;
                        break;
                    case depOrConst:
                        if (std::isalpha(token[0])) {
                            var.dependencies.push_back(token);
                            state = plus;
                        } else if (std::isdigit(token[0])) {
                            var.value += std::stoul(token);
                            state = plus;
                        } else {
                            state = error;
                        }
                        break;
                    case plus:
                        state = (token == "+") ? depOrConst : error;
                        break;
                    default:  // error
                        in.setstate(std::ios::failbit);
                        return in;
                }
            }
        }
        return in;
    }
    bool operator<(const Variable &other) const {
        return name < other.name;
    }
    bool unsolved() const { 
        return !dependencies.empty();
    }
    bool replaceKnowns(std::set<Variable, std::less<>> &equations) const {
        std::vector<std::string> unresolved;
        for (auto dep = dependencies.begin(); dep != dependencies.end(); ++dep) {
            auto m = equations.find(*dep);
            if (m != equations.end() && !m->unsolved()) {
                value += m->value;
            } else {
                unresolved.push_back(*dep);
            }
        }
        std::swap(unresolved, dependencies);
        return unsolved();
    }
    const std::string getName() const { return name; }
private:
    std::string name{};
    mutable unsigned value = 0;
    mutable std::vector<std::string> dependencies{};
};

bool operator<(const Variable &v, const std::string &s) {
    return v.getName() < s;
}

bool operator<(const std::string &s, const Variable &v) {
    return v.getName() < s;
}

std::set<Variable, std::less<>> solve(std::istream &in) {
    std::set<Variable, std::less<>> equations;
    bool unsolved = false;
    for (Variable var; in >> var; ) {
        unsolved |= var.unsolved();
        equations.insert(var);
    }
    while (unsolved) {
        unsolved = false;
        for (auto &eq: equations) {
            unsolved |= eq.replaceKnowns(equations);
        }
    }
    return equations;
}

int main() {
    std::stringstream in{"b = c + d + 3\nd = e + 4\na = b + c + d + 1\ne = 7\nc = d + 2"};
    auto solution_list = solve(in);
    for (const auto& s: solution_list) {
        std::cout << s << "\n";
    }
}

Sample input and output

The main function tests the following system of equations:

b = c + d + 3
d = e + 4
a = b + c + d + 1
e = 7
c = d + 2

This results in the following correct output:

a = 52
b = 27
c = 13
d = 11
e = 7

Answer 1

I see three abstractions in the problem.

1. Variable
2. Expression
3. Equation

I see two main functions.

1. Parse an input string to construct a set of equations.
2. Solve a set of equations to come up with a set of variables with the solved values.

Separating the data involved in the program to three distinct abstractions makes it easier to understand the code. It allows the program to be divided into smaller chunks that are easier to understand.

From a functionality point of view, it is better to divide the functionality into two main functions. One can independently implement them and check them for accuracy.

Construction of the set of equations is separate from solving them. One can implement the code to parse the set of equations without solving them. The parsing code can be verified for accuracy before passing the parsed data to the solving function.

Solving the set of equations is independent of the method to construct them. The function to solve a set of equations can be implemented and tested with a set of hard coded equations.

Once both functions are independently tested and verified for accuracy, they can be combined very easily.

Here's my implementation that captures those notions.

#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <cctype>
#include <functional>

namespace Impl2
{
   // A Variable has a name and a value.
   // The name is constrained to a single character.
   struct Variable
   {
      Variable() : name(0), value(0) {}
      Variable(char n) : name(n), value(0) {}
      char name;
      mutable unsigned value;

      bool operator<(Variable const& rhs) const
      {
         return (name < rhs.name);
      }
   };

   std::ostream& operator<<(std::ostream& out, Variable const& var)
   {
      return (out << var.name << " = " << var.value);
   }

   // An Expression is what appears on the RHS of an Equation.
   // A set of variables and a constant. The value of an
   // Expression is the sum of the values of its variables and
   // the constant.
   struct Expression
   {
      Expression() : cons(0) {}
      std::set<Variable> vars;
      unsigned cons;
   };

   std::istream& operator>>(std::istream& in, Expression& expr)
   {
      char ch;
      int val = 0;
      while ( in >> ch )
      {
         if (isalpha(ch) )
         {
            expr.vars.insert(Variable(ch));
            expr.cons += val;
            val = 0;
         }
         else if ( isdigit(ch) )
         {
            val = val*10 + (ch-'0');
         }
         else 
         {
            // ch is '+';
         }
      }
      expr.cons += val;

      return in;
   }

   std::ostream& operator<<(std::ostream& out, Expression const& expr)
   {
      for ( auto const& var: expr.vars )
      {
         out << var.name << " + ";
      }
      out << expr.cons;
      return out;
   }

   // An Equation contains a variable and an Expression.
   // Needed to make Expression mutable to allow modification
   // of Equations during the process of solving a set of 
   // Equations.
   struct Equation
   {
      Variable var;
      mutable Expression expression;
      bool operator<(Equation const& rhs) const
      {
         return (var < rhs.var);
      }
   };

   std::istream& operator>>(std::istream& in, Equation& eq)
   {
      char ch;

      // Get the name of the variable.
      in >> eq.var.name;
      if (!in)
      {
         return in;
      }

      // Get the = token.
      in >> ch;
      if (!in)
      {
         return in;
      }

      if ( ch != '=')
      {
         // Error.
      }

      // Parse rest of Equation, which is an Expression.
      return ( in >> eq.expression);
   }

   std::ostream& operator<<(std::ostream& out, Equation const& eq)
   {
      return (out << eq.var.name << " = " << eq.expression);
   }

   // Parse an input stream to construct a set of
   // Equations.
   std::set<Equation> parse(std::stringstream& in)
   {
      std::set<Equation> equations;
      std::string line;
      while (std::getline(in, line)) {
         std::stringstream buff{line};
         Equation eq;
         buff >> eq;
         equations.insert(eq);
      }

      return equations;
   }

   // Solve a set of Equations and return a set of Variables
   // that contain the solved values.
   std::set<Variable> solve(std::set<Equation> equations)
   {
      std::set<Variable> variables;
      while ( !equations.empty() )
      {
         Variable var;

         for ( Equation const& eq: equations )
         {
            if ( eq.expression.vars.empty() )
            {
               eq.var.value = eq.expression.cons;
               var = eq.var;
               equations.erase(eq);
               break;
            }
         }

         for ( Equation const& eq: equations )
         {
            if ( eq.expression.vars.find(var) != eq.expression.vars.end() )
            {
               eq.expression.cons += var.value;
               eq.expression.vars.erase(var);
            }
         }

         variables.insert(var);
      }

      return variables;
   }

   void test(std::string const& equationsStr)
   {
      std::stringstream in{equationsStr};
      std::set<Equation> equations = parse(in);
      std::cout << "Equations:\n";
      for (const auto& eq: equations) {
         std::cout << eq << "\n";
      }
      std::cout << "\n";

      std::cout << "Solution:\n";
      std::set<Variable> variables = solve(equations);
      for (const auto& var: variables) {
         std::cout << var << "\n";
      }
   }
}

int main()
{
   std::string in{"b = c + d + 3\nd = e + 4\na = b + c + d + 1\ne = 7\nc = d + 2"};
   Impl2::test(in);
}

Output of the program:

Equations:
a = b + c + d + 1
b = c + d + 3
c = d + 2
d = e + 4
e = 7

Solution:
a = 52
b = 27
c = 13
d = 11
e = 7

Update, make the name of Variable a string

It turns out the name of a Variable can be a string consisting of characters for which isalpha(c) is true.

Changes needed for that:

Change Variable to

struct Variable
{
   Variable() : name(), value(0) {}
   Variable(std::string const& n) : name(n), value(0) {}
   std::string name;
   mutable unsigned value;

   bool operator<(Variable const& rhs) const
   {
      return (name < rhs.name);
   }
};

Change operator<<(std::istream&, Expression&) to

std::istream& operator>>(std::istream& in, Expression& expr)
{
   char ch;
   int val = 0;
   std::string varName = "";
   while ( in >> ch )
   {
      if (isalpha(ch) )
      {
         varName += ch;
         expr.cons += val;
         val = 0;
      }
      else
      {
         if ( !varName.empty() )
         {
            expr.vars.insert(Variable(varName));
            varName = "";
         }

         if ( isdigit(ch) )
         {
           val = val*10 + (ch-'0');
         }
         else 
         {
            // ch is '+';
         }
      }
   }
   expr.cons += val;

   return in;
}