Monday 4 March 2019

Fundamental Algorithms: Parse to RPN

Another one, Parsing to Reverse Polish Notation. Why it's so important? For example, typing to the first calculators, one had to do it in RPN! It's very easy to find a value of an expression in RPN. Deadly simple, having one, like:
3 2 + 4 3 * +
It's enough to take en empty LIFO stack, go through it and:
1 When we see a number push it on stack.
2. Seeing operand, pop stack twice, perform the operation and push result.
3. When done pop stack - this is result!

Parsing is not such easy, but is explained in details, for example, here.
Code on github.
Whole Series.

Thank you!

Fundamental Algorithms: Links

Links to whole series:
1. Order Statistics - C++
2. Polynomial GCD, Polynomial Division - Python
3. Recursive Permutations, All the Subset of Set and Variations With Repetitions - C++
4.Parsing (and evaluating) to RPN