codeforces 552 E. Vanya and Brackets 表达式求值

时间：2024-01-04 13:41:50

题目链接

讲道理距离上一次写这种求值的题已经不知道多久了。

括号肯定是左括号在乘号的右边， 右括号在左边。 否则没有意义。 题目说乘号只有15个， 所以我们枚举就好了。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <complex>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef complex <double> cmx;

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9+7;

const int inf = 1061109567;

const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

stack <char> sign;

stack <ll> digit;

int a[20];

string str;

void cal() {

    char s = sign.top(); sign.pop();

    ll x = digit.top(); digit.pop();

    ll y = digit.top(); digit.pop();

    ll tmp;

    if(s == '+')

        tmp = x+y;

    else

        tmp = x*y;

    digit.push(tmp);

}

ll solve(){

    if(!digit.empty())

        digit.pop();

    for(int i = 0; i < str.size(); i ++) {

        if(isdigit(str[i])) {

            digit.push(str[i]-'0');

        } else if(str[i] == '(') {

            sign.push('(');

        } else if(str[i] == ')') {

            while(sign.top() != '(') {

                cal();

            }

            sign.pop();

        } else if(str[i] == '*') {

            sign.push('*');

        } else {

            while(!sign.empty() && sign.top() == '*')

                cal();

            sign.push('+');

        }

    }

    while(!sign.empty())

        cal();

    return digit.top();

}

int main()

{

    string s;

    cin>>s;

    int cnt = 0;

    a[cnt++] = -1;

    for(int i = 0; i < s.size(); i++)

        if(s[i] == '*')

            a[cnt++] = i;

    a[cnt++] = s.size();

    ll ans = 0;

    for(int i = 0; i < cnt; i ++) {

        for(int j = i+1; j < cnt; j ++) {

            str = s;

            str.insert(a[i]+1, 1, '(');

            str.insert(a[j]+1, 1, ')');

            ans = max(ans, solve());

        }

    }

    cout<<ans<<endl;

    return 0;

}

相关文章