parenthesizing an expression to get minimum result using recursion in C++

Question

So I have written this code to minimize and maximize an expression using recursion. The code successfully runs and give the maximum value for the expression. However it fails to give the minimum value. Where am I going wrong. The two variables minum and maxum stores INT_MAX and INT_MIN respectively.

What I am doing is generating all possibilities and whenever the result comes out to be minimum than what is already stored in minum we are updating it.

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;
}

`

Where am I going wrong. Why does the code gives correct maxum but fails in giving minimum value. For example for 1+2*3+4*5 the expected output is Minimum value : 27, Maximum value : 105 but I am getting it as Minimum value : 3, Maximum value : 105

Note : Only single digit inputs are allowed.

EDIT : Even if someone can tell me the reason, why is not working that will be accepted as an answer

[Why one shouldn't include bits/stdc++.h](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Aconcagua, Sep 30 '19 at 08:07
About [using namespace std](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Aconcagua, Sep 30 '19 at 08:08
@v78 If I understood question right, it is not task to find minimum possible value with arbitrary operations, but just to re-order evaluations (i. e. place parentheses) such that you get minimum or maximum value? And with given example input, we'd expect 27 then... — Aconcagua, Sep 30 '19 at 08:20
Off-topic: You don't modify the string so you should accept it as const reference – otherwise you'll be creating copies with each new recursive call. — Aconcagua, Sep 30 '19 at 08:27
`S[i] - 48` – be aware that this only works for character sets based on ASCII. Admitted, it's rather unlikely that you'll still encounter a machine using an incompatible character set (such as EBCDIC) nowadays, but by writing `S[i] - '0'`, you not only cover *any* arbitrary character set usable for C or C++ (digits from 0-9 succeeding one another is mandated by standard in both languages), but you show more clearly your intention as well. — Aconcagua, Sep 30 '19 at 09:57

score 2 · Answer 1 · answered Sep 30 '19 at 08:51

2

Consider the following solution, it explores all the possibilities. The basic invariant it that for a range only the pair {max value, min value} are the important candidates because of our limited algebra(DMAS). This greedy choice can be argued with exchange argument(even for negative numbers, except 0 for division, which can be handled as a special case).

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;
}

answered Sep 30 '19 at 08:51

v78

2,803
21
44

Please tell me what's wrong in my code? Why it gives correct maximum but not minimum – Sep 30 '19 at 08:55
You are not exploring all of the possibilities, even if you correct `maxim` and `minim` correction. Suppose max of {i...k} / min {k...j} is the maximum for the range{1...j}. – v78 Sep 30 '19 at 08:57
Yes, Now I got it but wait tis should not happen for the input that consists of only * and +. Right? As we do not minimize anything here. We just have to maximize iit. Then why am I not getting correct output? – Sep 30 '19 at 09:04
You are doing too much work, your solution calculates all four possible sums, but only two of these really are needed, the one adding the two maxima and the one the two minima. Similarly for all other operations... – Aconcagua Sep 30 '19 at 09:24
No, @FarhanAhmed, it can happen with + ans -es, because you can end up with min by +ing a smallest number of the range [i...n) or subtracting the largest possible number of [i...n) – v78 Sep 30 '19 at 09:24
No, @Aconcagua, I don't want to miss out potential solutions for min by just looking at range mins. I have to see the range maximas as well. see my comment above. – v78 Sep 30 '19 at 09:26
You cannot! Sum of left and right minima will *always* be smaller than sum of any minimum and any maximum, as well as sum of both maxima will *always* be larger than any other sum... Similarly, you'll get minimum and maximum quotients always by min/max and max/min respectively. – Aconcagua Sep 30 '19 at 09:28

score -2 · Answer 2 · answered Sep 30 '19 at 08:28

-2

Your algorithm is broken. The problem is that you are evaluating the minimum of any sub expression. For example, when k = 3, you evaluate "1+2", and decided that has a value of 3 - which is less than the value of any other sub-expression, and less than the smallest possible value of the total expression.

Sadly, your approach won't even work for maximum. Give 1/2+1, the largest possible value of the whole expression is 1 == 1/2 + 1, but the largest possible sub-expression is 3 (2+1). I don't know how to fix this.

answered Sep 30 '19 at 08:28

Martin Bonner supports Monica

28,528
3
51
88

You got it wrong buddy. We just need to parenthesize our expression. Please read the question – Sep 30 '19 at 08:29
@FarhanAhmed I don't understand your comment. We do you mean "We just need to parenthesize our expression"? What I meant is that if you parenthesize `1+2*3+4*5` as `(1+2)*(3+(4*5))` you will calculate the minimum of `(1+2)` as "3" - which is wrong. – Martin Bonner supports Monica Sep 30 '19 at 16:11

parenthesizing an expression to get minimum result using recursion in C++

2 Answers2