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:


or same expression in postfix notation:


into a list of

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

Which corresponds to a tree: Binary tree of parsed expression

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'

Parsed expression binary tree

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.

  • 1
    $\begingroup$ Are you familiar with YACC or bison? This is precisely the problem that they solve. $\endgroup$ Nov 15 at 11:01
  • $\begingroup$ 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.) $\endgroup$
    – rici
    Nov 15 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.