Infix expression to Binary Tree in C

Question

I have to parse an infix expression into a binary tree.

The expression is:

 (((x1 + 5.12) ∗ (x2 − 7.68))/x3) 

I don't really have a clue on how to interpret the expression. Does someone has a clue on how to process this?

Answer 1

Your task is not so hard, firstly you should acquaint yourself with notation types and then with expression parsing.

In general, to parse and evaluate an (infix) expression, you need to:

• read and tokenize it, i.e. classify each symbol as: operand, operation, etc.

• convert from infix to binary expression tree: this is usually done with algorithms such as Shunting yard algorithm.

• create a grammar that defines operation precedence and allows strict¹ order of expression evaluation.

Expressions written in infix notation are slightly more difficult to parse, that is why usually they are converted to more "machine friendly" versions, like (reverse) Polish notation which provides some advantages among which is the elimination of the need of parenthesses.

So, as you can see this is roughly the big picture and your task is a part of it. Here is a visualisation of binary expression tree for: 2 * 3 / ( 2 – 1 ) + 5 * ( 4 – 1 )

Here is more on the topic and an example implementation in C++.

---

^{1. In your case obeying the rules of Algebra.}