c++ – How to rearrange a string equation?

c++ – How to rearrange a string equation?

I started with a Syntax Diagram to define (I wouldnt call it) a language:

Syntax

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 n: ++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] << n;
    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, Im 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 x0. So, either the right hand side is 0, or the negative coefficient for x0 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.

c++ – How to rearrange a string equation?

Leave a Reply

Your email address will not be published. Required fields are marked *