 Vaggelis.M - 3 years ago 98
C Question

# Recursive Calculation of a queue

I have a some elements in a queue (for example

`/ - 4 2 + 4 5`
).

that need to be calculated as
`(4-2)/(4+5)`
. Can someone explain to me the Guillaume Jacquenot

You try to understand a polish notation that is a form of notation for logic, arithmetic, and algebra.

The expression for adding the numbers 4 and 5 is, in prefix/polish notation, written `+ 4 5` rather than `4 + 5`.

The expression for subtracting the numbers 4 and 2 is, in prefix/polish notation, written `- 4 2` rather than `4 - 2`.

Then, operations can be composed. `op3 (op1 m1 n1) (op2 m2 n2)`, which can be interpreted as `(m1 op1 n1) op3 (m2 op2 n2)`, where `op1`, `op2`, `op3` can be `+`, `-`, `*`, `/`.

Parentheses are optional and the previous polish notation can be written `op3 op1 m1 n1 op2 m2 n2`

The easiest way to understand it, is to use a tree. A tree will also help you to better understand the recursive algorithm that are used to evaluate such notations. On such a tree, any operation will be considered as a node, and numbers are leaves.

To evaluate an expression, one needs:

• to parse the expression: it consists in identifying the operators and the numbers and build the associate tree.
• to visit the created tree to evaluate all operations and produce the final result.
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download