Firstly to understand the parsing expression in data structure we should know about the arithmetic notations.
There are three ways of writing arithmetic notations which are having same meaning:- 1. Infix Notation
INFIX NOTATION:- In infix notation operators comes in between the operands. It is very easily understandable in infix notation only for us human beings. But in computing devices it is very difficult and consumes space and time.
PREFIX NOTATION:- In prefix notation operator comes before the operands. It is also known as Polish Notation
e.g- +xy (this is equivalent to the x+y)
POSTFIX NOTATION:- In postfix notation operator comes after the operands. It is also known as Reversed Polish Notation.
e.g xy+ (this is also equivalent to x+y)
Below table will clearly make u understand the difference:-
(x + y) * z
* + x y z
x y + z *
x * (y + z)
* x + y z
x y z + *
(x + y) * (z + t)
* + x y + z t
x y + z t + *
To parse an infix notation we first convert the infix notation either into prefix notation or post fix notation after that it is computed.
Parsing of an arithmetic expression follows precedence and associativity.
Precedence:- When an operand is in between two unlike operators then the precedence of an operator decides which operator will be executed first.
For e.g expression is x + y * z then x + (y * z)
Addition operation has less precedence so multiplication operation will be executed first.
Associativity:- If the operators are having same precedence then associativity will describe the rule.
For e.g If expression is x + y - z then (x + y) - z