conversion from infix to postfix, and, compilation of postfix for eval
 

Hi,
I was trying to write a graph plotting program with c++. I need to convert the infix expression from user to postfix expression for quick evaluation. However, the evaluation of postfix is kind of interpreted, and thus kind of slow for evaluating huge number of values. Say if I plot an implicit function the penalty is quite huge. Is there a way that I can compile the infix expression from my running graph plotting application for high speed evaluation. How can this be best done(also easily if possible)?
Thanks,
Mandeep

In http://fruttenboel.verhoeven272.nl/m4m/Plov21.html.gz I show a small compiler and part of it is a procedure to change normal math into RPN math. Look for procedure 'Expression'.

Hi, thanks for the pointer. Your project is pretty cool. Actually I was thinking in terms of generating expression into c code and compile into a dynamic library and load it at runtime for fastest possible evaluation.

GNU lightning has an RPN calculator example.

No problem.

You only need to scan the InFix expression left to right, keeping an eye on the operator and (possibly) parenthesis. Lets take a line:

Now there are two ingredients: terms and factors. Factors are separated by either '*' or '/' and terms are seperated by either '+' or '-'. A term can be a literal or a group of factors, seperated by factorial operators (* or /).

The first operand behind the assignment operator ':=' can only be a term or a factor. Unless it is a '(' because then it is a full expression coming up. And that's the essence of the scanner... If you want to read a really good text about this, consult 'Compiler Construction' by Niklaus Wirth.

You may find a copy of the latest edition at http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf The fun starts in Chapter 2, Page 9.

But beware! Professor Wirth is a keen writer and if you are a real programmer you may be tempted to read the full book...

The Wirth compilers use recursive descent. The scanners are stand alone procedures (functions) which can be called recursively. So if you are in the TERM scanner, the FACTOR scanner must be callable and (hence) should not rely on global variables. In the PLOV compiler, look for the scanner that deals with comments : anything between a '(*' and a '*)'. The scanner is laid out such that arbitrarily deeply nested comments are dealt with without the need for a depth counter.

I merely read the books of Wirth and then applied it to my compiler project. What you're making is a compiler too. The input is a text file in InFix source code and the output is an RPN-ish object code. A simple compiler it may be, but it still IS a compiler and you should deal with the algorithm of it, based on the fact that your algorithm is FOR A COMPILER. And not for a nuclear power plant emergency valve controller...

More literature you can find on http://fruttenboel.verhoeven272.nl/Oberon/index.html halfway down the page.

thanks
 

Thanks a lot for the information. I am a fan of Niklaus Wirth, I loved the pascal language. He keeps stuff really simple and concise. I downloaded the compiler construction book and I will go through all of it (thanks a lot for the link). Your answer clarifies a lot in few words

Thanks for the answer. I think this would be helpful.