My own infix to prefix approach. What do you think?

[Les Bell]

(05-02-2014 12:57 AM)Matt Agajanian Wrote:  Actually I just thought I'd throw my idea out to you folks to see if I was on the right track of a concept that I drew up. I'm not necessarily looking to embark on a full-scale project. I was just pondering the concept for a practical way as a manual exercise to parse infix expressions into postfix statements.

Ah, OK. The general idea is that a parser constructs a tree for the expression. For your example of "(2+3)x(4+5)", the tree starts at the top with "x" and it has two children. The left child is "+" and it has two children: "2" on the left and "3" on the right. Similarly, the right child is also "+" and it has two children: "4" and "5". Something like (please excuse bad ASCII art!):

x
+ +
2 3 4 5

Having constructed the tree, you walk around it, starting with the root node; for each node you process the left child and then the right child, respectively, along with the content of the node itself.

If your processing is to output the content of each node before processing the children, then the result will be to print the prefix version of the expression (and this is the default behaviour of ANTLR v3, as I mentioned, although I notice that ANTLR v4 spits out a bit more diagnostic information, making it harder to see).

If your processing is to process the children and then output the content of the node, then it will output the postfix version of the expression.

And, of course, if your processing for each node is to perform the specified operation on the two children and return the result, then it will evaluate the expression, and you've just built an interpreter.

The grammar I posted builds a parser that does all that, plus unary minus. The upper-case rules also build a lexer which breaks text up into the right kinds of tokens. ID and FLOAT allow recognition of variable names and floating point numbers, while WS and NEWLINE let it deal with white space between the tokens. As far as I can see, it all works, and would only need (according to the ANTLR 4 book) a few (~8) lines of code to make it pretty-print infix or postfix output, or do the evaluation. I might try that this coming weekend, if I get time.

From there, it's easy enough to add things like x ^ y, variable assignment, etc. Everything falls into the tree pattern, although sometimes a node has just one child (e.g. unary minus) and sometimes three or more.

I figured you were just exploring the ideas here, but it would actually be practical to automatically translate programs for some of the infix calculators into RPN or RPL. Anyway, have fun - parsing and language translation has some of the most elegant ideas in computer science.