Evaluation of Postfix Expression using C++ STL

By Sai Koushik Kalakota

In this blog, I am going to explain how to evaluate postfix expression using the C++ standard template library.

Standard Template Library:

The Standard Template Library (STL) is a set of C++ template classes which consists of readily available and implemented of data structures and

algorithms like stacks, queues, lists, dequeues.

 

Postfix:

Postfix is a collection of operators and operands for writing arithmetic expressions where the operators appear in the expression after the operands.

Example: 12*3+

 

Algorithm:

1. Create an empty stack.

2. traverse through every symbol of given postfix expression.

     1. if the symbol is an operand push it to a stack.

     2. else if the symbol is an operator then pop the top two elements in the stack and perform the operation with the operator and push the result to the

stack.

3. after traversing through the whole expression final result will be left in the stack.

 

C++ Code for Postfix Evaluation:

#include
#include<bits/stdc++.h>

using namespace std;

int main()
{
    stacks;

    int top1,top2,result;

    string postfix =  "132*+1-";

    for(int i=0;i<postfix.length();i++)
    {
        if(isdigit(postfix[i]))
        {
            s.push((int)(postfix[i]-'0'));
        }

        else
        {
            top1 = s.top();
            s.pop();
            top2 = s.top();
            s.pop();

            if(postfix[i]=='+')
            {
                result = top2+top1;
                s.push(result);

            }

            if(postfix[i]=='-')
            {
                result = top2-top1;
                s.push(result);
            }

            if(postfix[i]=='*')
            {
                result = top2*top1;
                s.push(result);
            }

            if(postfix[i]=='/')
            {
                result = top2/top1;
                s.push(result);
            }
        }
        
    }

    cout<<"Postfix evaluation: "<<s.top();
}

The output of the following code is Postfix evaluation: 6

The time complexity of the given code is O(n) where n is the length of given postfix expression.