P1022 [NOIP2000 普及组] 计算器的改良

题解

题目链接

P1022 [NOIP2000 普及组] 计算器的改良

题目大意

给定一个合法有解的一元一次方程，其中只包含整数系数以及 +, -, =, 求该方程的解。
如：

• \(6a−5+1=2−2a\)
• \(−5+y=2y+6\)

等。

大体思路

按正常解方程思路来模拟，可以将原方程化简成 \(ax=b\) 的形式，则可得方程解 \(x=b/a\) 。
模拟过程中按各个数字是未知数前的系数 \(a\) 还是常数项 \(b\) 统计即可。

时间复杂度与空间复杂度分析

很显然，线性的模拟，时间与空间复杂度均为 \(O(n)\)

完整代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    s += '=';  //在字符串末尾加上'=', 相当于结束符号, 避免特判

    long long a = 0, b = 0;  //a: 未知数前的系数, b: 常数项
    char x;
    long long num = 0, flag = 0, pos = 1;  //flag: 当前数字项是否是负数, pos: 1表示在等号左边，-1表示在等号右边
                                           //这里相当于将未知数的系数全部移项至等号左边，常数项全部移项至等号右边
    for (int i = 0; i < s.size(); ++i) {
        if (!isdigit(s[i])) {
            if (flag) num *= -1;

            if (isalpha(s[i])) {
                x = s[i];
                a += pos * (num ? num : 1);
            }
            else b -= pos * num;

            num = flag = 0;
            if (s[i] == '-') flag = 1;
            if (s[i] == '=') pos = -1;  //遇到等号，说明要到等号右边了，将pos改为-1
        }
        else num = num * 10 + s[i] - '0';
    }
    printf("%c=%.3f\n", x, 1.0 * b / a);

    return 0;
}

AC提交记录

(https://www.luogu.com.cn/record/176528736)

平均 \(3\) ~ \(4ms\)，没什么问题