如何重新排列字符串方程式？ [英] How to rearrange a string equation?
问题描述
我需要开发一个程序来求解线性方程。程序
首先读取一个整数 n ，它是等式的数量。
然后程序读取包含等式的 n 行。
例如，程序的输入如下：
3
2x1 + 3x2 + 4x3 = 16
1x1 + 2x2 + 1x3 = 8
3x1 + 1x2 + 2x3 = 13
任何运算都应首先将每个方程式转换为正确形式的
。适当的方程式应具有以下属性
-
变量从左到右按字母顺序排列：
3x2 + 2x1 + 4x3 = 16
应该是
2x1 + 3x2 + 4x3 = 16
-
任何变量应仅出现一次：
4x1 + 3x2-2x1 + 4x3 = 16
应该
2x1 + 3x2 + 4x3 = 16
-
方程中应只出现一个常数项，并且右边应为
：2x1 + 3x2 + 5 + 4x3-11 = 10
应该
2x1 + 3x2 + 4x3 = 16
-
系数等于1或-1时，数字1是可选的：
1x1 + 3x2-1x3 = 10
可以直接输入
x1 + 3x2-x3 = 10
到目前为止，我所做的事情如下：
＃include< iostream>
＃include< string>
＃include< sstream>
＃include< cstdlib>
使用命名空间std;
int main（）{
int n;
cin>> n;
字符串eqn [100];
//从用户
获得等式（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;
字符串j = ss.str（）;
for（int t = 0; t
if（y
for（int o = 1; o< = counter; o ++）{
s = eqn [i] .find（ x + j，s + 1）;
字符串x1 = eqn [i] .substr（s-1，3）;
字符串x2 = x2 + x1;
cout<< x1;
}
}
cout<<恩德尔
}
int k; cin>> k;
返回0;
}
但是事情变得复杂了，我不确定这是否正确
除了 find（）， substr（）？
我应该如何解决这个问题？
我从
然后我将其翻译为手写解析器。
parse-equation.cc ：
#include< iostream>
#include< algorithm>
int parseDigit（const char *& la）
{
switch（* la）{
case'0'：++ la;返回0;
案例 1：++ la;返回1;
case‘2’：++ la;返回2;
案例 3：++ la;返回3;
案例‘4’：++ la;返回4;
案例 5：++ la;返回5;
案例 6：++ la;返回6;
案例 7：++ la;返回7;
案例 8：++ la;返回8;
案例 9：++ la;返回9;
默认值：返回-1; //错误！
}
}
int parseNumber（const char *&la）
{
int value = parseDigit（la）;
如果（值<0）返回-1; //错误！
for（;;）{
const int digit = parseDigit（la）;
如果（数字< 0）返回值;
值* = 10;值+ =数字;
}
}
struct Term {
int coeff; // -1 ...缺少
int指数； // -1 ...失踪->错误
Term（int coeff = -1，int expon = 0）：coeff（coeff），expon（expon）{}
};
期限parseTerm（const char *&la）
{
期限；
term.coeff = parseNumber（la）;
if（* la =='x'）{
++ la;
term.expon = parseDigit（la）;
如果（term.coeff <0）term.coeff = 1; //容忍丢失的系数。对于x
}
返回期限；
}
结构表达式{
bool error;
int coeffs [10]；
Expression（布尔错误= false）：错误（错误）
{
std :: fill（std :: begin（coeffs），std :: end（coeffs）， 0）;
}
};
表达式parseExpression（const char *& la）
{
Expression expr;
int符号= +1；
do {
const term term = parseTerm（la）;
if（term.expon< 0）返回Expression（true）; //错误！
expr.coeffs [term.expon] + =符号* term.coeff;
开关（* la）{
情况‘+’：sign = +1; ++ la;打破;
情况‘-’：符号= -1； ++ la;打破;
case’=’：休息；
默认值：return Expression（true）; //错误！
}
}而（* la！=’=’）;
++ la;
//解析右侧
const int result = parseNumber（la）;
if（结果<0）返回Expression（true）; //错误！
expr.coeffs [0]-=结果；
//检查是否有多余的字符
开关（* la）{
case'\n'：++ la;
案例 \0：休息；
默认值：return Expression（true）; //错误！
}
return expr;
}
std :: ostream&运算符<（（std :: ostream& out，const Expression& expr）
{
if（expr.error）out<< 错误！;
else {
bool empty = true;
for（size_t i = 9; i; --i）{
const int coeff = expr.coeffs [i];
（如果（coeff）out<< coeff<< ‘x’<<我<< std :: showpos，empty = false;
}
如果（空）出<< 0;
out<< std :: noshowpos<< ’=’<< -expr.coeffs [0];
}
返回；
}
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
};
枚举{nSamples = sizeof样本/ sizeof * samples};
for（size_t i = 0; i< nSamples; ++ i）{
std :: cout<< 解析’<<样本[i]< ’\n;
const char * la = samples [i];
std :: cout<< 得到<< parseExpression（la）<< std :: endl;
}
返回0；
}
使用 g ++ 进行编译并在 cygwin 中进行了测试：
$ g ++ -std = c ++ 11 -o parse-equation parse-equation.cc
$ ./parse -equation
解析'2x1 + 3x2 + 4x3 = 16'
得到4x3 + 3x2 + 2x1 = 16
解析'1x1 + 2x2 + 1x3 = 8'
得到1x3 + 2x2 + 1x1 = 8
解析'3x1 + 1x2 + 2x3 = 13'
得到2x3 + 1x2 + 3x1 = 13
解析'2x1 + 3x2 + 5 + 4x3-11 = 10'
得到4x3 + 3x2 + 2x1 = 16
解析'x1 + 3x2-x3 = 10'
得到-1x3 + 3x2 + 1x1 = 10
注意：
-
代替
parseDigit（）和parseNumber（），std ::可以使用strtol（）。这将大大减少代码。 -
我将
const char *用作读取头la（...缩写为向前看）。纯C ++方式可能是std :: stringstream或std :: string :: iterator但是，也许我对这些新奇的东西还不够习惯。对我来说，const char *是最直观的方式... -
右边的结果简单地从x 0 的系数中减去手侧。因此，要么右侧为0，要么x 0 的负系数变为右侧。对于我漂亮的
operator<<（（）），我选择了后者。 -
错误处理能力很差，可以通过提供有关解析失败原因的更多详细信息来增强错误处理能力。我忽略了这一点，不要再吹牛代码了。
-
可以轻松地增强解析器，以在任何适当的位置跳过空格。
-
在当前状态下，右侧结果可能不是负数。我将此扩展保留为练习。
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
Variables are ordered alphabetically from left to right:
3x2+2x1+4x3=16Should be
2x1+3x2+4x3=16Any variable should appear only once:
4x1+3x2-2x1+4x3=16Should be
2x1+3x2+4x3=16Only one constant term should appear in the equation and it should be on the right hand side:
2x1+3x2+5+4x3-11=10Should be
2x1+3x2+4x3=16Coefficient when equals to one or -1 the digit 1 is optional:
1x1+3x2-1x3=10Can 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?
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 '\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;
}
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
$
Note:
Instead of
parseDigit()andparseNumber(),std::strtol()could be used. This would reduce the code significantly.I used
const char*for the "read head"la(... abbr. for "look ahead"). The pure C++ way might have been astd::stringstreamor astd::string::iteratorbut, may be, I'm not used enough to these new fancy things. For me, theconst char*was the most intuitive way...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.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.
The parser could be enhanced easily to skip white space at any appropriate place. This would improve the convenience.
In the current state, the result on right hand side might not be a negative number. I leave this extension as exercise.
这篇关于如何重新排列字符串方程式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
