CODEWITHSUNDEEP
calgorithmdata-structures
Vaggelis.M
Vaggelis.M

Reputation: 5

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 recursive algorithm about this?

Upvotes: 0

Views: 241

Answers (1)

Guillaume Jacquenot
Guillaume Jacquenot

Reputation: 11707

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.

Upvotes: 1

Related Questions