How do I parenthesize an expression?

Question

I have an idea for a simple program to make that will help me with operator precedence in languages like C. The most difficult part of this is parenthesizing the expression. For example, I want this:

*a.x++ = *b.x++

Converted to this:

((*(((a).(x))++)) = (*(((b).(x))++)))

Which I did manually in these steps:

           *a.x++ = *b.x++
       *(a).(x)++ = *(b).(x)++
     *((a).(x))++ = *((b).(x))++
   *(((a).(x))++) = *(((b).(x))++)
 (*(((a).(x))++)) = (*(((b).(x))++))
((*(((a).(x))++)) = (*(((b).(x))++)))

What is the best way to accomplish this? Is there already a solution out there that I could use? I'd prefer to do this in either PHP, C, C++, Python, or Ruby.

(This isn't the whole idea of my program, it is only the first step.)

Answer 1

How about converting to postfix and evaluating. Can you try if the following approach works. Lets take *a.x++

Operator    Precedence  Arguments Needed
.           3               2
++          2               1
*           1               1

So now convert the expression to postfix notation. This should give you

a x . ++ *

Now evaluation of postfix is as simple as pushing things into a stack, when you hit an operator, pop the top n (as needed by operator) elements and pass them as arguments, store results back onto the stack. In your case, instead of evaluating, you'd return a textual representation of the operation

        Stack
Read a      a
Read x      x
Read .      (a.x)
Read ++     ((a.x)++)
Read *      (*((a.x)++))

if it helps, you may want to look at:
http://www.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/
Bart de smet's DynCalc series of posts
My attempt at TDDing a similar solution

Answer 2

As a simple example:

Exp = Term | Exp, AddOp, Term 
Term = Factor | Term, MulOp, Factor
Factor = Number | Ident | PreOp, Factor | (, Exp, ) | Factor, PostOp

You can uses the grammar to write the translations:

Exp    = Term                    -> Term
       | Exp, AddOp, Term        -> (, Exp, AddOp, Term, )
Term   = Factor                  -> Factor
       | Term, MulOp, Factor     -> (, Term, MulOp, Factor, )
Factor = Number                  -> Number
       | Ident                   -> Ident
       | PreOp, Factor           -> (, PreOp, Factor, )
       | (, Exp, )               -> (, Exp, )
       | Factor, PostOp          -> (, Factor, PostOp, )

In which case:

a-- + b * (a+b) 

Translates to:

((a--) + (b * ((a+b))))

Answer 3

You can find "cparen" in the archives of the old net.sources newsgroup.

If you search (Google) for 'cparen', you get too much noise, but if you search for net.sources and 'cparen.c' that narrows the search enough to be useful.

Here is one website:

http://www.megalextoria.com/usenet-archive/news005f3/b14/net/sources/00000360.html

It is not a shell archive, as I would have expected. It looks like a pure ASCII text tar file. There are few enough files that you could just unpack it by hand.

Answer 4

You could create a binary expression tree from the operators.

I believe there are several algorithms available online to create such tree already.

One simple way I could think of, is by sorting the operator by precedence, and then split the string into 2 parts by the operator with the lowest precedence first, then continue recursively splitting the other 2 parts down over and over and then eventually, you'll have the expression in binary tree form.

And then when you have the expression in binary tree form, you can then "parenthesize" up from the tree's leaves up to the root.

And of course, you could compile a full-fledged parser via yacc/bison.