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

Parsing is a huge topic. Since you just want to use it to solve a specific problem, try not to get immersed in all these specific parsing algorithms that people are suggesting. Rather, there are numerous parser generators, such as antler or bison which, given an appropriate grammar, will parse text and allow you to perform programmatic operations on the components -- such as put parentheses around them. Some of these systems come with grammars for C, or have such grammars available.

antlr can generate parsers in any of the languages you mentioned; see http://www.antlr.org/

Answer 2

Just pick up a parser for your selected language, for instance C parser, parse the expression/source code and print the AST back in the way you want.

test.c:

void main(void){
    int c = 2;
}

terminal:

$ python
>>> import pycparser
>>> test = pycparser.parse_file('test.c')
>>> test.show()
FileAST: 
  FuncDef: 
    Decl: main, [], []
      FuncDecl: 
        ParamList: 
          Typename: []
            TypeDecl: None, []
              IdentifierType: ['void']
        TypeDecl: main, []
          IdentifierType: ['void']
    Compound: 
      Decl: c, [], []
        TypeDecl: c, []
          IdentifierType: ['int']
        Constant: int, 2
>>> for node in test.ext:
...     print node
...
<pycparser.c_ast.FuncDef object at 0x7fe1436db750>
>>>

Answer 3

I wrote a program in Python to parenthesize an expression string.

def pref(op):
    print "called with op", op
    ret = -1
    if op == '+':
        print "matched +"
        ret = 1
    if op == '-':
        print "matched -"
        ret = 2
    if op == '*':
        print "matched *"
        ret = 3
    if op == '/':
        print "matched /"
        ret = 4

    return ret

def evaluate(expr, operand_stack, operator_stack):
    print "**In evaluate**"
    print operator_stack
    print operand_stack

    expr1 = operand_stack.pop()
    expr2 = operand_stack.pop()
    op    = operator_stack.pop()

    # Parenthesize the expression
    expr = "(" + expr2 + op + expr1 + ")"
    print "expr1", expr1
    print "expr2", expr2
    print "expr", expr

    # Push the result back on the stack
    operand_stack.append(expr)

    print operator_stack
    print operand_stack
    print "**Out evaluate**"
    return expr

def looper(str, expr, operator_stack, operand_stack):
    l = 0
    cnt = len(str)

    # Loop over the input string
    while  l < cnt:
        if str[l] in ('+', '-', '*', '/'):
            print "operator found: op, index", str[l], l
            print operator_stack, len(operator_stack)

            x = len(operator_stack) - 1
            if x > 0:
                print "Comparing:", operator_stack[x], str[l]

                # If op on stack has higher preference than the op in question
                if (pref(operator_stack[x]) > pref(str[l])):
                    expr = evaluate(expr, operand_stack, operator_stack)
            operator_stack.append(str[l])
        else:
            # Add the operand to operand stack
            operand_stack.append(str[l])
        l += 1

    print operator_stack
    print operand_stack

    print "Take care of last elements"
    op_cnt = len(operator_stack)
    while op_cnt:
        expr = evaluate(expr, operand_stack, operator_stack)
        op_cnt -= 1

    print operator_stack
    print operand_stack

if __name__ == '__main__':
    str = "a+c*d-e/w*x+a-s"
    cnt = len(str)

    operand_stack  = []
    operator_stack  = []
    expr = ""
    looper(str, expr, operator_stack, operand_stack)

    print "Output=>", operand_stack[0]

Answer 4

You're going to need a parser of some sort that understands operator precendence. The usual version for C is Lexx/Yacc or flex/bison, and the easiest way to do it is construct a parse tree. Once you've done that, just walk the parse tree in the "preorder" order and emit parens as you enter and leave a node.

Answer 5

There is a very old (1980's) open source program to do exactly this. It's called "cparen", but I'm damned if I can find it on the net. Only enthusiastic mentions of it, e.g. https://groups.google.com/group/comp.lang.c/tree/browse_frm/month/1990-03/1583b4728a6d94db http://www.language-c.info/re-should-i-capitalize-const-identifiers

If you have more luck than me in finding it, do write

Answer 6

The most reliable way will be to parse the expression (taking into account precedence rules, of course) and then process the resulting AST (Abstract Syntax Tree) in a top-down manner, adding parenthesis as you move along