CF E. Vanya and Brackets(添加一对括号使得表达式的值最大)

hb120973135

E. Vanya and Brackets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
[size=1em]
Vanya is doing his maths homework. He has an expression of form ,
where x1, x2, ..., xn are
digits from 1 to 9, and sign represents
either a plus '+' or the multiplication sign '*'. Vanya needs
to add one pair of brackets in this expression so that to maximize the value of the resulting expression.

Input
[size=1em]
The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is
odd), its odd positions only contain digits from 1 to 9,
and even positions only contain signs  +  and  * .
[size=1em]
The number of signs  *  doesn't exceed 15.

Output
[size=1em]
In the first line print the maximum possible value of an expression.

Sample test(s)
input
3+5*7+8*4


output
303


input
2+3*5


output
25


input
3*4*5


output
60


Note
[size=1em]
Note to the first sample test. 3 + 5 * (7 + 8) * 4 = 303.
[size=1em]
Note to the second sample test. (2 + 3) * 5 = 25.
[size=1em]
Note to the third sample test. (3 * 4) * 5 = 60 (also many other variants are valid, for instance, (3) * 4 * 5 = 60).
[size=1em]
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
const int N = 5005;
#define LL __int64
char fh[N],s[N];  //����ջ�����ʽ
LL num[N];     //����ջ
int ftop,ntop ,slen;      //����ջ��������ջ��
void calculate(){
if(fh[ftop]=='+')
num[ntop-1]+=num[ntop],ntop--;
else if(fh[ftop]=='-')
num[ntop-1]-=num[ntop],ntop--;
else if(fh[ftop]=='*')
num[ntop-1]*=num[ntop],ntop--;
else if(fh[ftop]=='/')
num[ntop-1]/=num[ntop],ntop--;
ftop--;
}
void countfuction(int l,int r){
ftop=0;ntop=0;
int flagNum=0;
LL ans=0;
for(int i=0; i<=slen; ++i){
if(i!=slen&&(s>='0'&&s<='9')){
ans=ans*10+s-'0';
flagNum=1;
}
else{
if(flagNum)num[++ntop]=ans; flagNum=0;  ans=0;
if(i==slen)break;
if(s=='+'||s=='-'){
while(ftop&&fh[ftop]!='(') calculate();
fh[++ftop]=s;
}
else if(s=='*'&&i==r){
while(ftop&&fh[ftop]!='(') calculate();   ftop--;
while(ftop&&(fh[ftop]=='*'||fh[ftop]=='/')) calculate();
fh[++ftop]=s;//printf(&quot;# &quot;);
}
else if(s=='*'||i==l){
while(ftop&&(fh[ftop]=='*'||fh[ftop]=='/')) calculate();
fh[++ftop]=s;
if(i==l)
fh[++ftop]='(';
}
}
}
while(ftop) calculate();
}
int main(){
while(scanf(&quot;%s&quot;,s)>0){
LL ans=0;
int id[20],k=0;
for(int i=strlen(s); i>=0; i--)
s[i+2]=s;
s[0]='1'; s[1]='*';
slen=strlen(s);
s[slen]='*'; s[slen+1]='1'; s[slen+2]='\0';
slen=strlen(s);
for(int i=0; i<slen; i++)
if(s=='*')
id[k++]=i;
for(int i=0; i<k-1; i++)
for(int j=i+1; j<k; j++){
countfuction(id,id[j]);
if(num[1]>ans)
ans=num[1];
}
printf(&quot;%I64d\n&quot;,ans);
}
}