个人网站命名 备案,网站开发前期准备工作,深圳二次源网站建设,成品网站w在线观看题目链接#xff1a;According to Bartjens 题目描述#xff1a; 给定一个由数字和一个组成的字符串#xff0c;你需要在数字之间添加,−,∗,-,*,−,∗三种符号#xff0c;在保证表达式合法的情况下#xff08;同时形成的新的数字不能有前导零#xff09;#xff0c;使表…题目链接According to Bartjens 题目描述 给定一个由数字和一个组成的字符串你需要在数字之间添加,−,∗,-,*,−,∗三种符号在保证表达式合法的情况下同时形成的新的数字不能有前导零使表达式的结果等于200020002000输出所有可能的添加方案你至少要添加一个符号按照字典序从小到大进行输出。 例如210010021001002100100的解如下 题解 本题只知道至少添加一个符号所以我们需要依次枚举添加一个、两个、三个一直到n−2n-2n−2个nnn为表达式的长度然后使用DFSDFSDFS尝试在每个位置放置符号放置的时候需要注意不能出现含有前导零的数字保证不出现前导零有两种方案 枚举所有位置在最后进行检查的时候判断出现在计算符号之后的数字以000开头但是位数大于111在搜索的过程中进行判断假定搜索到位置pospospos如果当前位置是000那么当前位置的后面只能放置非数字符号 如何计算表达式的值可以使用逆波兰表达式具体的使用两个栈一个用来保存数字一个用来保存符号符号站里面的符号的优先级要保证递增 遇到数字则直接加入数字栈遇到符号的时候检查符号与符号栈栈顶的符号的优先级如果栈顶的符号优先级较高或相等那么则应该弹出栈顶的符号进行一次计算直到符号栈为空或者栈顶的符号优先级较低再将当前的符号入栈最后弹出符号栈里面的所有符号依次进行计算。 代码
#include bits/stdc.hconst int NaN 0x3f3f3f3f;
const int OPERATOR_NUM 3;using namespace std;int maxDepth, caseID;
string expression, now;
char ope[] *-;
vectorstring ans;// 比较两个运算符的优先级
int cmp(char op1, char op2)
{if (op1 op2) { return 0; }if (op1 *) { return 1; }if (op2 *) { return -1; }return 0;
}// 计算两个数的和、差或者积
int calculate(int lhs, char ope, int rhs)
{if (ope ) { return lhs rhs; }if (ope -) { return lhs - rhs; }return lhs * rhs;
}bool check()
{int num NaN, lhs 0, rhs 0;stackint number;stackchar ops;for (int i 0; i now.length() - 1; i) {if (isdigit(now[i])) {if (num NaN) { num 0; }num num * 10 now[i] - 0;} else {number.push(num);while (!ops.empty() cmp(ops.top(), now[i]) 0) {rhs number.top(); number.pop();lhs number.top(); number.pop();number.push(calculate(lhs, ops.top(), rhs));ops.pop();}ops.push(now[i]);num NaN;}}if (num ! NaN) { number.push(num); }while (!ops.empty()) {rhs number.top(); number.pop();lhs number.top(); number.pop();num calculate(lhs, ops.top(), rhs); ops.pop();number.push(num);}return number.top() 2000;
}void dfs(int nowDepth, int pos)
{if (nowDepth maxDepth) {int tempLen now.length();int increment expression.length() - pos;now.append(expression.substr(pos, increment));if (check()) { ans.push_back(now); }now.erase(tempLen, increment);return;}if (maxDepth - nowDepth expression.length() - 2 - pos) { return; }for (int i pos; i expression.length() - 2; i) {// 这里是保证最后一个数字不含有前导零if (nowDepth maxDepth - 1 expression[i 1] 0 expression[i 2] ! ) { continue; }for (int j 0; j OPERATOR_NUM; j) {int tempLen now.length();int increment i - pos 1 1;now.append(expression.substr(pos, i - pos 1));now.push_back(ope[j]);dfs(nowDepth 1, i 1);now.erase(tempLen, increment);}// 这里保证当前数字不含前导零当前数字如果是以0开头那么不能继续进行拼接if (expression[pos] 0) { break; }}
}int main()
{while (cin expression) {ans.resize(0);now ;if (expression[0] ) { break; }for (maxDepth 1; maxDepth expression.length() - 1; maxDepth) { dfs(0, 0); }caseID;cout Problem caseID endl;sort(ans.begin(), ans.end());for (auto str : ans) { cout str endl; }if (ans.size() 0) { cout IMPOSSIBLE endl; }}return 0;
}
