Construct a function-callable object from an RPN at a runtime

Question

I'm designing a program that would perform certain operations on a streaming data. Operations are defined by the RPN (reverse polish notation) expressions provided at runtime. Data is being streamed from a file source, one fixed size portion at a time. Operations reference some of the currently input portion of data, like data[1]. The program applies the same operation to all input portions (and streams out the results).

It is quite easy to implement an RPN parser that operates on numbers and arithmetic operation to give the result. However, using such an implementation would imply re-parsing the RPN for every data portion.

What I would like to implement is to build somehow an object that would hold the once parsed RPN implementation based on the alphabet of elementary operations on data, where the program would provide the input data (or fill-in the inputs), invoke the object's operator() to obtain and output the result.

How would one implement such a class (a callable expression) and construct such an object using the 'non-modern' C++ (no C++11 or C++14)?

Answer 1

Since its RPN, the operations can be modeled as a sequence of transformations of a stack. Loading one input portion on the stack and then performing your operations in order would do the trick. No tree needed, it's implicit in the order of operations. No need to reparse either, it would indeed be a sequence of operations (functions or functors) rather then a sequence of symbols denoting operations.

I would choose a functor since I like storing references or pointers to objects better than storing references or pointers to functions. You implement that as a class having an overloaded operator () that does the required stack transformation (like multiplying the two top elements if it's a multiplication functor).

Above: Ancient device working that way...

As to what is stored on the stack and what isn't:

• At first your operands are stored in a queue matching the order of input
• Your operator objects, result of parsing once and never changing, are stored separately in an operator queue.
• Applying the 'get' operator will transfer one operand from the queue to the operand stack

So e.g. if you want to compute

sin (3 + 4) / (5 + 6)

your operand queue is:

[start] 3 4 5 6 [end]

Your operator object queue (it contains pointers to functors, not symbols, each functor has only one instance, but is referenced possibly multiple times) is:

[start] &getFunctor &getFunctor &addFunctor &sinFunctor &getFunctor &getFunctor &addFunctor &divideFunctor [begin]

Your operand stack starts out emptpy:

[top][bottom]

Applying the operator queue will give you subsequently:

(get)    [top] 3 [bottom]
(get)    [top] 3 4 [bottom]
(add)    [top] 7 [bottom]
(sin)    [top] 0.657 [bottom]
(get)    [top] 5  0.657 [bottom]
(get)    [top] 5 6  0.657 [bottom]
(add)    [top] 11  0.657[bottom]
(divide) [top] 0.0597 [bottom]

If you then want to apply exactly the same operations to e.g.

[start]10 20 30 40[end]

just replace the operand queue (or let the start pointer of you operand queue point to the next "chunk" of your operand file, and again run your operator queue against this new sequence of operands.

Note that the operator queue, as said, doesn't hold operator symbols, but pointers to ready-to-go function objects that will do their thing as soon as you call them, without reparsing or regenerating code.

So if you have lots of data:

[start of file]3 4 5 6   10 20 30 40   -1 -10 15 80 ...[end of file]

You just keep applying the same operator queue and everything will work.