Calculating a Postfix Expression using Stack in C++

Today we will write a program to calculate the value of a postfix expression using stacks in C++.

What is Postfix Notation/Expression?

A postfix notation is where the operators are placed after the operands in the expression.

For example, the postfix notation for, 

A+B is AB+

A+B/C*(D-A)^F^H is ABCDA-FH^^*/+

2+4/5*(5-3)^5^4 is 24553-54^^*/+

How to calculate Postfix Expressions

  1. Start reading the expression from left to right.
  2. If the element is an operand then, push it in the stack.
  3. If the element is an operator, then pop two elements from the stack and use the operator on them.
  4. Push the result of the operation back into the stack after calculation.
  5. Keep repeating the above steps until the end of the expression is reached.
  6. The final result will be now left in the stack, display the same.

C++ code to calculate Postfix Expression using Stack

#include<iostream>
#include<stack>
#include<math.h>
using namespace std;

// The function calculate_Postfix returns the final answer of the expression after calculation
int calculate_Postfix(string  post_exp)
{
    stack <int> stack;
    int len = post_exp.length();

    // loop to iterate through the expression
    for (int i = 0; i < len; i++)
    {

        // if the character is an operand we push it in the stack

        // we have considered single digits only here
        if ( post_exp[i] >= '0' &&  post_exp[i] <= '9')
        {
            stack.push( post_exp[i] - '0');
        }

        // if the character is an operator we enter else block
        else
        {
            // we pop the top two elements from the stack and save them in two integers
            int a = stack.top();
            stack.pop();
            int b = stack.top();
            stack.pop();

            //performing the operation on the operands
            switch (post_exp[i])
            {
                case '+': // addition
                          stack.push(b + a);
                          break;
                case '-': // subtraction
                          stack.push(b - a);
                          break;
                case '*': // multiplication
                          stack.push(b * a);
                          break;
                case '/': // division
                          stack.push(b / a);
                          break;
                case '^': // exponent
                          stack.push(pow(b,a));
                          break;
            }
        }
    }

    //returning the calculated result
    return stack.top();
}

//main function/ driver function
int main()
{
    //we save the postfix expression to calculate in postfix_expression string
    string postfix_expression = "59+33^4*6/-";

    cout<<"The answer after calculating the postfix expression is : ";
    cout<<calculate_Postfix(postfix_expression);
    return 0;
}

Output

The answer after calculating the postfix expression is: -4

The working of the above code is as:

  1. Push ‘5’ and ‘9’ in the stack.
  2. Pop ‘5’ and ‘9’ from the stack, add them and then push ‘14’ in the stack.
  3. Push ‘3’ and ‘3’ in the stack.
  4. Pop ‘3’ and ‘3’ from the stack, and push ‘27’ (3^3) in the stack.
  5. Push ‘4’ in the stack.
  6. Pop ‘4’ and ‘27’ from the stack, multiply them and then push ‘108’ in the stack.
  7. Push ‘6’ in the stack.
  8. Pop ‘6’ and ‘108’ from the stack, divide 108 by 6 and then push ‘18’ in the stack.
  9. Pop ‘18’ and ‘14’ from the stack, subtract 18 from 14 and then push ‘-4’ in the stack.
  10. Print -4 as the final answer.

Note

  1. We have written the above code considering only the five basic operations, that are:
    • addition(+)
    • subtraction(-)
    • division(/)
    • multiplication(*)
    • exponent(^)
  2. We have included numbers from only 0 to 9 in our code. However, the scope of the program can be broadened over to more numbers too.

If you just want to convert infix to postfix without calculating the result, you can give a read here:

C++ program to convert infix to postfix

Leave a Reply

Your email address will not be published. Required fields are marked *