What is an efficient way to store mathematical expressions for evaluation?

My goal is to write a program that can parse mathematical expressions including variables - like "x^2+3y+sin(x)" - and then evaluate them when given their values (so for x=0, y=1, the output would be 3).

There is no problem with the parsing itself - I used a version of the shunting yard algorithm and it works well. However, I am now thinking how to store the output in a way that can be easily evaluated.

One way would be to simply replace all variables in the expression with their values and then evaluate it. That would be fine if the expression were evaluated once - however, I expect that there will be one expression and many different values will be plugged into it. Thus, I would like to find a way to store the parsed expression so that substituting the variables and evaluating it is fast, as well as reasonably memory-efficient. Any ideas?

One way that occured to me was to store the expression as an array of tokens in reverse Polish notation, which can be evaluated efficiently.
The Token couldlook something like this:

enum TokenType {NUMBER, VARIABLE, OPERATOR, FUNCTION};

struct Token
{
  TokenType type;
  union
  {
    int value; // if type = NUMERIC
    int variable_index;  // if type = VARIABLE
    operator_params op;  // if type = OPERATOR
    function_params fun; // if type = FUNCTION
  }
}

The variable values could be strored in a simple array and accesed by the variable index of the Token. When the values change, we can just update the array of variable values - the expression stays the same.

I am not sure what the best way to store operators and functions for this application is. My thoughts go towards having a function pointer that points to the right operation, but I am not sure if that is the best way.

Ordering the tokens in RPN order is one way to do it, and quite performant.
The tokens would either be literals, variables or operators. To evaluate the expression, you process the tokens in order, and if it's a literals or variable, you push its value to a stack. If it's an operation, you pop one or two items from the stack (depending on whether it is a unary or binary operator), apply the operation on those items, and push the result back. For well-formed expressions, you will be left with one value on the stack at the end, which is the final result of the evaluation.

Another approach which works is to create nested lambda expressions, as I've shown in this CodeReview post. The main advantage of that is that the result of parsing the expression is a lambda function which works pretty much the same as a regular function in C++.