当前位置: 首页 > news >正文

中国电子系统建设三公司网站网络营销与直播电商

中国电子系统建设三公司网站,网络营销与直播电商,深圳代办注册公司执照,佛山做外贸网站咨询题目链接:According to Bartjens 题目描述: 给定一个由数字和一个组成的字符串,你需要在数字之间添加,−,∗,-,*,−,∗三种符号,在保证表达式合法的情况下(同时形成的新的数字不能有前导零),使表…

题目链接:According to Bartjens
题目描述:

给定一个由数字和一个===组成的字符串,你需要在数字之间添加+,−,∗+,-,*+,,三种符号,在保证表达式合法的情况下(同时形成的新的数字不能有前导零),使表达式的结果等于200020002000,输出所有可能的添加方案(你至少要添加一个符号),按照字典序从小到大进行输出。
例如2100100=2100100=2100100=的解如下:
在这里插入图片描述

题解:

本题只知道至少添加一个符号,所以我们需要依次枚举添加一个、两个、三个一直到n−2n-2n2个(nnn为表达式的长度),然后使用DFSDFSDFS尝试在每个位置放置符号,放置的时候需要注意不能出现含有前导零的数字,保证不出现前导零有两种方案:

  • 枚举所有位置,在最后进行检查的时候判断出现在计算符号之后的数字以000开头但是位数大于111
  • 在搜索的过程中进行判断,假定搜索到位置pospospos如果当前位置是000那么当前位置的后面只能放置非数字符号;

如何计算表达式的值?可以使用逆波兰表达式,具体的使用两个栈,一个用来保存数字,一个用来保存符号,符号站里面的符号的优先级要保证递增:

  • 遇到数字则直接加入数字栈;
  • 遇到符号的时候,检查符号与符号栈栈顶的符号的优先级,如果栈顶的符号优先级较高或相等,那么则应该弹出栈顶的符号进行一次计算,直到符号栈为空,或者栈顶的符号优先级较低,再将当前的符号入栈;
  • 最后弹出符号栈里面的所有符号依次进行计算。

代码:

#include <bits/stdc++.h>const int NaN = 0x3f3f3f3f;
const int OPERATOR_NUM = 3;using namespace std;int maxDepth, caseID;
string expression, now;
char ope[] = "*+-";
vector<string> 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;stack<int> number;stack<char> 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;
}
http://www.hrbkazy.com/news/21570.html

相关文章:

  • 公司建网站找哪家投放广告的网站
  • 天津河西做网站百度推广最近怎么了
  • 技术研发流程的六个阶段百度关键词搜索优化
  • dw做旅游网站毕业设计模板下载橙子建站怎么收费
  • 广州黄埔网站建设公司腾讯会议多少钱一个月
  • apache 配置网站地址百度指数分析大数据
  • 网站制作和如何推广怎么联系百度人工服务
  • 域名邮箱登录入口关键词优化排名的步骤
  • 网站后台不显示验证码win7优化大师官方网站
  • 扁平化网站设计趋势seo优化就业前景
  • 江门网站建设联系电话semaphore
  • 套模版做网站武汉seo管理
  • 微信网站什么做什么是淘宝搜索关键词
  • 做网站每年运营要花掉多少钱营销技巧有哪些
  • 专做律师网站用手机制作自己的网站
  • 网站设计岗位的职责与要求网络推广是做什么工作的
  • 建设网站代办机构优书网
  • php网站建设素材seo和网络推广有什么区别
  • 门户网站 cms推广方式营销方案
  • 湖州 网站建设seo优化广告
  • 关于动物自己做的网站软文推广例子
  • 页面设计的像胶囊怎么形容深圳网站设计实力乐云seo
  • 有什么做家常菜的网站网址收录平台
  • html网站开发心得体会亚马逊查关键词排名工具
  • 怎样进行seo推广seo有哪些优化工具
  • 网站公司建设个服务号多少钱市场营销在线课程
  • 有哪些网站做任务有佣金seo怎么优化关键词排名
  • 汽车网站正在建设中模板中国seo排行榜
  • 做网络的网站很重要吗网站开发的一般流程
  • 做网站策划用什么软件2023年5月份病毒感染情况