Stacks can be used to implement algorithms involving Infix, postfix and prefix expressions. So let us learn about them:-
INFIX:-
An infix expression is a single letter, or an operator, proceeded by one infix string and followed by another infix string.
A
A + B
(A + B) + (C – D)
PREFIX:-
A prefix expression is a single letter, or an operator, followed by two prefix strings. Every prefix string longer than a single variable contains an operator, first operand and second operand
A
+ A B
+ + A B – C D
POSTFIX:-
A postfix expression (also called Reverse Polish Notation) is a single letter or an operator, preceded by two postfix strings. Every postfix string longer than a single variable contains first and second operands followed by an operator.
A
A B +
A B + C D –
Prefix and postfix notations are methods of writing mathematical expressions without parenthesis. Time to evaluate a postfix and prefix expression is O(n), where n is the number of elements in the array.
| INFIX | PREFIX | POSTFIX |
| A + B | + A B | A B + |
| A + B – C | – + A B C | A B + C – |
| (A + B) * C – D | – * + A B C D | A B + C * D – |
To study further, we must also know the operator precedence and their associativity:-
| TOKEN | OPERATOR | PRECEDENCE | ASSOCIATIVITY |
| ( ) [ ] – . |
function call array element struct or union member |
17 | left-to-right |
| — ++ | increment, decrement | 16 | left-to-right |
| ! ~ – + & * sizeof |
logical NOT one’s complement unary minus or plus address or indirection size (in bytes) |
15 | right-to-left |
| (type) | type cast | 14 | right-to-left |
| * / % | multiplicative | 13 | left-to-right |
| + – | binary add or subtract | 12 | left-to-right |
| << >> | shift | 11 | left-to-right |
| > >= < <= |
relational | 10 | left-to-right |
| == != | equality | 9 | left-to-right |
| & | bitwise AND | 8 | left-to-right |
| ^ | bitwise XOR | 7 | left-to-right |
| | | bitwise OR | 6 | left-to-right |
| && | logical AND | 5 | left-to-right |
| || | logical OR | 4 | left-to-right |
| ? : | conditional | 3 | right-to-left |
| = += /= *= %= &= ^= |
assignment | 2 | right-to-left |
| , | comma | 1 | left-to-right |