数据结构作业——max_and_min(栈)
2024-10-20 20:41:32
Description
TonyY 最近喜欢上了数学,今天他研究一个只有加号和乘号,运算数为整数, 大小在 1-9 之间的表达式,你可以任意地往里加括号,如何让表达式的值最大或 者最小?
Input
输入仅一行,为上述的算式,长度 n(1<=n<=200),保证算式合法。
Output
输 出 添括 号 后 的 算式 最 大 值 和最 小 值 , 由于 答 案 较 大, 请 将 答 案对 870764322 求余后输出。
Sample Input
1+2*3
Sample Output
97
思路
因为表达式只有加、乘两种,所以大大降低了难度,不难证明要使式子值最大,加法的优先级此时要高于乘法,这样才能尽可能使大的数相乘,使式子值最小,按照原来的优先级即可。
#include<iostream> #include<cstdio> #include<stack> #include<cstring> using namespace std; typedef __int64 LL; const LL maxn = 205; const LL mod = 870764322; int main() { LL i,len,tmp1,tmp2,maxres = 1,minres = 0; char str[maxn]; stack<LL>maxstk,minstk; scanf("%s",str); len = strlen(str); maxstk.push(str[0] - '0'); for (i = 1;i < len;i++) { if (str[i] == '+') { tmp1 = maxstk.top(); maxstk.pop(); tmp2 = str[++i] - '0'; maxstk.push(tmp1 + tmp2); } else if (str[i] == '*') { maxstk.push(str[++i] - '0'); } else { maxstk.push(str[i] - '0'); } } while (!maxstk.empty()) { maxres *= maxstk.top(); maxres %= mod; maxstk.pop(); } minstk.push(str[0] - '0'); for (i = 1;i < len;i++) { if (str[i] == '+') { minstk.push(str[++i] - '0'); } else if (str[i] == '*') { tmp1 = minstk.top(); minstk.pop(); tmp2 = str[++i] - '0'; minstk.push((tmp1*tmp2)%mod); } else { minstk.push(str[i] - '0'); } } while (!minstk.empty()) { minres += minstk.top(); minres %= mod; minstk.pop(); } printf("%I64d\n%I64d\n",maxres,minres); return 0; }
最新文章
- 安装MYSQL详细教程 版本:mysql-installer-community-5.7.16.0 免安装版本和安装版本出现错误的解决
- hibernate -- HQL语句总结
- mybatis如何做分页处理
- php----显示中文乱码的问题
- lr常用
- SDUTOJ 3312
- windows下配置启动多个mysql服务
- JavaBean中DAO设计模式介绍(转)
- Java并发编程之闭锁简介
- iptsbles及磁盘扩容
- hbase 命令
- linux下 mysql数据库的备份和还原sql
- shell判断USB接口是否有设备插入
- error: js/dist/app.js from UglifyJs Unexpected token: name (Dom7)
- Delphi XE5开发Android程序使用自定义字体文件.
- [Java笔记]面向对象-单例模式
- RunAsPolicy Exit Code 1替代
- linux上搭建ftp、vsftp, 解决访问ftp超时连接, 解决用户指定访问其根目录,解决ftp主动连接、被动连接的问题
- tornado入门1
- [2016北京集训试题6]网络战争-[最小割树(网络流)+kd-tree+倍增]