# 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:

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.