Vaggelis.M - 5 months ago 32

C Question

I have a some elements in a queue (for example

`/ - 4 2 + 4 5`

that need to be calculated as

`(4-2)/(4+5)`

Answer

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.