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 ();
};
Postfix Notation
In this notation, operators are written after there operands. eg:
AB+
Postfix Evaluation
To evaluate mathematical expression, postfix notation is generally used. Here we are going to see the algorithm to evaluate any Postfix mathematical expression.
Algorithm for Postfix Evaluation
- Process Postfix expression one character at a time.
- Define an empty Stack.
- For every character ‘a’ in Postfix expression.
- if character is an operand then PUSH it to the Stack.
- if character is an operator then
- POP two items from the Stack
- Perform the mathematical operation on two popped elements.
- PUSH the result into Stack.
- At the End, Final result will be stored in the Stack which will be the Result of the Postfix evaluation.
Let’s look into an example to make it more clear.
In below example we will apply above algorithm on,
Infix expression – (1+2)*3+(4+5)
Postfix expression – 12+3*45++
| Input Character | Stack Operation | Stack content |
|---|---|---|
| 1 | PUSH | 1 |
| 2 | PUSH | 1 2 |
| + | POP top 2 elements and perform operation and PUSH result | 3 |
| 3 | PUSH | 3 3 |
| * | POP top 2 elements and perform operation and PUSH result | 9 |
| 4 | PUSH | 9 4 |
| 5 | PUSH | 9 4 5 |
| + | POP top 2 elements and perform operation and PUSH result | 9 9 |
| + | POP top 2 elements and perform operation and PUSH result | 18 |
| All Done | POP the only element which is the final Result = 18 |
Few of the functions used below are explained in Generic Stack Implementation and Infix to Postfix conversion. Refer those before going ahead.
Let’s look into the sample code.
/* This function will evaluate the Postfix expression */
void evaluate (char* postfix)
{
StackGeneric<int> oper (100);
char* temp = postfix;
while (*temp != '\0')
{
if (*temp >= '0' && *temp <= '9')
{
oper.push (int (*temp - 48));
}
else
{
int x = oper.pop ();
int y = oper.pop ();
switch (*temp)
{
case '+':
oper.push(x + y);
break;
case '-':
oper.push(y - x);
break;
case '*':
oper.push(x * y);
break;
case '/':
oper.push(y / x);
break;
}
}
temp++;
}
cout << "Final value: " << oper.pop () << endl;
}
/* 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;
}
/* This function will convert Infix to Postfix expression */
void evaluate_postfix_expression (char* exp)
{
StackGeneric<char> oper (100);
char* temp = exp;
char postfix[100] = "";
int postfix_index = 0;
while (*temp != '\0')
{
if (*temp >= '0' && *temp <= '9')
{
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;
evaluate (postfix);
}
Let’s define a main function to use above methods.
int main ()
{
char expr[100] = "";
cout << "Enter the Expression" << endl;
cin >> expr ;
evaluate_postfix_expression (expr);
}
Let’s analyze the output of this main function.
Enter the Expression
(1+2)*3+(4+5)
Infix expression: (1+2)*3+(4+5) Postfix expression: 12+3*45++
Final value: 18
Enter the Expression
(1*2)+(8/4)-(3*4)
Infix expression: (1*2)+(8/4)-(3*4) Postfix expression: 12*84/+34*-
Final value: -8
Enter the Expression
1+2*3+(8/4)
Infix expression: 1+2*3+(8/4) Postfix expression: 123*84/++
Final value: 9
