заключить в скобки выражение, чтобы получить минимальный результат, используя рекурсию в C ++ - PullRequest
Новая
       30

заключить в скобки выражение, чтобы получить минимальный результат, используя рекурсию в C ++

0 голосов
/ 30 сентября 2019

Итак, я написал этот код для минимизации и максимизации выражения с использованием рекурсии. Код успешно выполняется и дает максимальное значение для выражения. Однако это не дает минимального значения. Куда я иду не так. Две переменные minum и maxum хранят INT_MAX и INT_MIN соответственно.

Я создаю все возможности, и когда результат оказывается минимальным, чем то, что уже сохранено в минимуме, мы обновляем его. 

int parenthesis(string &S, int i, int j, int &minum, int &maxum)
{
    if(i>j)
        return 0;
    if(i==j)
        return S[i]-48;

    int k, rightr, leftr, res;
    for(k=i+1;k<j;k+=2)
    {
        // evaluate the left expression
        leftr = parenthesis(S, i, k-1, minum, maxum);
        // evaluate the right expression
        rightr = parenthesis(S, k+1, j, minum, maxum);
        if(S[k]=='/')
            res = leftr / rightr;
        else if(S[k]=='*')
            res = leftr * rightr;
        else if(S[k]=='-')
            res = leftr - rightr;
        else 
            res = leftr + rightr;

        // update the minum and the maxum variable
        if(res>maxum)
            maxum = res;
        if(res<minum)
            minum = res;

    }
    return res;
}

int main()
{
    string S;
    int N, i, j, k;
    cin>>S;
    int minum=INT_MAX, maxum=INT_MIN;
    j = S.size()-1;
    parenthesis(S, 0, j, minum, maxum);

    cout<<minum<<" "<<maxum;
    return 0;
}

`

Где я иду не так. Почему код дает правильный максимум, но не дает минимального значения. Например, для 1+2*3+4*5 ожидаемый результат равен Minimum value : 27, Maximum value : 105, но я получаю его как Minimum value : 3, Maximum value : 105

Примечание: разрешены только однозначные вводы.

РЕДАКТИРОВАТЬ: Даже если кто-то может сказатьмне причина, почему не работает, которая будет принята как ответ

Ответы [ 2 ]

2 голосов
/ 30 сентября 2019

Рассмотрим следующее решение, оно исследует все возможности. Основной инвариант это то, что для диапазона только пара {max value, min value} являются важными кандидатами из-за нашей ограниченной алгебры (DMAS). Этот жадный выбор может быть аргументирован аргументом exchange (даже для отрицательных чисел, кроме 0 для деления, которое может обрабатываться как особый случай). 

pair<int, int> Maximize(string S, int i, int j)
{
    if(i>j)
        return {0, 0};
    if(i==j)
        return {S[i]-48, S[i]-48};
    int maxim = INT_MIN;
    int minim = INT_MAX;

    int k, res;
    for(k=i+1;k<j;k+=2)
    {
        // evaluate the left expression
        auto leftr = Maximize(S, i, k-1);
        // evaluate the right expression
        auto rightr = Maximize(S, k+1, j);
        for (auto sign1 = 0; sign1 < 2; ++sign1) {
            for (auto sign2 = 0; sign2 < 2; ++sign2) {
                int l = sign1? leftr.first: leftr.second;
                int r = sign2? rightr.first: rightr.second;
                if(S[k]=='/')
                    res = l / r;
                else if(S[k]=='*')
                    res = l * r;
                else if(S[k]=='-')
                    res = l - r;
                else 
                    res = l + r;
                // update the minim and the maxim variable
                if(res>maxim)
                    maxim = res;
                if(res<minim)
                    minim = res;
            }
        }

    }
    return {maxim, minim};
}

int main()
{
    string S;
    int j;
    // cin>>S;
    S = "1+2*3+4*5";
    j = S.size()-1;
    auto res = Maximize(S, 0, j);
    cout << res.first << " " << res.second << "\n";

    return 0;
}
0 голосов
/ 30 сентября 2019

Ваш алгоритм не работает. Проблема в том, что вы оцениваете минимум любого подвыражения. Например, когда k = 3, вы оцениваете «1 + 2» и решили, что оно имеет значение 3 - которое меньше, чем значение любого другого подвыражения, и меньше, чем наименьшее возможное значение из общего выражения.

К сожалению, ваш подход даже не будет работать максимально. Дайте 1/2 + 1, наибольшее возможное значение всего выражения составляет 1 == 1/2 + 1, но наибольшее возможное подвыражение - 3 (2 + 1). Я не знаю, как это исправить.

...