Expression Parsing (Infix, Prefix and Postfix)
- Infix Notation
- Prefix (Polish) Notation
- Postfix (Reverse-Polish) Notation
Expression Parsing
There are 3 types of notation we read in the first paragraph. We will read each notation in details as well as how to convert
1. Infix To Postfix
2. Infix To Prefix
3. Prefix To Infix
4. Tree From Postfix
but before that we will know what is Precedence and Associativity.
Precedence
Precedence means giving the priority and more importance than else. Suppose an operand is in between two separate operators, which operator must take the operand first, is determined by the operator’s precedence over others. For example –
Since the operation of multiplication takes precedence over the addition, b* c is evaluated first. Later, an operator precedence table will be given.
Associativity
Associativity defines the concept where operators occur in an expression with the same precedence. For example, in expression a + b − c, both + and – have the same precedence, then the associativity of such operators determines which part of the expression will be evaluated first. Both + and − are left associative here, so the expression will be calculated as (a+b) −c.
| Sr.No | Operator | Precedence | Associativity |
|---|---|---|---|
| 1 | Exponentiation ^ | Highest | Right Associative |
| 2 | Multiplication ( * ) and Division ( / ) | Second Highest | Left Associative |
| 3 | Addition ( + ) and Subtraction ( – ) | Lowest | Left Associative |
What is an infix, prefix, and postfix expression?
Prefix : – (Pre = के पहले) Meaning when the operation in an expression comes before the operand it is called prefix.
General Syntex =
example : +AC
Infix :- (In = बीच में ) When the operation in an expression is between two operands, it is called infix.
General Syntex =
example : A + C
Postfix :- (Post = बाद में ) When operation comes after operand in an expression, it is called postfix.
General Syntex =
example : AC+
Infix To Postfix Conversion Using STACK
What are the rules of infix to postfix conversion?
Following the rules, we have to follow :
- Print operands as they arrive
- An incoming symbol is ‘(‘, then push it onto the stack
- If the received symbol is ‘) ‘ the stack will pop up and print the operators before left parenthesis is found
- The upcoming symbol has higher precedence then the top of the stack, push it on the stack.
- If the next symbol has lower precedence than the top of the stack, pop, and print the top. Then test the incoming operator against the new top of the stack.
- If the arriving operator has equal precedence with top of the stack, use associativity rule(a,b)
- pop and print all
Note: (associativity rule)
(a) Associativity L to R then pop and print the top of the stack and then push the incoming operator.
(b) if associativity R to L then push the incoming operator.
Let’s take an example of Infix to Postfix for better understand
Infix Expression: A + B * C / D – E
| S.No | Scanned | STACK | Postfix Expression | Description |
|---|---|---|---|---|
| 1 | A | EMPTY | A | START |
| 2 | + | + | A | |
| 3 | B | + | AB | |
| 4 | * | + * | AB | RULE NO 5, BECAUSE ‘*’ HAS HIGHER PRECEDENCE |
| 5 | C | + * | ABC | |
| 6 | / | + / | ABC* | FIRST APPLY RULE NO 7, AND THAN 5 |
| 7 | D | +/ | ABC*D | |
| 8 | – | – | ABC*D/+ | APPLY RULE NO. 6 |
| 9 | E | – | ABC*D/+E | |
| 10 | ABC*D/+E- | APPLY RUL NO 8 |
Resultant Postfix Expression: ABC*D/+E –
Infix To Prefix Using Stack
For infix to prefix, we use same rules but must reverse the expression. For example A + B / C, here we reverse this expression like C / B + A then applies all those rules which are applicable on infix to postfix.
