Math Expression Evaluator (MEE)

I think the use of a full-fledge Math Expression Evaluator (MEE) might be too overkill for solving this particular problem, but it is always good to have an MEE in your portfolio of tools in case it is needed.

The hard part of this problem is actually the parsing of the expression to create the final one - not actually hard, just a little annoying with the placement of the indexes. Once you have it, use the MEE and save the smallest val. Code is down below, cheers, ACC.

Minimize Result by Adding Parentheses to Expression - LeetCode

2232. Minimize Result by Adding Parentheses to Expression

Medium

You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.

Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.

Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

 

Example 1:

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.

Example 2:

Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.

Example 3:

Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.

 

Constraints:

• 3 <= expression.length <= 10
• expression consists of digits from '1' to '9' and '+'.
• expression starts and ends with digits.
• expression contains exactly one '+'.
• The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

public class Solution {
    public string MinimizeResult(string expression)
    {
        double smallest = Double.MaxValue;
        string retVal = "";

        int midIndex = expression.IndexOf('+');
        string firstHalf = expression.Substring(0, midIndex);
        string secondHalf = expression.Substring(midIndex + 1);

        for (int i = 0; i < firstHalf.Length; i++)
        {
            string exp1 = "";

            if (i == 0)
            {
                exp1 = "(" + firstHalf;
            }
            else
            {
                exp1 = firstHalf.Substring(0, i) + "*(" + firstHalf.Substring(i);
            }

            for (int j = secondHalf.Length - 1; j >= 0; j--)
            {
                string exp2 = "";

                if (j == secondHalf.Length - 1)
                {
                    exp2 = secondHalf + ")";
                }
                else
                {
                    exp2 = secondHalf.Substring(0, j + 1) + ")*" + secondHalf.Substring(j + 1);
                }

                string finalExpression = exp1 + "+" + exp2;

                double current = 0;
                MathExpressionEvaluator(finalExpression, out current);

                if (current < smallest)
                {
                    smallest = current;
                    retVal = finalExpression;
                }
            }
        }

        return retVal.Replace("*", "");
    }
    
        public static bool MathExpressionEvaluator(string expression,
                                               out double result)
    {
        result = 0;
        if (expression == null)
        {
            return false;
        }
        if (expression.Trim().Length == 0)
        {
            return true;
        }
        if (expression.Length > 2 &&
            expression.StartsWith("(") &&
            expression.EndsWith(")") &&
            IsWellFormedBrackets(expression.Substring(1, expression.Length - 2)))
        {
            return MathExpressionEvaluator(expression.Substring(1, expression.Length - 2), out result);
        }

        if (Double.TryParse(expression, out result))
        {
            return true;
        }

        char[] operators = new char[] { '+', '-', '*', '/' };
        foreach (char op in operators)
        {
            int bracketsCount = 0;
            for (int i = expression.Length - 1; i >= 0; i--)
            {
                if (expression[i] == '(')
                {
                    bracketsCount++;
                }
                else if (expression[i] == ')')
                {
                    bracketsCount--;
                }

                if (expression[i] == op &&
                    bracketsCount == 0)
                {
                    double value1 = 0;
                    double value2 = 0;
                    string part1 = "";
                    string part2 = "";

                    if (i > 0)
                    {
                        part1 = expression.Substring(0, i);
                    }
                    if (i + 1 < expression.Length)
                    {
                        part2 = expression.Substring(i + 1);
                    }
                    if (!MathExpressionEvaluator(part1, out value1))
                    {
                        return false;
                    }
                    if (!MathExpressionEvaluator(part2, out value2))
                    {
                        return false;
                    }

                    switch (op)
                    {
                        case '+':
                            result = value1 + value2;
                            break;
                        case '-':
                            result = value1 - value2;
                            break;
                        case '*':
                            result = value1 * value2;
                            break;
                        case '/':
                            if (value2 == 0)
                            {
                                return false;
                            }
                            result = value1 / value2;
                            break;
                    }

                    return true;
                }
            }
        }

        return false;
    }

    public static bool IsWellFormedBrackets(string expression)
    {
        if (expression == null ||
            expression.Trim().Length == 0)
        {
            return true;
        }

        int bracketsCount = 0;
        for (int i = 0; i < expression.Length; i++)
        {
            if (expression[i] == '(')
            {
                bracketsCount++;
            }
            else if (expression[i] == ')')
            {
                bracketsCount--;
            }
            if (bracketsCount < 0)
            {
                return false;
            }
        }

        return bracketsCount == 0;
    }
}