Evaluation of Arithmetic Expression
An important application of stack is the compilation of arithmetic stack expressions in the programming languages.
The compiler must be able to translate the expression which is written in the usual notation known as infix notation to form a reverse polish notation.
compiler accomplish this task of notation conversion i.e infix to postfix with help of stack.
There are mainly three types of notations as follows:
1. Infix notation
2. postfix notation
3. prefix notation
Before discuss above three notation, you have to know about two main terms:
a) operator: to do any arithmetic operation or else i.e +,-,* etc.
b) operand: operand can be any number or alphabet i.e a , b or 8 ,7 etc.
Remember : operator is placed between operands. for example : a + b * c
Precedence and associativity table:
Priority | Operator | Precedence | Associativity |
---|---|---|---|
1 | Exponentiation ^ | Highest | Right Associative |
2 | Multiplication ( ∗ ) & Division ( / ) | Second Highest | Left Associative |
3 | Addition ( + ) & Subtraction ( − ) | Lowest | Left Associative |
In case of bracket() used the it will be top highest.
.
Now , move to the notations:
- Infix Notation
In infix notation, operators are in between operands
for example: a + b
where a and b are two operands and operator + is placed between operands.
2. Postfix notation
In postfix notation, operators placed after operands
for example: a b +
3. Prefix notation
In prefix notation, operators placed before operands
for example : + a b
INFIX TO POSTFIX CONVERSION
There are two operations performed:
- pop: delete from stack
- push: add into stack
ALGORITHM INFIX TO POSTFIX CONVERSION
- Create a stack
- for each character ‘s’ in the input stream {
- if (s is an operand)
output s - else if (s is a right parentheses){
POP and output tokens until a left parentheses is popped(but do not output)
} - else {
POP and output tokens until one of lower priority than s is encountered or a left parentheses is encountered
or the stack is empty
PUSH s
}
- if (s is an operand)
- POP and output tokens until the stack is empty.
EXAMPLE:
For better understanding, let us trace out an example 1 * 2 – (3 + 4) + 5
INPUT CHARACTER | OPERATION ON STACK | STACK | POSTFIX EXPRESSION |
A | Empty | 1 | |
* | Push | * | 1 |
B | * | 12 | |
– | Check and Push | – | 12 * |
( | Push | – ( | 12 * |
C | – ( | 12 * 3 | |
+ | Check and Push | – ( + | 12 * 3 |
D | – ( + | 12 * 34 | |
) | Pop and append to postfix till ‘(‘ | – | 12 * 34 + |
+ | Check and push | + | 12 * 34 + – |
E | + | 12 * 34 + – 5 | |
End of Input | Pop till Empty | Empty | 12 * 34 + – 5 + |
we can also alphabets instead of numbers. suppose A=1,B=2,C=3,D=4 and E=5 then final POSTFIX Expression :- A B * C D + – E +
Algorithm To Convert Postfix Expression into Prefix Notation
- Scan the Postfix Expression from Left To Right.
- If the character is an Operand, then Push it on to the Stack.
- If the character is an Operator, then Pop Operand 1 and Operand 2 and concatenate them and Push the result on the Stack.
- Repeat the above steps until the Postfix Expression is scanned completely.
- To get the Prefix Expression, Pop the remaining elements of the Stack.
For example: