Codeforces Round #308 (Div. 2) E. Vanya and Brackets

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
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  * .

The number of signs  *  doesn’t exceed 15.

Output
In the first line print the maximum possible value of an expression.

Examples
inputCopy
3+5*7+8*4
outputCopy
303
inputCopy
2+3*5
outputCopy
25
inputCopy
3*4*5
outputCopy
60
Note
Note to the first sample test. 3 + 5 * (7 + 8) * 4 = 303.

Note to the second sample test. (2 + 3) * 5 = 25.

Note to the third sample test. (3 * 4) * 5 = 60 (also many other variants are valid, for instance, (3) * 4 * 5 = 60).

给定表达式，加入括号使运算结果最大；

枚举位置然后求最大即可：

#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
#define inf 0x3f3f3f3f
typedef long long ll;
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b%2)ans=ans*a;
        a=a*a;
        b=b/2;
    }
    return ans;
}
vector<int> pos;
stack<ll>num;
stack<char> ch;

ll cal(string s)
{
    while(!num.empty())num.pop();
    while(!ch.empty())ch.pop();
    for(int i=0;i<s.length();i++){
        char c=s[i];
        if(c>='0'&&c<='9')num.push(c-'0');
        else if(c=='('){
              ch.push(c);
        }
        else if(c==')'){
            while(ch.top()!='('){
                    char x=ch.top();ch.pop();
                    ll a=num.top();num.pop();
                    ll b=num.top();num.pop();
                    if(x=='*')num.push(a*b);
                    else num.push(a+b);
        }
        ch.pop();
    }
        else {
            if(c=='+'){
                while(!ch.empty()&&ch.top()=='*'){
                    char x=ch.top();ch.pop();
                    ll a=num.top();num.pop();
                    ll b=num.top();num.pop();
                    if(x=='*')num.push(a*b);
                    else num.push(a+b);
                }
                ch.push(c);
            }
            else ch.push(c);
        }
}
        while(!ch.empty()){
            char x=ch.top();ch.pop();
            ll a=num.top();num.pop();
            ll b=num.top();num.pop();
            if(x=='*')num.push(a*b);
            else num.push(a+b);
        }
        return num.top();
}
int main()
{
    ios::sync_with_stdio(false);
    string str;
    while(cin>>str){
        int n=str.size();
        pos.clear();
        pos.push_back(-1);
        for(int i=1;i<n;i+=2){
            if(str[i]=='*'){
                pos.push_back(i);
            }
        }
        pos.push_back(n);
        int len=pos.size();
        ll ans=0;
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                string s=str;
                s.insert(pos[i]+1,1,'(');
                s.insert(pos[j]+1,1,')');
                ans=max(ans,cal(s));

            }
        }
        cout<<ans<<endl;
    }

}