Boolean expressions, visitor pattern and.. stack overflow

Boolean expressions, visitor pattern and.. stack overflow

I have some kind of expression library than defines boolean expressions (something that can evaluate to true or false). The code looks like this:

class ExpressionVisitor;

class Expression
{
public:
    virtual ~Expression() {}    
    virtual void Accept(ExpressionVisitor &visitor) = 0;
    //.. other methods
    
}

class ConstantExpression : public Expression
{
public:
    ConstantExpression(bool val) : m_val(val){}
    void Accept(ExpressionVisitor &visitor) override { visitor.VisitConstantExpression(this); }
    bool GetValue() const { return m_val; }
private:
    bool m_val;
}

class NotExpression : public Expression
{
public:
    NotExpression(Expression *pInnerExpression) : m_pInnerExpression(pInnerExpression) {}
    void Accept(ExpressionVisitor &visitor) override { visitor.VisitNotExpression(this); }
    Expression* GetInnerExpression() const { return m_pInnerExpression; }    
private:
    Expression *m_pInnerExpression;
}

class BinaryExpression : public Expression
{
public:
    AndExpression(Expression *pLeftExpression, Expression *pRightExpression) : m_pLeftExpression(pLeftExpression), m_pRightExpression(pRightExpression) {}
    Expression* GetLeftExpression() const { return m_pLeftExpression; }
    Expression* GetRightExpression() const { return m_pRightExpression; }
private:
    Expression m_pLeftExpression, m_pRightExpression;
}

class AndExpression : public BinaryExpression
{
public:
    AndExpression(Expression *pLeftExpression, Expression *pRightExpression) : BinaryExpression(pLeftExpression, pRightExpression) {}
    void Accept(ExpressionVisitor &visitor) override { visitor.VisitAndExpression(this); }
}

class OrExpression : public BinaryExpression
{
public:
    OrExpression(Expression *pLeftExpression, Expression *pRightExpression) : BinaryExpression(pLeftExpression, pRightExpression) {}
    void Accept(ExpressionVisitor &visitor) override { visitor.VisitOrExpression(this); }
}

class ExpressionVisitor
{
public:
    virtual ~ExpressionVisitor() {}
    void VisitConstantExpression(ConstantExpression*);
    void VisitNotExpression(NotExpression*);
    void VisitAndExpression(AndExpression*);
    void VisitOrExpression(OrExpression*);
}

Now to evalate an expression I have a concrete visitor:

class EvaluatorVisitor : public ExpressionVisitor
{
public:
    EvaluatorVisitor() : m_result(false){}
    
    bool GetResult() const { return m_result; }

    void VisitConstantExpression(ConstantExpression* pExpr)
    {
        m_result = pExpr->GetValue();
    }
    void VisitNotExpression(NotExpression* pExpr)
    {
        pExpr->GetInnerExpression()->Accept(this);
        auto innerResult = m_result;
        m_result = !innerResult;
    }
    void VisitAndExpression(AndExpression* pExpr)
    {
        pExpr->GetLeftExpression()->Accept(this);
        auto leftResult = m_result;
        pExpr->GetRightExpression()->Accept(this);
        auto rightResult = m_result;
        m_result = leftResult && rightResult;
    }
    void VisitOrExpression(OrExpression* pExpr)
    {
        pExpr->GetLeftExpression()->Accept(this);
        auto leftResult = m_result;
        pExpr->GetRightExpression()->Accept(this);
        auto rightResult = m_result;
        m_result = leftResult || rightResult;
    }
    
private:
    bool m_result;
}

And I use it like this:

EvaluatorVisitor evaluator;
Expression *pExpr = ...;
pExpr->Accept(&evaluator);
bool result = evaluator.GetResult();

Now for really large (deep) expressions that contains a lot of binary expressions, I get a stack overflow because the EvaluatorVisitor is inherently recursive (because of the Accept() call). How do I solve this (besides the obvious 'increase the stack size')?