Math Expression yielding Max Value

The problem is the following: given a sequence of N numbers (N <= 10), using the most common mathematic operators {+, -, /, *} determine the math expression that will yield the max result. For example, if the numbers given are {1, 2, 3} (and btw, the order matters), you can generate multiple different valid math expressions using {+, -, /, *}, such as:
1 + 2 + 3 = 6
1 / 2 + 3 = 3.5
And so on. However, the expression yielding the max result is 1 + 2*3 = 7.
To solve this problem you need two functions, both recursive ones: first to evaluate a math expression. Second, to generate the different expressions. The math expression evaluator needs to take care of the order of the operators properly - a hint is to go right to left and having the operators inside the main for loop in reverse order of precedence, i.e., addition, subtraction, multiplication and division. The use of brackets is important when you have a case like this one: {-0.2, -0.2}. One of the expressions to be formulated is -0.2/-0.2, and this won't work given the implementation since it will first split based on the minus sign (right to left) which will generate two sub-expressions: -0.2/ and -0.2. The first part is invalid. Using brackets we can easily fix this problem: -0.2/(-0.2), which will be evaluated properly. The generation of the different valid math expressions is a simple Depth-First-Search where we create a tree and each path of the tree represents a valid expression. It is an expensive code: O(4^N). Since N is relatively small, brute-force will do it. Code is below. One sample case to try would be this one:

MaxMathExpression.exe 0.99 1 -0.1 0.11 0.1 -1 0.1

The solution:
0.99+1/(-0.1)/0.11/0.1*(-1)/0.1 = 9091.90 (you can check it here: http://www.wolframalpha.com/input/?i=0.99%2B1%2F%28-0.1%29%2F0.11%2F0.1*%28-1%29%2F0.1)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MaxMathExpression
{
    class Program
    {
        static void Main(string[] args)
        {
            double maxExpressionValue = Double.MinValue;
            string maxExpression = "";
            double[] numbers;
            if (args.Length == 0)
            {
                Console.WriteLine("Usage: MaxMathExpression.exe <list of double numbers>");
                return;
            }
            numbers = new double[args.Length];
            for (int i = 0; i < args.Length; i++)
            {
                numbers[i] = Convert.ToDouble(args[i]);
            }
            CalculateMaxMathExpression(ref numbers,
                                       0,
                                       "",
                                       ref maxExpressionValue,
                                       ref maxExpression);
            Console.WriteLine("Max Mathematical Expression: {0} = {1}", maxExpression, maxExpressionValue.ToString("F"));
        }
        static void CalculateMaxMathExpression(ref double[] numbers,
                                               int currentIndex,
                                               string currentExpression,
                                               ref double maxValue,
                                               ref string maxExpression)
        {
            if (numbers == null)
            {
                return;
            }
            if (currentIndex >= numbers.Length)
            {
                double currentValue = 0;
                if (MathExpressionEvaluator(currentExpression, out currentValue))
                {
                    //Debug{
                    //Console.WriteLine("{0} = {1}", currentExpression, currentValue.ToString("F"));
                    //Debug}
                    if (currentValue > maxValue)
                    {
                        maxValue = currentValue;
                        maxExpression = currentExpression;
                    }
                }
                return;
            }
            string[] operators = null;
            if (currentIndex == 0)
            {
                operators = new string[] { "", "-" };
            }
            else
            {
                operators = new string[] { "+", "-", "*", "/" };
            }
            foreach (string op in operators)
            {
                CalculateMaxMathExpression(ref numbers,
                                           currentIndex + 1,
                                           currentExpression + op + ((numbers[currentIndex] < 0) ? "(" + numbers[currentIndex].ToString() + ")" : numbers[currentIndex].ToString()),
                                           ref maxValue,
                                           ref maxExpression);
            }
        }
        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;
        }
        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;
        }
    }
}

Comments

Popular posts from this blog

Changing the root of a binary tree

Prompt Engineering and LeetCode

ProjectEuler Problem 719 (some hints, but no spoilers)