c++ - 在 C++ 中使用递归将表达式括起来以获得最小结果

Question

所以我编写了这段代码来使用递归最小化和最大化表达式。代码成功运行并给出了表达式的最大值。但是它没有给出最小值。我哪里错了。 minum和maxum两个变量分别存储INT_MAX和INT_MIN。

我正在做的是生成所有可能性，只要结果比已存储在 minum 中的最小，我们就会更新它。

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，最大值:105

注意:只允许输入单个数字。

编辑:即使有人能告诉我原因，为什么不工作也会被接受为答案

Answer 1

考虑以下解决方案，它探讨了所有可能性。基本不变量是，对于一个范围，由于我们的代数 (DMAS) 有限，​​因此只有 {max value, min value} 对是重要的候选者。这种贪婪的选择可以用交换论证来论证(即使是负数，除法 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;
}