Find all possible outcomes of a given expression - GeeksforGeeks

Find all possible outcomes of a given expression - GeeksforGeeks
Given an arithmetic expression, find all possible outcomes of this expression. Different outcomes are evaluated by putting brackets at different places.
We may assume that the numbers are single digit numbers in given expression.

vector<int> evaluateAll(string exp, int low, int high)

{

    // To store result (all possible evaluations of

    // given expression 'exp')

    vector<int> res;

 

    // If there is only one character, it must

    // be a digit (or operand), return it.

    if (low == high)

    {

        res.push_back(exp[low] - '0');

        return res;

    }

 

    // If there are only three characters, middle

    // one must be operator and corner ones must be

    // operand

    if (low == (high-2))

    {

        int num = eval(exp[low]-'0', exp[low+1],

                       exp[low+2]-'0');

 

        res.push_back(num);

        return res;

    }

 

    // every i refers to an operator

    for (int i=low+1; i<=high; i+=2)

    {

        // l refers to all the possible values

        // in the left of operator

        vector<int> l = evaluateAll(exp, low, i-1);

 

        // r refers to all the possible values

        // in the right of operator

        vector<int> r = evaluateAll(exp, i+1, high);

 

        // Take above evaluated all possible

        // values in left side of 'i'

        for (int s1=0; s1<l.size(); s1++)

        {

            // Take above evaluated all possible

            // values in right side of 'i'

            for (int s2=0; s2<r.size(); s2++)

            {

                // Calculate value for every pair

                // and add the value to result.

                int val = eval(l[s1], exp[i], r[s2]);

                res.push_back(val);

            }

        }

    }

    return res;

}

Read full article from Find all possible outcomes of a given expression - GeeksforGeeks