LinuxQuestions.org
Did you know LQ has a Linux Hardware Compatibility List?
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 05-11-2010, 03:22 AM   #1
mandeep.singh.bhatia
LQ Newbie
 
Registered: Apr 2010
Location: Delhi, India
Distribution: openSuse
Posts: 6

Rep: Reputation: 0
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

Last edited by mandeep.singh.bhatia; 05-11-2010 at 03:50 AM. Reason: forgot to mention prog lang
 
Old 05-11-2010, 05:23 AM   #2
fruttenboel
Member
 
Registered: Jul 2008
Posts: 270

Rep: Reputation: 48
Quote:
Originally Posted by mandeep.singh.bhatia View Post
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'.
 
Old 05-12-2010, 03:09 AM   #3
mandeep.singh.bhatia
LQ Newbie
 
Registered: Apr 2010
Location: Delhi, India
Distribution: openSuse
Posts: 6

Original Poster
Rep: Reputation: 0
Smile

Quote:
Originally Posted by fruttenboel View Post
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.
 
1 members found this post helpful.
Old 05-12-2010, 10:14 AM   #4
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian
Posts: 2,541

Rep: Reputation: 878Reputation: 878Reputation: 878Reputation: 878Reputation: 878Reputation: 878Reputation: 878
GNU lightning has an RPN calculator example.
 
1 members found this post helpful.
Old 05-12-2010, 08:05 PM   #5
fruttenboel
Member
 
Registered: Jul 2008
Posts: 270

Rep: Reputation: 48
Quote:
Originally Posted by mandeep.singh.bhatia View Post
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.
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:

Code:
sum := a1 + a2 * b3 + a3 / (3 - 1) + a4
avg := sum / count
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.

Last edited by fruttenboel; 05-12-2010 at 08:21 PM. Reason: I forgot some things
 
2 members found this post helpful.
Old 05-13-2010, 06:45 AM   #6
mandeep.singh.bhatia
LQ Newbie
 
Registered: Apr 2010
Location: Delhi, India
Distribution: openSuse
Posts: 6

Original Poster
Rep: Reputation: 0
Thumbs up thanks

Quote:
Originally Posted by fruttenboel View Post
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:

Code:
sum := a1 + a2 * b3 + a3 / (3 - 1) + a4
avg := sum / count
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 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

Last edited by mandeep.singh.bhatia; 05-13-2010 at 07:11 AM.
 
1 members found this post helpful.
Old 05-13-2010, 06:52 AM   #7
mandeep.singh.bhatia
LQ Newbie
 
Registered: Apr 2010
Location: Delhi, India
Distribution: openSuse
Posts: 6

Original Poster
Rep: Reputation: 0
Smile

Quote:
Originally Posted by ntubski View Post
GNU lightning has an RPN calculator example.
Thanks for the answer. I think this would be helpful.

Last edited by mandeep.singh.bhatia; 05-13-2010 at 07:02 AM. Reason: correcting previous statement
 
  


Reply

Tags
c++, compiling, postfix


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Postfix Compilation Error saif.sicsr Linux - Server 1 02-26-2009 07:40 AM
Postfix Compilation Error saif.sicsr Linux - Server 4 02-25-2009 07:23 PM
Postfix: postfix: fatal: chdir(/usr/libexec/postfix) Micro420 Ubuntu 2 07-13-2008 01:21 PM
Postfix compilation error Swift&Smart Linux - Software 1 12-28-2004 03:04 AM
postfix + mysql compilation santiagofs Fedora 2 05-03-2004 01:07 PM


All times are GMT -5. The time now is 04:44 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration