Evaluating variable from postfix expression

Question

I'm trying to build a solver for single variable equations. I'm using Shunting-yard algorithm, expanded with suggestions by denver and rici. Obviously this algorithm works great to parse trough given math expression, determine its validity and evaluate the value. However, I'm having trouble to understand how to incorporate solving for a certain variable.

If I use the equation 2 * (x - 4) = 4, this can without much fuss be transformed into RPN as 2 x 4 - * 4 -. From here, it would be easy to evaluate the value for any given x. But, how to determine x? I'm looking at gab's answer, and although it's clear to me how to build a tree from the RPN form, I don't understand how to calculate the value (step 5. in his answer).

Thank you.

score 1 · Accepted Answer · answered Apr 15 '20 at 18:57

You what you would do if you solved this with pencil and paper: You move stuff to the other side of the equation until only x remains. Your tree looks like this:

All branches are operators, all leaves are operands. The path from your single variable passed through the * and − nodes on the left-hand side. That means that you must get as much stuff as possible from the left-hand side to the right-hand side, ideally until there is only the x node left.

The first node on the left is a multiplication operator. You can apply the transformation

a * b == c    ⟺    b = c / a

to the tree: Remove the multiplication on the left and insert its inverse operation, division by the constant 2, on the right. Your tree now looks like this:

        =
      /   \
    −       ÷
   / \     / \
  x   4   4   2

The division operates on two constants. You can "fold" them into the result, 2:

(If you have only one variable, you can do that as you create the nodes, so that you don't have an intermediary step with a ÷ node that you are going to delete anyway. You should also detect any divisions by zero here.)

Now move the subtraction operator in the same way:

Calculate the constant expression on the right and you get x == 6.

So you basically turn the top-most left-hand operator into its inverse until there's only the variable left:

a + x == b   ⟺   x == b − a            x + a == b   ⟺   x == b − a
a − x == b   ⟺   x == a − b            x − a == b   ⟺   x == b + a
a * x == b   ⟺   x == b / a            x * a == b   ⟺   x == b / a
a / x == b   ⟺   x == a / b            x / a == b   ⟺   x == b * a

If you have only one variable and have resolved all constant expressions, your x will be the variable or an operator node; the a will be a constant number.

(But careful with division: In the example above, the division has no remainder. If the division has a remainder, integer division will not give the correct result when resolving the value of x and floating-point division will likely introduce small errors.)

Evaluating variable from postfix expression

1 Answers1