题解：Equation Elation（P1559）

一、题目分析

本题要求解简单的代数方程，并按步骤输出求解过程。关键要点：

• 方程形式为$表达式 = 变量$，如$3 * 4 + 4 - 1 / 1 = xyzzy$
• 需遵循运算优先级：先乘除后加减，同优先级从左到右计算
• 输出每一步运算后的表达式，最终得到$数值 = 变量$的形式

二、解题思路

1. 输入处理：

   • 去除输入中的空格，分离表达式和变量部分
   • 解析表达式中的操作数和运算符

2. 运算处理：

   • 先处理所有乘除运算，再处理加减运算
   • 每次处理一个运算符，更新表达式并输出中间步骤

3. 输出格式：

   • 输出原始方程和每一步运算后的表达式
   • 不同方程的输出之间用空行分隔

三、代码解析

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

string boby;        // 存储等号左边的表达式
string tail;        // 存储等号和变量部分
vector<int> shu;    // 存储操作数
vector<char> op;    // 存储运算符

// 输出当前表达式和变量
void sc() {
    for (int i = 0; i < op.size(); i++) {
        cout << shu[i] << " " << op[i] << " ";
    }
    cout << shu[shu.size() - 1] << tail << endl;
}

int main() {
    while (1) {
        string s;
        getline(cin, s);
        if (cin.eof()) break;  // 输入结束
        
        // 去除空格
        string t = "";
        for (int i = 0; i < s.size(); i++)
            if (s[i] != ' ') t += s[i];
        
        // 分离表达式和变量
        int flag = 0;
        boby = "", tail = "";
        for (int i = 0; i < t.size(); i++) {
            if (flag == 0 && t[i] == '=') flag = 1;
            if (flag == 0) boby += t[i];
            else tail += t[i];
        }
        
        // 处理变量部分格式
        string temp = tail;
        tail = " ";
        for (int i = 0; i < temp.size(); i++) {
            if (temp[i] == '=') tail += "= ";
            else tail += temp[i];
        }
        
        // 解析表达式中的操作数和运算符
        shu.clear();
        op.clear();
        int flag_sign = 0;  // 符号标志（0正，1负）
        int value = 0;
        for (int i = 0; i < boby.size(); i++) {
            // 遇到运算符且前一个字符是数字时，保存当前操作数和运算符
            if ((boby[i] == '*' || boby[i] == '/' || boby[i] == '+' || boby[i] == '-') && 
                (i > 0 && boby[i-1] >= '0' && boby[i-1] <= '9')) {
                op.push_back(boby[i]);
                if (flag_sign == 1) value = -value;
                shu.push_back(value);
                value = 0;
            } 
            // 处理正负号
            else if (boby[i] == '+') flag_sign = 0;
            else if (boby[i] == '-') flag_sign = 1;
            // 处理数字
            else if (boby[i] >= '0' && boby[i] <= '9') {
                value = value * 10 + (boby[i] - '0');
            }
        }
        // 保存最后一个操作数
        if (flag_sign == 1) value = -value;
        shu.push_back(value);
        
        // 输出原始方程
        sc();
        
        // 先处理所有乘除运算
        while (1) {
            int find_op = 0, pos = 0;
            for (int i = 0; i < op.size(); i++) {
                if (op[i] == '*' || op[i] == '/') {
                    find_op = 1;
                    pos = i;
                    break;
                }
            }
            if (find_op == 0) break;  // 无乘除运算，退出
            
            // 计算乘除结果
            int result;
            if (op[pos] == '*') result = shu[pos] * shu[pos + 1];
            else result = shu[pos] / shu[pos + 1];
            
            // 更新操作数和运算符数组
            op.erase(op.begin() + pos);
            shu.erase(shu.begin() + pos);
            shu.erase(shu.begin() + pos);
            shu.insert(shu.begin() + pos, result);
            
            // 输出当前步骤
            sc();
        }
        
        // 处理加减运算
        while (op.size() != 0) {
            int result;
            if (op[0] == '+') result = shu[0] + shu[1];
            else result = shu[0] - shu[1];
            
            // 更新操作数和运算符数组
            op.erase(op.begin());
            shu.erase(shu.begin());
            shu.erase(shu.begin());
            shu.insert(shu.begin(), result);
            
            // 输出当前步骤
            sc();
        }
        
        cout << endl;  // 不同方程间用空行分隔
    }
    return 0;
}

四、关键步骤解析

1. 输入处理

   • 用$getline$读取整行输入，去除所有空格
   • 通过$=$分隔表达式（boby）和变量（tail）
   • 处理变量部分格式，确保$= 变量$的形式（如$= xyzzy$）

2. 表达式解析

   • 遍历表达式字符串，识别操作数和运算符
   • 用$flag_sign$记录操作数的正负（处理Unary运算符）
   • 将操作数存入$shu$数组，运算符存入$op$数组

3. 运算优先级处理

   • 乘除优先：先遍历运算符找到第一个$*$或$/$，计算结果并更新数组
   • 加减后处理：乘除处理完后，依次计算加减运算

4. 步骤输出

   • $sc()$函数按$操作数 运算符 操作数$的格式输出表达式
   • 每次运算后更新数组并输出中间结果
   • 最终输出$数值 = 变量$的形式

五、示例解析

以输入$3 * 4 + 4 - 1 / 1 = xyzzy$为例：

1. 解析结果：

   • 操作数：$[3, 4, 4, 1, 1]$
   • 运算符：$['*', '+', '-', '/']$
   • 变量：$xyzzy$

2. 乘除运算处理：

   • 第一次找到$*$（位置0）：3×4=12，数组更新为$[12, 4, 1, 1]$，运算符$['+', '-', '/']$ 输出：$12 + 4 - 1 / 1 = xyzzy$
   • 找到$/$（位置2）：1÷1=1，数组更新为$[12, 4, 1]$，运算符$['+', '-']$ 输出：$12 + 4 - 1 = xyzzy$

六、注意事项

1. 运算顺序：

   • 严格遵循先乘除后加减，同优先级从左到右
   • 每次处理一个运算符，更新数组后继续处理

2. 格式输出：

   • 输出时操作数和运算符用空格分隔
   • 不同方程的输出之间有一个空行

七、复杂度分析

• 时间复杂度：O(n²)，n为表达式长度（最多20次运算）
  • 解析表达式：O(n)
  • 乘除运算：最多O(n)次，每次O(n)
  • 加减运算：最多O(n)次，每次O(n)
• 空间复杂度：O(n)，存储操作数和运算符

八、可能的优化

1. 表达式解析优化：
   使用栈结构解析表达式，更高效处理运算符优先级

2. 输入处理优化：
   用正则表达式匹配操作数和运算符，减少手动解析错误

3. 代码结构优化：
   将乘除和加减运算处理封装为函数，提高可读性