There are a number of ways of writing expressions: normal infix notation,
prefix (function) notation, postfix (reverse Polish) notation, and as
trees. Trees are hard to represent in our normal text-based writing
systems, however, they are easy to use in a computer.
For this example assume we have the +, -, *, and / operators
and that we just have integers. The tree for (7-5) * (3+(1-2)) would look like:
*
/ \
/ \
- +
/ \ / \
# # # -
7 5 3 / \
# #
1 2
Each node in the tree can be represented as a struct/class,
with the following fields:
- The operator, which we can encode as a char variable.
We'll represent integers with the special operator '#'
and we'll have a field that contains the integer value.
- The integer value. This field is always there, but is
only used with the '#' operator.
- A pointer to the the left subtree if it's not the '#' operator
(a terminal node).
- A pointer to the right subtree as above.
Processing trees is made especially easy because it can be done
in a nice, compact, natural, recursive manner.
See the two examples of how to declare this: