How to represent a mathematical expression using the parse tree

The graphical representation of a symbol is called a parse tree. TerminalTerminal symbols are the basic symbols of the language defined by a formal grammar. or non-terminalNonterminal symbols are replaced by groups of terminal symbols according to the production rules. symbols are acceptable in the parse tree. The start symbol, which is also the root, derives the string during parsing. The parse tree respects the precedence of operators. The first sub-tree to be explored is the deepest, so the parent node's operator has a lower priority than the sub-tree operator.

Note: The parse trees are constructed from bottom up approach, not top down.

The problem

The mathematical expressions we read are in-order form. Due to the tree's hierarchy, we can better comprehend the evaluation order for the entire expression. We must assess the operators in the subtrees before assessing the top-level multiplication.

Once we have evaluated the expressions in the children, we can easily replace a complete subtree with one node using the hierarchical structure of trees. The parse tree for the simple equation $A+(B*C)$ is:

Working

It is necessary to separate the expression string into tokens to construct a parse tree. The four tokensThe smallest unit of a programming language that has a meaning is known as token. to remember are left and right parentheses, operators, and operands. Every time we read an expression with a left parenthesis, we should create a new tree to represent that new expression. When we read the right parenthesis, on the other hand, it means we have completed an expression. Leaf nodes and children of operators are operands. Every operator has a left and right child.

Rules

The following are the four rules that can be derived from the data presented above:

1. Add a new node as the current node's left child and descend to the new node's left child if the current token is a "(".

2. For example, if the token currently being used is one of the operators listed in the list [+,-,/,*], then set the root value of this node to that operator as its root value. Insert a new node in the right child of the current node and descend to this node.

3. If the current token is an operand, set its value to the current node and make its parent current node.

4. Go to the parent node of the current node if the token is a")".

Let's see an example of the rules delineated above. We use the expression $(1+(2×3))$ and parse this expression into the ensuing array of character tokens [ ' ’' ‘'’' ‘'’' '’' ‘'’' ‘'’' ‘'’' '’' ''].

This example shows us that we must keep track of the parent and current node. So for the implementation of this example, we can use a stack data structure. Whenever we move to a child of the current node, we first push the current node on the stack. Similarly, when we return to the parent of the current node, we pop the parent from the stack.

Applications

The few applications of parse trees are as follows:

• It reminisces the syntax of the input language that aids in syntax analysis.

• It utilizes an in-memory representation of the input with a grammar-conforming structure.

• Parse trees, rather than semantic actions, can allow you to make multiple passes over the input without re-praising it.