substituting expressions for numbers

edit

If you don't want to use strings, then I think you do have to walk the expression tree at the moment. Sage does come with some tools to help with this in sage.symbolic.expression_conversions, but they could be improved. For example, something like the following should be added to the Sage library:

from sage.symbolic.expression_conversions import Converter

class DoNothing(Converter):
    def arithmetic(self, ex, operator):
        return reduce(operator, map(self, ex.operands()))
    def pyobject(self, ex, obj):
        return ex
    def symbol(self, ex):
        return ex
    def relation(self, ex, operator):
        return operator(*map(self, ex.operands()))
    def derivative(self, ex, operator):
        #We'll just ignore this for now
        return ex 
    def composition(self, ex, operator):
        return operator(*map(self, ex.operands()))

Then,

sage: f = 10*x + 3
sage: d = DoNothing()
sage: d(f)
10*x + 3

With this little utility class in place, you can write:

class TenReplacer(DoNothing):
    def pyobject(self, ex, obj):
        return 99 if obj == 10 else obj

and have

sage: f = 10*x + 3
sage: t = TenReplacer()
sage: t(f)
99*x + 3
sage: t(f == 10)
99*x + 3 == 99
sage: t(f == 100)
99*x + 3 == 100