完整的模拟计算思路
查看原帖
完整的模拟计算思路
477036
ParseY_Pasy楼主2021/10/16 19:22

如果不想听我那长篇大论的解释,就直接看这段代码吧(

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//long long的简写
ll strtoi(string i){
    ll o=0;
    for(auto&&a:i){
        if(isdigit(a))
            o=o*10+(a-'0');
    }
    o*=(i[0]=='-'?-1:1);
    return o;
}
bool containnum(string a){
    for(auto&&c:a){
        if(isdigit(c))
            return 1;
    }
    return 0;
}
int main(){
    string c;
    getline(cin,c);
    ll coefficient=0,constant=0;
    char sign;
    int nega = 1;
    for(int i = 0,len = c.length();i<len;i++){
        string num;
        if(c[i] == '='){
            nega = -1;
            continue;
        }
        if(c[i]!='+'&&c[i]!='-'&&c[i]!='='){
            ll sign_start = i;
            while(c[i]!='+'&&c[i]!='-'&&c[i]!='='&&i<len){
                if(c[i] == '=')
                    nega = -1;
                num+=c[i++];
            }
            i--;
            if(i>0)
                num = (c[sign_start-1]!='='?c[sign_start-1]:' ') + num;
            if(isalpha(num[num.length()-1])){
                if(containnum(num))
                    coefficient += nega*strtoi(num);//找到系数
                else
                    coefficient += num[0]=='-'?nega*-1:nega*1;
                sign = num[num.length()-1];
            }
            else
                constant+=nega*strtoi(num);//否则算作常数
        }
    }
    if(coefficient!=0 && constant==0)
        cout << sign<<"=0.000" <<endl;
    else if(coefficient!=0 && constant!=0)
        printf("%c=%.3lf",sign,(-1.0*constant/coefficient));
    return 0;
}

好的相信你已经看好了全部代码,让我们开始逐段分析

首先看题:

在计算器上键入的一个一元一次方程中,只包含整数、小写字母及+、-、=这三个数学符号(当然,符号“-”既可作减号,也可作负号)。

方程中并没有括号,也没有除号,方程中的字母表示未知数。

你可假设对键入的方程的正确性的判断是由另一个程序员在做,或者说可认为键入的一元一次方程均为合法的,且有唯一实数解。

输入格式

一个一元一次方程。

输出格式

解方程的结果(精确至小数点后三位)。

我们应当庆幸这题没有恶心到加上乘除和括号(

首先对于一般的一元一次方程:

ax + b = 0

其解析解为:

 x= -\frac{b}{a} 

那么解这个方程的关键就在于求出ab

对于一个比较复杂的方程,我们可以按照如下方式进行求系数和常数:

设系数为 coefficient

常数为 constant

比如:

114514a+1919=1919a-114514

我们同样可以庆幸没有空格(

那么,首先我们得分离出各个项。

分离项的算法很简单,O(N)搞定。(可以通过空格分词算法修改得到)

对于一个字符串num,我们将其作为一个项的存储。 而a则作为输入的方程。 代码如下:

string num,a;//定义
getline(cin,a);//这就是输出
for(int i = 0;i<num.length();i++){
    if(a[i] != '+' && a[i] != '-' && a[i] != '='){
        ...
    }//这里就是对于当前字符的判断
}

对于分割,我们首先需要确定开头。 开头的目标是最靠前的非分隔符字符。 这里的分隔符就是+,-,= 那么只要顺序检索,第一个非分隔符字符就是最靠前的。 接下来找到了开头,就可以读入num了。 对于读入num,用循环。 循环的表达式如下: while(a[i] != '+' && a[i] != '-' && a[i] != '=' && i < num.length()){ ... } 注意这里依旧要检索当前字符是否为分隔符,而最后的下标限定是为了防止末尾非分隔符而持续读入造成内存错乱的情况。 那么对于内部就很简单了,num+=a[i++]; a[i++]在读入num的时候会同时增加i的值,这样就省去了写一个i++;(顺带压行

相信各位都知道如何得到一个标准的方程项了。 通过这样,在循环中我们依次能得到这些内容:

114514a
1919
1919a
114514

接下来就是求值。

首先来看第一个项,这里面包含一个114514和a

注意未知数是小写字母,那么我们通过内置方法isalpha很容易就可以得出未知数是哪个字符。

我们用sign存储未知数,以便后续输出答案。

因为未知数是单个字符且一定在末尾,直接找末位字符就行。

string num = "114514a";
bool has_sign = isalpha(num[num.length()-1]);//是否拥有字母(未知数)

则检索到末位字符为字母(has_sign == true)后,

char sign = num[num.length()-1];

接下来求系数。

我们不能直接将这个字符串进行计算放到最终结果里,但我相信各位都会自己写一个字符串转数字的函数。

我的这个版本可以过滤非数字字符,且长度尽可能压缩,如下:

long long strtoi(string i){
    long long o=0;
    for(auto&&a:i){
		if(isdigit(a))
			o=o*10+(a-'0');
	}
    if(i[0]=='-')
    	o*=-1;
    return o;
}

解释一下,首先定义o作为输出

然后是C++11的新特性:范围循环。

如果你学过Python,那你只要把其理解为

for a in i:
   ...

就行了。

范围循环很简洁,适用于STL中有范围的容器,string刚好满足。

有人会问为什么之前不用?

因为你必须存当前下标,还不如经典for。

然后isdigit就是判断一个字符是否为数字,系统函数直接用。

o = o*10 + (a-'0');

我们已经确认了a是数字,那么根据大家应该初阶就学过的ASCII码加减,我们就可以通过字符的加减求其数字。

题外话:ANSI标准规定任何编译器中字符0-9的ASCII值必须连续,所以不用考虑兼容性。

o*10

就是为这个新的数字腾出一个位。最后就是:

return 0;

那最后一个if呢?

负号我们默认在开头,所以检查一下开头是不是负号就好了,如果是则结果符号取反。 这样就是稳定的字符串转整型数字。

好的,那我们现在就可以求出系数了吗?

不行。

看向原方程,第四项

-114514

被存储为

114514

如何解决这个问题? 很简单,将num与该字符串的前一个符号合并

自然在开始循环读字符串的时候,我们在检索到一个单词就存一个其开始下标,称为sign_start,放在while前,存储当前的i 那么:

num = a[sign_start-1]+num;

字符串加减各位应该都会,不讲了。

由于strtoi会过滤所有除负号外的字符,所以不用担心前面是加号或等于号的情况,以及后面可能的未知数。 接下来,放心的用strtoi,我们就求出了这个项的系数。

系数求完了,我们就得看看放在系数部分还是常数部分里。

检查项的最后一个字符,如果是未知数sign,则coefficient加上strtoi(num)

但如果过了等号怎么办?

此时需要把系数给搬过来,系数得取反。

那就写个检索器:

if(a[i] == '=')
    //标明已经过等号了

我们需要对等号后的系数乘-1,那么加上个整数nega,初值为1,过了等号为-1,加在最终结果上,如下:

coefficient+=nega*strtoi(num);
constant += nega*strtoi(num);

这样,就可以求一个有系数的项了。

但对于一个没有系数的一次项,怎么办?写一个新的函数:

	bool containnum(string a);

检索一个字符串是否包含数字。

很简单,直接放代码:

bool containnum(string a){
    for(auto&&c:a){
        if(isdigit(c))
            return 1;
    }
    return 0;
}

这样如果containnum(num)false ,则其为一个一次项

这个一次项只会在系数部分中出现,所以逻辑如下:

如果 有数字?
    则按上面的方式计算系数
否则
    则根据前面的符号决定为1或-1

前面的符号就是

num[0]

运用三目表达式压缩: 系数为:

num[0]=='-'?-1:1;

这样的话,就可以完整的计算系数和常数了。

最终的精度控制用printf的格式字符串。

最终的结果即为

-1.0 *constant / coefficient

但有一个问题:C++在处理0/非零数的除法时,经常会出现正负不分的情况。

按照平常的使用习惯,我们规定当系数非零且常数为零时,直接输出0.000

设a为系数,b为常数。

if(a!=0 && b==0)
    cout << sign<<"=0.000" <<endl;
else if(a!=0 && b!=0)
    printf("%c=%.3lf",sign,(-1.0*b/a));

那么整体流程完毕,AC代码见文章开头。

2021/10/16 19:22
加载中...