how to store a math problem in a binary tree?

Question

If I have the following problem: $\ 12 - (2 +3) - (3 *4)/ (5 -7) $ How would it be stored in a binary tree?

following the order of operations, would you start with $\ (3*4) $ at the top or $\ 12 $ as the first node?

Answer 1

To parse this expression you need to have a grammar for your operators, that describes their precedence and how they associate. A typical operator precedence looks something like

• Expressions in brackets have highest precedence
• Division and multiplication have equal precedence, and associate to the left
• Addition and subtraction have equal precedence, and associate to the left

Associating to the left means that ambiguous expressions like

$$a - b - c$$

are parsed as

$$(a - b) - c$$

rather than

$$a - (b - c)$$

After that, the form of the expression tree is determined. The only potential ambiguity in the expression you gave is the two minus signs, which should be disambiguated as

$$(12 - (2+3)) - ((3\times 4) \;/\;(5 - 7))$$

You then get (in horizontal tree notation)

Subtract
  (Subtract
    (12)
    (Add 2 3))
  (Divide
    (Multiply 2 3)
    (Subtract 5 7))

Answer 2

You should insert parenteses to make every operation properly binary: $(12-(2+3))-(3\cdot4)/(5-7)$. It's primarily a difference, so let the root of your tree have a minus ($-$) on it, then stick $12-(2+3)$ in the left subtree and $(3\cdot4)/(5-7)$ in the right subtree. The left subtree is a difference, so it too has $-$ at its root, while the right subtree will have $/$ at its root. And so on …