/*************** Problem from :ds Problem describe : 给出一个表达式 仅含 + * 以及 1-9 保证表达式合法 求怎么加括号使得表达式结果最大和最小 输出最大值和最小值 最大为 先加后乘 最小为 先乘后加 输入仅仅 1-9 data:2016.12.3 ****************/ #include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> #include<map> #include<stack> #include<queue> #include<ctime> #include<cstring> #include<vector> #include<string> #define ll __int64 #define inf 0x3f3f3f3f3f using namespace std; const ll mod = 870764322; int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); stack <ll> Max_que; stack <ll> Min_que; char s[1205]; scanf("%s", s); int len=strlen(s), i; for(i=0; i<len; i++) { //比如 1+2*3+4 遇到 *号时候 把2和3乘起来 if(s[i] == '*') { ll x=(Min_que.top()*(s[i+1]-'0'))%mod; Min_que.pop(); Min_que.push(x); i++; Max_que.push( s[i]-'0' ); } //比如 1*2+3*4 遇到+号时候 把2和3加起来 else if(s[i] == '+') { ll x = ( Max_que.top()+(s[i+1]-'0') )%mod; Max_que.pop(); Max_que.push(x); i++; Min_que.push( s[i]-'0' ); } else if(s[i]>='0' && s[i]<='9') { Max_que.push( s[i]-'0' ); Min_que.push( s[i]-'0' ); } } //求最大值 ll ans=1; while(!Max_que.empty()) { ans = (ans*Max_que.top())%mod; Max_que.pop(); } printf("%I64d\n", ans); //求最小值 ans = 0; while(!Min_que.empty()) { ans = (ans+Min_que.top())%mod; Min_que.pop(); } printf("%I64d\n", ans); return 0; }
