# Parse algebraic expression into a list of operations

Given algebraic expression in a string, I want to split it into a list of operations for building a parallel binary tree. For example, I'm trying to convert expression such as:

(a+b+c+d)/(e*f)

or same expression in postfix notation:

ab+c+d+ef*/

into a list of

  Expr1 = 'a+b'
Expr2 = 'c+d'
Expr3 = 'e*f'
Expr4 = 'Expr1+Expr2'
Expr5 = 'Expr4/Expr3'


Which corresponds to a tree:

However,parsing expression iteratively I've only managed to turn it into a list like this:

  Expr1 = 'a+b'
Expr2 = 'Expr1+c'
Expr3 = 'Expr2+d'
Expr4 = 'e*f'
Expr5 = 'Expr3/Expr4'


Is there any algorithm to parse expression into a list of operations, which can be computed as parallel as it's possible? Any help will be appreciated.

• Are you familiar with YACC or bison? This is precisely the problem that they solve. Nov 15 at 11:01
• I think you need to be clearer about what you mean by "parallel" in this context. The final parse tree you include is the correct parse tree for the algebraic expression, although if you exploit the associativity of addition, you can come up with flatter trees, such as the one at the top. I think it will be tricky to do that tree rearrangement during the initial parse, as opposed to writing a post-parse tree-write, since it is clearly dependent on identifying a chain of associative operators. (It won't work if you replace + with -, for example.)
– rici
Nov 15 at 21:46