by Stack is a data structure used for storing collection of data where order in which data is arriving is important. In Stack, insertion and deletion both happened from the same end which is known as “Top”.
The data which is arrived last will be deleted first in Stack. This data ordering is called as Last in First out or LIFO. Before going ahead have a look into Stack basics and Generic Stack Implementation.
Let’s have a look on basic class definition for Generic Stack.
template <typename T>
class StackGeneric
{
private:
int size;
int top;
T* elements;
public:
StackGeneric (int sz);
~StackGeneric ();
bool push (T value);
int pop ();
bool isEmpty ();
int maxSize ();
int entries ();
};
Infix Notation
This is the most common notation which we use generally in out writings. In this notation, mathematical operators (such as +, -, * etc.) are written in-between there operands. eg:
A+B,
(A*B)+C
Postfix Notation
In this notation, operators are written after there operands. eg:
AB+
AB*C+
For more information related to Expression notation check Prefix, Postfix and Infix Expression notations.
Infix to Postfix conversion
Here we are going to define the algorithm to convert an Infix expression notation to Postfix expression notation.
Algorithm to convert Infix to Postfix
- Define a Stack
- For each character ‘a’ in Infix Expression
- if character is operands then put it in output expression
- if character is an right parenthesis ‘)’, then pop all the items from stack and put it in output expression till left parenthesis ‘(‘ is encountered
- if character is an operator ‘b’ or left parenthesis then
- pop all tokens from the stack and put it into the output expression until one of the higher priority operator or left parenthesis is encountered.
- push b into the stack.
Let’s look into an example to make it more clear.
In below example we will apply above algorithm to convert infix expression “(A+B)*C+(D+E)” into Postfix expression.
| Input Character | Stack Operation | Stack content | Postfix Expression |
|---|---|---|---|
| ( | PUSH | ( | |
| A | ( | A | |
| + | PUSH | ( + | A |
| B | ( + | AB | |
| ) | POP till “(” is encountered | AB+ | |
| * | PUSH | * | AB+ |
| C | * | AB+C | |
| + | POP till higher priority operator is encountered and then PUSH this | + | AB+C* |
| ( | PUSH | + ( | AB+C* |
| D | + ( | AB+C*D | |
| + | PUSH | + ( + | AB+C*D |
| E | + ( + | AB+C*DE | |
| ) | POP till “(” is encountered | + | AB+C*DE+ |
| All Done | POP all elements | AB+C*DE++ |
Few of the functions used below are explained in Generic Stack Implementation. Refer those before going ahead.
Let’s look into the sample code.
/* This function will return the operator precedence values */
int return_operator_precedence (char* oper)
{
if (*oper == '^')
return 3;
else if (*oper == '*' || *oper == '/')
return 2;
else if (*oper == '+' || *oper == '-')
return 1;
else
return -1;
}
void convert_infix_to_postfix (char* exp)
{
StackGeneric<char> oper (100);
char* temp = exp;
char postfix[100] = "";
int postfix_index = 0;
while (*temp != '\0')
{
if ((*temp >= 'a' && *temp <= 'z') || (*temp >= 'A' && *temp <= 'Z'))
{
postfix[postfix_index++] = *temp;
}
else if (*temp == ')')
{
char c = oper.pop ();
while (c != '(')
{
postfix[postfix_index++] = c;
c = oper.pop ();
}
}
else if (*temp == '(')
{
oper.push (*temp);
}
else
{
if (oper.isEmpty ())
{
oper.push (*temp);
}
else if (return_operator_precedence (temp) <= return_operator_precedence (oper.atTop ()))
{
postfix[postfix_index++] = oper.pop ();
oper.push (*temp);
}
else
{
oper.push (*temp);
}
}
temp++;
}
while (!oper.isEmpty ())
{
postfix[postfix_index++] = oper.pop ();
}
postfix[postfix_index++] = '\0';
cout << "Infix expression: " << exp << " Postfix expression: " << postfix << endl;
}
Let’s define a main function to use above methods.
int main ()
{
char expr[100] = "";
cout << "Enter the Expression" << endl;
cin >> expr ;
convert_infix_to_postfix (expr);
}
Let’s analyze the output of this main function.
Enter the Expression
(A+B)*C+(D+E)
Infix expression: (A+B)*C+(D+E) Postfix expression: AB+C*DE++
Enter the Expression
(A*B)+(C/D)-(E*F)
Infix expression: (A*B)+(C/D)-(E*F) Postfix expression: AB*CD/+EF*-
Enter the Expression
A+B*C/(E-F)
Infix expression: A+B*C/(E-F) Postfix expression: ABC*EF-/+
