算法标签：

dfs

问题概述

本题核心任务是解决等式构造问题。给定包含等号的等式，其中等式右边的运算符（仅涉及“+”“-”“*”）存在缺失情况，需要通过程序找到合适的运算符组合，使等式成立。若存在这样的组合，输出完整等式；若不存在，则输出“Impossible”。

解题思路

1. 输入处理：从标准输入读取等式，先解析出等号左边的数值。对于等式右边，将数字、括号按顺序存储起来，同时标记出可插入运算符的位置，为后续填充运算符做准备。在处理过程中，会跳过输入中的空格，避免干扰数据解析。
2. 深度优先搜索（DFS）：利用深度优先搜索算法，对标记的运算符位置进行遍历。在每一个运算符位置，依次尝试“+”“-”“*”三种运算符，通过递归的方式处理下一个运算符位置，从而穷举所有可能的运算符组合情况。
3. 表达式计算：针对每一种运算符组合，通过特定的计算规则对等式右边的表达式求值。计算时遵循先括号内后括号外、先乘除后加减的运算优先级。遇到括号时，优先计算括号内的表达式；遇到乘除或加减运算符时，对相邻的数字进行相应运算。
4. 结果判断与输出：计算完等式右边表达式的值后，将其与等式左边的数值进行比较。若相等，说明找到了满足条件的运算符组合，将该组合对应的等式输出；若尝试完所有组合都无法使等式成立，则输出“Impossible” 。

关键步骤解析

• 输入解析：通过字符串处理和数值提取方法，将等式拆分为等号左边的数值和右边的数字、括号序列，并记录可插入运算符的位置，为后续操作提供基础数据。
• 深度优先搜索：深度优先搜索的递归过程保证了对所有可能的运算符组合进行探索，通过不断尝试不同运算符，找到符合等式成立条件的组合。
• 表达式求值：基于运算优先级的计算规则，确保等式右边表达式计算结果的准确性，是判断等式是否成立的关键依据。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <cstdio>  // 添加这个头文件以使用sscanf
using namespace std;

//构造为表达式用到的代替数字
#define LEFT  -1    // 左括号
#define RIGHT -2    // 右括号
#define MUL   -3    // *
#define ADD   -4    // +
#define SUB   -5    // -
#define OP    -6    // 有运算符
#define NONE  -10

const int maxn = 100;
string a;   // 原始的等式数据
int b[maxn];    // 伪表达式
int best[maxn]; // 存储答案
int op[maxn];   // 运算符在数组b中的位置
int bn;         // 数组b的项数
int iLeft;      // 等号左边的数
int possible;   // 是否有解
int apos, bpos, opos;   // 位置指针

// 跳过空格
void skipSpace() {
	while (apos < static_cast<int>(a.length()) && a[apos] == ' ') apos++;
}

int compute(); //前向声明，间接递归

//若有括号返回括号里面的值，否则返回当前数字
int bracket() {
	int sum;
	if (b[bpos] == LEFT) {
		bpos++; // 跳过左括号
		sum = compute();    // 计算括号里面的值
		bpos++; // 跳过右括号
	}
	else sum = b[bpos++];    // 没有括号
	return sum;
}

//计算函数
int compute() {
	int sum = bracket(); //当前值
	while (b[bpos] == MUL || b[bpos] == ADD || b[bpos] == SUB) {
		int operation = b[bpos++];     // 取出运算符
		int ret = bracket();    // 取下一个数
		switch (operation) {
			case MUL: sum *= ret; break;
			case ADD: sum += ret; break;
			case SUB: sum -= ret; break;
		}
	}
	return sum;
}

void dfs(int dep) {
	if (possible) return;
	// 所有的运算符构造完毕，判断等式是否成立
	if (dep == opos) {
		bpos = 0;
		int iRight = compute();
		//等式成立
		if (iRight == iLeft) {
			possible = 1;
			for (int i = 0; i < bn; ++i) best[i] = b[i];
		}
		return;
	}
	
	// Hint: 这里有顺序要求
	b[op[dep]] = ADD; dfs(dep + 1);
	b[op[dep]] = SUB; dfs(dep + 1);
	b[op[dep]] = MUL; dfs(dep + 1);
	
}

int main() {
	int _ = 1;
	while (getline(cin, a) && a.find('=') != string::npos) {
		possible = 0;
		for (int i = 0; i < maxn; ++i) b[i] = NONE; //初始化伪表达式
		apos = 0; //初始化原表达式指针
		sscanf(a.c_str(), "%d", &iLeft);    // '='左边的数
		while (apos < static_cast<int>(a.length()) && isdigit(a[apos])) apos++; //跳过左边数字
		skipSpace(); //跳过空格
		apos++; //跳过 '='
		// 处理'='右边
		bn = 0;
		opos = 0;
		while (skipSpace(), apos < static_cast<int>(a.length())) {
			if (a[apos] == '(') { // 左括号
				b[bn++] = LEFT;
				apos++;
				continue;
			}
			if (a[apos] == ')') { // 右括号
				b[bn++] = RIGHT;
				apos++;
			}
			else {
				sscanf(a.substr(apos).c_str(), "%d", &b[bn++]);   // 读取数字
				while (apos < static_cast<int>(a.length()) && isdigit(a[apos])) apos++; //跳过该数字
			}
			skipSpace();
			// 如果不是结尾和')'，则有一个运算符
			if (apos < static_cast<int>(a.length()) && a[apos] != ')') {
				op[opos++] = bn;
				b[bn++] = OP;
			}
		}
		
		dfs(0);
		cout << "Equation #" << _++ << ":\n";
		if (!possible ||!bn) {
			cout << "Impossible\n";
		}
		else if (bn == 1 && iLeft == b[0]) {
			cout << iLeft << "=" << iLeft << "\n";
		}
		else {
			cout << iLeft << "=";
			for (int i = 0; i < bn; ++i) {
				switch (best[i]) {
					case ADD:   cout << "+"; break;
					case SUB:   cout << "-"; break;
					case MUL:   cout << "*"; break;
					case LEFT:  cout << "("; break;
					case RIGHT: cout << ")"; break;
					default :   cout << best[i]; break; // 修正：显示best[i]而非b[i]
				}
			}
			cout << "\n";
		}
		cout << "\n";
	}
	
	return 0;
}