”;
Ordinary arithmetic expressions like 2*(3*4) are easier for human mind to parse but for an algorithm it would be pretty difficult to parse such an expression. To ease this difficulty, an arithmetic expression can be parsed by an algorithm using a two step approach.
-
Transform the provided arithmetic expression to postfix notation.
-
Evaluate the postfix notation.
Infix Notation
Normal arithmetic expression follows Infix Notation in which operator is in between the operands. For example A+B here A is first operand, B is second operand and + is the operator acting on the two operands.
Postfix Notation
Postfix notation varies from normal arithmetic expression or infix notation in a way that the operator follows the operands. For example, consider the following examples.
| Sr. No. | Infix Notation | Postfix Notation |
|---|---|---|
| 1 | A+B | AB+ |
| 2 | (A+B)*C | AB+C* |
| 3 | A*(B+C) | ABC+* |
| 4 | A/B+C/D | AB/CD/+ |
| 5 | (A+B)*(C+D) | AB+CD+* |
| 6 | ((A+B)*C)-D | AB+C*D- |
Infix to PostFix Conversion
Before looking into the way to translate Infix to postfix notation, we need to consider following basics of infix expression evaluation.
-
Evaluation of the infix expression starts from left to right.
-
Keep precedence in mind, for example * has higher precedence over +. For example
-
2+3*4 = 2+12.
-
2+3*4 = 14.
-
-
Override precedence using brackets, For example
-
(2+3)*4 = 5*4.
-
(2+3)*4= 20.
-
Now let us transform a simple infix expression A+B*C into a postfix expression manually.
| Sr.No | Character read | Infix Expressed parsed so far | Postfix expression developed so far | Remarks |
|---|---|---|---|---|
| 1 | A | A | A | |
| 2 | + | A+ | A | |
| 3 | B | A+B | AB | |
| 4 | * | A+B* | AB | + can not be copied as * has higher precedence. |
| 5 | C | A+B*C | ABC | |
| 6 | A+B*C | ABC* | copy * as two operands are there B and C | |
| 7 | A+B*C | ABC*+ | copy + as two operands are there BC and A |
Now let us transform the above infix expression A+B*C into a postfix expression using stack.
| Sr.No | Character read | Infix Expressed parsed so far | Postfix expression developed so far | Stack Contents | Remarks |
|---|---|---|---|---|---|
| 1 | A | A | A | ||
| 2 | + | A+ | A | + | push + operator in a stack. |
| 3 | B | A+B | AB | + | |
| 4 | * | A+B* | AB | +* | Precedence of operator * is higher than +. push * operator in the stack. Otherwise, + would pop up. |
| 5 | C | A+B*C | ABC | +* | |
| 6 | A+B*C | ABC* | + | No more operand, pop the * operator. | |
| 7 | A+B*C | ABC*+ | Pop the + operator. |
Now let us see another example, by transforming infix expression A*(B+C) into a postfix expression using stack.
| Sr.No | Character read | Infix Expressed parsed so far | Postfix expression developed so far | Stack Contents | Remarks |
|---|---|---|---|---|---|
| 1 | A | A | A | ||
| 2 | * | A* | A | * | push * operator in a stack. |
| 3 | ( | A*( | A | *( | push ( in the stack. |
| 4 | B | A*(B | AB | *( | |
| 5 | + | A*(B+ | AB | *(+ | push + in the stack. |
| 6 | C | A*(B+C | ABC | *(+ | |
| 7 | ) | A*(B+C) | ABC+ | *( | Pop the + operator. |
| 8 | A*(B+C) | ABC+ | * | Pop the ( operator. | |
| 9 | A*(B+C) | ABC+* | Pop the rest of the operator(s). |
Example
Now we”ll demonstrate the use of stack to convert infix expression to postfix expression and then evaluate the postfix expression.
#include<stdio.h>
#include<string.h>
//char stack
char stack[25];
int top=-1;
void push(char item) {
stack[++top]=item;
}
char pop() {
return stack[top--];
}
//returns precedence of operators
int precedence(char symbol) {
switch(symbol) {
case ''+'':
case ''-'':
return 2;
break;
case ''*'':
case ''/'':
return 3;
break;
case ''^'':
return 4;
break;
case ''('':
case '')'':
case ''#'':
return 1;
break;
}
}
//check whether the symbol is operator?
int isOperator(char symbol) {
switch(symbol){
case ''+'':
case ''-'':
case ''*'':
case ''/'':
case ''^'':
case ''('':
case '')'':
return 1;
break;
default:
return 0;
}
}
//converts infix expression to postfix
void convert(char infix[],char postfix[]){
int i,symbol,j=0;
stack[++top]=''#'';
for(i=0;i<strlen(infix);i++){
symbol=infix[i];
if(isOperator(symbol)==0){
postfix[j]=symbol;
j++;
} else {
if(symbol==''(''){
push(symbol);
} else {
if(symbol=='')''){
while(stack[top]!=''(''){
postfix[j]=pop();
j++;
}
pop();//pop out (.
} else {
if(precedence(symbol)>precedence(stack[top])) {
push(symbol);
} else {
while(precedence(symbol)<=precedence(stack[top])) {
postfix[j]=pop();
j++;
}
push(symbol);
}
}
}
}
}
while(stack[top]!=''#'') {
postfix[j]=pop();
j++;
}
postfix[j]='' '';//null terminate string.
}
//int stack
int stack_int[25];
int top_int=-1;
void push_int(int item) {
stack_int[++top_int]=item;
}
char pop_int() {
return stack_int[top_int--];
}
//evaluates postfix expression
int evaluate(char *postfix){
char ch;
int i=0,operand1,operand2;
while( (ch=postfix[i++]) != '' '') {
if(isdigit(ch)){
push_int(ch-''0''); // Push the operand
} else {
//Operator,pop two operands
operand2=pop_int();
operand1=pop_int();
switch(ch) {
case ''+'':
push_int(operand1+operand2);
break;
case ''-'':
push_int(operand1-operand2);
break;
case ''*'':
push_int(operand1*operand2);
break;
case ''/'':
push_int(operand1/operand2);
break;
}
}
}
return stack_int[top_int];
}
void main() {
char infix[25] = "1*(2+3)",postfix[25];
convert(infix,postfix);
printf("Infix expression is: %sn" , infix);
printf("Postfix expression is: %sn" , postfix);
printf("Evaluated expression is: %dn" , evaluate(postfix));
}
Output
If we compile and run the above program then it would produce following output −
Infix expression is: 1*(2+3) Postfix expression is: 123+* Result is: 5
”;