# Finding optimal path for evaluating expressions

I am creating a program which needs to do the following:

I have equations like the following and based on the input I get I should able to calculate the values of $x$, $y$ and $z$

$$x = a + b$$ $$y = x + c$$ $$z = x + y$$

When I get input in the order of $a$, $b$ and $c$ then I can evaluate the expression in the following order

find if $a$ belongs to any expression, if it is find any associated variables available in the input and in this $b$ is available in the input then calculate $x$. Check and see if $x$ is used in any other formula and in this case it is used to calculate $y$, so try to calculate the value of $y$. It requires $c$ use that and calculate $y$. Repeat the same for $y$ and calculate $z$. All works out.

Now if the input comes in different order, based on the formulas that I know before hand, I can sort the input and calculate the formulas properly.

Can any one think of better approach to this problem than the two options I suggested here?

** I can not normalize the equation since each value on left hand side need to be persisted for other purposes **

-
 Do you need to fill in the left hand sides as quickly as possible as the input becomes available (over a network, say), or is all of the input available when you begin processing? – dfeuer Oct 14 '11 at 20:31

You can initialize all variables to zero before accepting user input. If a user does not enter the data of the variable the zero remains assigned (or assign zero if the user does not enter the value). By doing this, you need to evaluate the expressions without further checks.

You can forget about the order of evaluation if you express y and z as follows:

$y=a+b+c$

$z=a+b+a+b+c = 2(a+b)+c$

Edit

As per your comment, consider this approach:

You can build a table like the one below to help you identify the sequence of expression evaluation based on whether a given variable was entered or not.

The input variables are represented with columns as a, b, c, etc. Each column has the value 1 if the data is entered and zero otherwise.

The column named key is a unique representation of the unique input combination.

For each unique input combination, the columns exp1, exp2, ...etc. show the sequence where the calculation needs to be followed. So if user enters a, b, c:

1-Calculate the key to be 111

2-Locate the row in the table

3-Carry on the formulas in the sequence 1,2,3 as indicated by exp1, exp2, exp3

-
 I like what you said about initializing. The expression is a sample. I have around 60 formulas with different set of inputs so I can not combine the formulas. – Nair Oct 14 '11 at 1:06 Thanks for your reply. Have a look at the edited message body. – Emmad Kareem Oct 14 '11 at 1:59 Excellent, I am going to write a sample code and see how it works. I will post my finding here. – Nair Oct 14 '11 at 3:56 Just curious, how would it work on key generation if I have an equation like x = a + b, y = c + d, z = e + f as you can see they are independent equations. – Nair Oct 14 '11 at 18:17 The variables involved are a,b,c,d,e,f so the key is 1,1,1,1,1,1 and the exp1 is: x=a+b, exp2 is: y=c+d and exp3 is z=e+f – Emmad Kareem Oct 14 '11 at 20:18
show 4 more comments

Normalize all equations so they contain all variables on one side of the equal sign with a constant on the other side of the equal sign. Then use Gaussian elimination to zero all elements but the major diagonal (this is called row reduction). The major diagonal will then contain the values of the variables.

-
 each value on left hand side need to be persisted for other purpose so I can not normalize the equation. Ty – Nair Oct 14 '11 at 1:29