c++ - How to rearrange a string equation?

Question

I am required to develop a program to solve linear equations. The programs reads first an integer n which is the number of equations. Then the program reads n lines containing the equations. For example, the input to the program is like:

3
2x1+3x2+4x3=16
1x1+2x2+1x3=8
3x1+1x2+2x3=13

Any operation should first convert every equation to the proper form. The equation proper should have the following properties

1. Variables are ordered alphabetically from left to right:

   3x2+2x1+4x3=16
   

   Should be

   2x1+3x2+4x3=16
   

2. Any variable should appear only once:

   4x1+3x2-2x1+4x3=16
   

   Should be

   2x1+3x2+4x3=16
   

3. Only one constant term should appear in the equation and it should be on the right hand side:

   2x1+3x2+5+4x3-11=10
   

   Should be

   2x1+3x2+4x3=16
   

4. Coefficient when equals to one or -1 the digit 1 is optional:

   1x1+3x2-1x3=10
   

   Can be input as be

   x1+3x2-x3=10
   

What I have done so far is as follows:

#include<iostream>
#include<string>
#include<sstream>
#include<cstdlib>

using namespace std;

int main() {
    int n;
    cin >> n;
    string eqn[100];
    //get eq from user
    for (int i = 0; i < n; i++) {
        cin >> eqn[i];
    }

    size_t  s = 0;
    size_t  y = 0;
    for (int i = 0; i < n; i++) {
        for (int x = 1; x <= ((eqn[i].length() - ((eqn[i].length() - 3) / 4)) / 3); x++)
        {
            int counter = 0;
            ostringstream ss;
            ss << x;
            string j = ss.str();
            for (int t = 0; t < eqn[i].length(); t++) {
                y = eqn[t].find("x" + j, y + 1);
                if (y < eqn[i].length()) { counter++; }
            }
            for (int o = 1; o <= counter; o++) {
                s = eqn[i].find("x" + j, s + 1);
                string x1 = eqn[i].substr(s - 1, 3);
                string x2 = x2 + x1;
                cout << x1;


            }


        }
        cout << endl;
    }
    int k;  cin >> k;

    return 0;
}

but things became over complicated, and I am not sure if that is the right approach..

Is there a better way to operate on a string equation other than find(), substr()? How should I approach the problem?

Answer 1

I started with a Syntax Diagram to define (I wouldn't call it) a language:

Then I translated this into a hand-written parser.

parse-equation.cc:

#include <iostream>
#include <algorithm>

int parseDigit(const char *&la)
{
  switch (*la) {
    case '0': ++la; return 0;
    case '1': ++la; return 1;
    case '2': ++la; return 2;
    case '3': ++la; return 3;
    case '4': ++la; return 4;
    case '5': ++la; return 5;
    case '6': ++la; return 6;
    case '7': ++la; return 7;
    case '8': ++la; return 8;
    case '9': ++la; return 9;
    default: return -1; // ERROR!
  }
}

int parseNumber(const char *&la)
{
  int value = parseDigit(la);
  if (value < 0) return -1; // ERROR!
  for (;;) {
    const int digit = parseDigit(la);
    if (digit < 0) return value;
    value *= 10; value += digit;
  }
}

struct Term {
  int coeff; // -1 ... missing
  int expon; // -1 ... missing -> ERROR

  Term(int coeff = -1, int expon = 0): coeff(coeff), expon(expon) { }
};

Term parseTerm(const char *&la)
{
  Term term;
  term.coeff = parseNumber(la);
  if (*la == 'x') {
    ++la;
    term.expon = parseDigit(la);
    if (term.coeff < 0) term.coeff = 1; // tolerate missing coeff. for x
  }
  return term;
}

struct Expression {
  bool error;
  int coeffs[10];

  Expression(bool error = false): error(error)
  {
    std::fill(std::begin(coeffs), std::end(coeffs), 0);
  }
};

Expression parseExpression(const char *&la)
{
  Expression expr;
  int sign = +1;
  do {
    const Term term = parseTerm(la);
    if (term.expon < 0) return Expression(true); // ERROR!
    expr.coeffs[term.expon] += sign * term.coeff;
    switch (*la) {
      case '+': sign = +1; ++la; break;
      case '-': sign = -1; ++la; break;
      case '=': break;
      default: return Expression(true); // ERROR!
    }
  } while (*la != '=');
  ++la;
  // parse right hand side
  const int result = parseNumber(la);
  if (result < 0) return Expression(true); // ERROR!
  expr.coeffs[0] -= result;
  // check for extra chars
  switch (*la) {
    case '
': ++la;
    case '': break;
    default: return Expression(true); // ERROR!
  }
  return expr;
}

std::ostream& operator<<(std::ostream &out, const Expression &expr)
{
  if (expr.error) out << "ERROR!";
  else {
    bool empty = true;
    for (size_t i = 9; i; --i) {
      const int coeff = expr.coeffs[i];
      if (coeff) out << coeff << 'x' << i << std::showpos, empty = false;
    }
    if (empty) out << 0;
    out << std::noshowpos << '=' << -expr.coeffs[0];
  }
  return out;
}

int main()
{
  const char *samples[] = {
    "2x1+3x2+4x3=16",
    "1x1+2x2+1x3=8",
    "3x1+1x2+2x3=13",
    "2x1+3x2+5+4x3-11=10",
    "x1+3x2-x3=10"
  };
  enum { nSamples = sizeof samples / sizeof *samples };
  for (size_t i = 0; i < nSamples; ++i) {
    std::cout << "Parse '" << samples[i] << "'
";
    const char *la = samples[i];
    std::cout << "Got    " << parseExpression(la) << std::endl;
  }
  return 0;
}

Compiled with g++ and tested in cygwin:

$ g++ -std=c++11 -o parse-equation parse-equation.cc 

$ ./parse-equation
Parse '2x1+3x2+4x3=16'
Got    4x3+3x2+2x1=16
Parse '1x1+2x2+1x3=8'
Got    1x3+2x2+1x1=8
Parse '3x1+1x2+2x3=13'
Got    2x3+1x2+3x1=13
Parse '2x1+3x2+5+4x3-11=10'
Got    4x3+3x2+2x1=16
Parse 'x1+3x2-x3=10'
Got    -1x3+3x2+1x1=10

$

Life Demo on Coliru

Note:

1. Instead of parseDigit() and parseNumber(), std::strtol() could be used. This would reduce the code significantly.

2. I used const char* for the "read head" la (... abbr. for "look ahead"). The pure C++ way might have been a std::stringstream or a std::string::iterator but, may be, I'm not used enough to these new fancy things. For me, the const char* was the most intuitive way...

3. The result on right hand side is simply subtracted from the coefficient for x⁰. So, either the right hand side is 0, or the negative coefficient for x⁰ becomes right hand side. For my pretty-printing operator<<(), I chose the latter option.

4. The error handling is rather poor and could be enhanced with more detailed infos about the reason of failed parsing. I left this out to not to "blow" the code even more.

5. The parser could be enhanced easily to skip white space at any appropriate place. This would improve the convenience.

6. In the current state, the result on right hand side might not be a negative number. I leave this extension as exercise.