HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Simple linear equation solver

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewc++14rags-to-richescppstackoverflowc++algorithm
solverlinearsimpleequation

Problem

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:

  • there's not much input error checking (yes, I know; see above)



  • the value of the variable could overflow and wrap



  • 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 > solve(std::istream&)’:
../src/alt.cpp:98:51: warning: passing ‘const Variable’ as ‘this’ argument discards qualifiers [-fpermissive]
unsolved |= eq.replaceKnowns(

Solution

I see three abstractions in the problem.

  • Variable



  • Expression



  • Equation



I see two main functions.

  • Parse an input string to construct a set of equations.



  • 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 
#include 
#include 
#include 
#include 
#include 
#include 

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 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::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 parse(std::stringstream& in)
   {
      std::set 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 solve(std::set equations)
   {
      std::set 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 equations = parse(in);
      std::cout  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;
exp

Code Snippets

#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 equation
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);
   }
};
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;
}

Context

StackExchange Code Review Q#158752, answer score: 3

Revisions (0)

No revisions yet.