Formula Finder

    static class Calculator
    {
        private struct Operation
        {
            public char op;
            public double val;
        }

        private const int maxDigits = 6;
        private const int maxPercentage = 2;
        private static readonly double[] concats = { 0f, 8f, 88f, 888f, 8888f, 88888f, 888888f, 8888888f, 88888888f };
        private const double minAcceptable = 1998f - 0.000001f;
        private const double maxAcceptable = 1998f + 0.000001f;

        public static void Start()
        {
            Step(new Stack<double>(10), new Stack<Operation>(30), 0, 0);
        }

        private static bool checkVictory(char op, Stack<Operation> opStack, double result)
        {
            if ( result < minAcceptable || result > maxAcceptable)
            {
                return false;
            }

            if (double.IsNaN(result) || double.IsInfinity(result))
            {
                return true;
            }

            Console.Write(op);
            foreach ( var stackOp in opStack )
            {
                if ( stackOp.op == 'n')
                {
                    Console.Write(" {0}", stackOp.val);
                } else
                {
                    Console.Write(stackOp.op);
                }
            }
            Console.WriteLine();

            return true;
        }

        private static void Step(Stack<double> numStack, Stack<Operation> opStack, int digitsUsed, int percentageCount)
        {
            if( numStack.Count >= 2 )
            {
                var op1 = numStack.Pop();
                var op2 = numStack.Pop();

                var r = op1 + op2;
                if ( !checkVictory('+', opStack, r) )
                {
                    numStack.Push(r);
                    opStack.Push(new Operation() { op = '+', val = 0 });
                    Step(numStack, opStack, digitsUsed, 0);
                    opStack.Pop();
                    numStack.Pop();
                }

                r = op1 - op2;
                if (!checkVictory('-', opStack, r))
                {
                    numStack.Push(r);
                    opStack.Push(new Operation() { op = '-', val = 0 });
                    Step(numStack, opStack, digitsUsed, 0);
                    opStack.Pop();
                    numStack.Pop();
                }

                r = op1 * op2;
                if (!checkVictory('*', opStack, r))
                {
                    numStack.Push(r);
                    opStack.Push(new Operation() { op = '*', val = 0 });
                    Step(numStack, opStack, digitsUsed, 0);
                    opStack.Pop();
                    numStack.Pop();
                }

                r = Math.Pow(op1, op2);
                if (!checkVictory('*', opStack, r))
                {
                    numStack.Push(r);
                    opStack.Push(new Operation() { op = '^', val = 0 });
                    Step(numStack, opStack, digitsUsed, 0);
                    opStack.Pop();
                    numStack.Pop();
                }

                if (op2 != 0)
                {
                    r = op1 / op2;
                    if (!checkVictory('/', opStack, r))
                    {
                        numStack.Push(r);
                        opStack.Push(new Operation() { op = '/', val = 0 });
                        Step(numStack, opStack, digitsUsed, 0);
                        opStack.Pop();
                        numStack.Pop();
                    }
                }

                numStack.Push(op2);
                numStack.Push(op1);
            }

            if ( numStack.Count >= 1 && percentageCount < maxPercentage )
            {
                var op1 = numStack.Peek();
                var r = op1 / 100;
                if (!checkVictory('%', opStack, r))
                {
                    numStack.Pop();
                    numStack.Push(r);
                    opStack.Push(new Operation() { op = '%', val = 0 });
                    Step(numStack, opStack, digitsUsed, percentageCount + 1);
                    opStack.Pop();
                    numStack.Pop();
                    numStack.Push(op1);
                }
            }

            for( int i = 1; i+digitsUsed <= maxDigits; i++ )
            {
                numStack.Push(concats[i]);
                opStack.Push(new Operation() { op = 'n', val = concats[i] });
                Step(numStack, opStack, i + digitsUsed, 0);
                numStack.Pop();
                opStack.Pop();
            }
        }
    }