I have the following (simplified) interfaces and classes (in C#). In this simplified example, I am modeling algebraic binary expressions exploiting the Visitor Pattern for their computation. I have expressions which evaluate to integer numbers and they can be composed of additions, multiplications, and integer numbers. The expressions are designed to be immutable thus, once an expression has been computed, i can save its value in the field Value.

public interface IGenericExpression<T>
{
    public IGenericExpression<T> LeftExpression { get; set; }
    public IGenericExpression<T> RightExpression { get; set; }
    public T Value { get; }
    public T Compute();
    public void Accept(IExpressionVisitor visitor);
}

public class IntExpression : IGenericExpression<int>
{
    public IGenericExpression<int> LeftExpression { get; set; }
    public IGenericExpression<int> RightExpression { get; set; }
    internal int? _value;
    public int Value => _value ??= Compute();
    public int Compute() => _value ??= new IntExpressionEvaluator().GetResult(this);
    public void Accept(IExpressionVisitor visitor) => visitor.Visit(this);
}

public class NumberExpression : IntExpression
{
    public NumberExpression(int number)
    {
        _value = number;
    }
}

public class AdditionExpression : IntExpression;

public class MultiplicationExpression : IntExpression;

public interface IExpressionVisitor
{
    public void Visit(IGenericExpression<int> expression);
    public void Visit(NumberExpression expression);
    public void Visit(AdditionExpression expression);
    public void Visit(MultiplicationExpression expression);
}

public class IntExpressionEvaluator : IExpressionVisitor
{
    private int result;

    public int GetResult(IntExpression expression)
    {
        expression.Accept(this);
        return result;
    }

    public void Visit(IGenericExpression<int> expression) =>
        throw new InvalidOperationException("Missing visit method for type " + expression.GetType());

    public void Visit(NumberExpression expression) => result = expression.Value;

    public void Visit(AdditionExpression expression)
    {
        expression.LeftExpression.Accept(this);
        var resLeft = result;
        expression.RightExpression.Accept(this);
        var resRight = result;
        result = resLeft + resRight;
    }

    public void Visit(MultiplicationExpression expression)
    {
        expression.LeftExpression.Accept(this);
        var resLeft = result;
        expression.RightExpression.Accept(this);
        var resRight = result;
        result = resLeft * resRight;
    }
}

My problem is the following. Imagine to have a very complex expression with a huge number of additions and multiplications. In the current state of the code, by calling Compute() on the expression, the property Value is set only for the caller of Compute(). Actually (for the immutability of the objects), I could save the value of each sub-expression evaluated during the computation of the main expression and I would like to do so.

What I have tried was to modify the Visit methods by substituting the calls to Accept with expression.LeftExpression.Value and expression.RightExpression.Value. But, in this way, at the first evaluation of the expression each sub-expression will require the allocation of another (unnecessary) evaluator object. To avoid this, in first instance, i decide to translate the IntExpressionEvaluator in a Singleton class, but actually i think that this is not the proper use case for the Singleton Pattern and, additionally, i think this may be limiting if i use more threads in parallel which want to compute their expressions. Therefore, i adopted another solution, which is equivalent to the one written above but i set the internal property _value (if it is equal to null) for both the LeftExpression and RightExpression. Also this last solution has some limitations since it requires to cast each LeftExpression and RightExpression to the type IntExpression.

Do you have any further suggestion about the mentioned solutions or new ones? Maybe, is the best solution a re-design?
I want to specify also that some elements in the code above may look strange but i underline that it is only a simplified example (however, any criticism is appreciated). Thank you in advance.