Your problem reduces to zero testing of multivariate polynomials, for which there are efficient randomized algorithms.
Your expressions are all multivariate polynomials. Apparently, your expressions are built up by the following rules: (a) if $x$ is a variable, then $x$ is an expression; (b) if $c$ is a constant, then $c$ is an expression; (c) if $e_1,e_2$ are expressions, then $e_1+e_2$ and $e_1e_2$ are expressions. If that's indeed what you intended, every expression is a multivariate polynomial over the variables.
Now, you want to know if two expressions are equivalent. This amounts to testing whether two multivariate polynomials are equivalent: given $p_1(x_1,\dots,x_n)$ and $p_2(x_1,\dots,x_n)$, you want to know if these two polynomials are equivalent. You can test this by subtracting them and checking whether the result is identically zero: define
$$q(x_1,\dots,x_n) = p_1(x_1,\dots,x_n) - p_2(x_1,\dots,x_n).$$
Now $p_1,p_2$ are equivalent if and only if $q$ is the zero polynomial.
Testing whether $q$ is identically zero is the zero testing problem for multivariate polynomials. There are efficient algorithms for that. For instance, one example algorithm is to evaluate $q(x_1,\dots,x_n)$ at many random values of $x_1,\dots,x_n$. If you find a value of $x_1,\dots,x_n$ such that $q(x_1,\dots,x_n)$, then you know that $q$ is not identically zero, i.e., $p_1,p_2$ are not equivalent. If after many trials they are all zero, then you can conclude that $q$ is identically zero (if $q$ is not identically zero, the probability that all of those trials yield zero can be made exponentially low). The number of iterations you need to do is related to the degree of $q$; see the literature on polynomial identity testing for details.
For instance, see https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma and http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/
These algorithms apply if you are working over a finite field. You didn't state what field/ring you are working in, and whether you are are treating these expressions as formal expressions (e.g., polynomials as abstract objects) or as functions from $\mathbb{F}^n \to \mathbb{F}$. If you are working over a finite field, the methods above apply immediately.
If you're treating the expressions as formal objects, then your expressions are equivalent to multivariate polynomials with integer coefficients. You can test equivalence of these by choosing a large random prime $r$ and testing equivalence modulo $r$, i.e., in the field $\mathbb{Z}/r\mathbb{Z}$. Repeat this polynomially many times, with different random values of $r$, and you should get an efficient randomized algorithm for testing equivalence of these formal expressions.