Using visitor pattern with large object hierarchy

Question

Context

I've been using with a hierarchy of objects (an expression tree) a "pseudo" visitor pattern (pseudo, as in it does not use double dispatch) :

 public interface MyInterface
 {
      void Accept(SomeClass operationClass);
 }

 public class MyImpl : MyInterface 
 {
      public void Accept(SomeClass operationClass)
      {   
           operationClass.DoSomething();
           operationClass.DoSomethingElse();
           // ... and so on ...
      }
 }

This design was, however questionnable, pretty comfortable since the number of implementations of MyInterface is significant (~50 or more) and I didn't need to add extra operations.

Each implementation is unique (it's a different expression or operator), and some are composites (ie, operator nodes that will contain other operator/leaf nodes).

Traversal is currently performed by calling the Accept operation on the root node of the tree, which in turns calls Accept on each of its child nodes, which in turn... and so on...

But the time has come where I need to add a new operation, such as pretty printing :

 public class MyImpl : MyInterface 
 {
      // Property does not come from MyInterface
      public string SomeProperty { get; set; }

      public void Accept(SomeClass operationClass)
      {   
           operationClass.DoSomething();
           operationClass.DoSomethingElse();
           // ... and so on ...
      }

      public void Accept(SomePrettyPrinter printer)
      {
           printer.PrettyPrint(this.SomeProperty);
      }
 }    

I basically see two options :

• Keep the same design, adding a new method for my operation to each derived class, at the expense of maintainibility (not an option, IMHO)
• Use the "true" Visitor pattern, at the expense of extensibility (not an option, as I expect to have more implementations coming along the way...), with about 50+ overloads of the Visit method, each one matching a specific implementation ?

Question

Would you recommand using the Visitor pattern ? Is there any other pattern that could help solve this issue ?