如何重新排列字符串方程？

我从语法图开始定义（我不会称之为）一种语言：

然后我把它翻译成一个手写的解析器。

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 '\0': 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;
}

g++在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

$

Coliru 上的生活演示

笔记：

1. 取而代之的parseDigit()和parseNumber()，std::strtol()都可以使用。这将显着减少代码。

2. 我用于const char*“读头” la（...缩写为“向前看”）。纯 C++ 方式可能是一个std::stringstream或一个，std::string::iterator但是，可能是，我对这些新奇的东西还不够习惯。对我来说，这const char*是最直观的方式......

3. 右手边的结果只是从 x ⁰的系数中减去。因此，要么右侧为 0，要么 x ⁰的负系数变为右侧。对于我的漂亮打印operator<<()，我选择了后一个选项。

4. 错误处理相当差，可以通过有关解析失败原因的更详细信息来增强。我忽略了这一点，以免更多地“炸毁”代码。

5. 解析器可以轻松增强以跳过任何适当位置的空白。这将提高便利性。

6. 在当前状态下，右侧的结果可能不是负数。我把这个扩展留作练习。