Program to Evaluate Postfix Expression - LeetCode

Given, an arithmetic expression. We need to Evaluate Postfix Expression, also known as Reverse Polish Notation. Operators include /,*,+,- and we will always return a finite result, there won’t be any divide with zero operations.

Example

Input: 234*+82/-
Evaluation:
3*4  = 12
2+12 = 14
8/2  =  4
14-4 = 10
Output: 10

What is a Postfix Expression

A Postfix Expression or a Reverse Polish Notation is a type of notation/order in which operators follow operands [Wikipedia]. For example,

2+3 = 23+
(5-3)/2 =253-/

Solution Approach

We chose the Stack data structure for this problem as the push and pop operations suit well to deal with the operands. First, we start traversing through each character of the string, initially we push all numbers as they come into the stack. Whenever we encounter an operand, then we pop out two numbers (operands) and perform the calculation based on the operand(add, subtract, multiply, or divide).

It is possible to perform other mathematical operations too but, here we use only(+,-,*,/)

Practice on LeetCode

Difficulty: Medium

Problem: Evaluate Reverse Polish Notation

Code to Evaluate Postfix Expression

#include <bits/stdc++.h>
using namespace std;

stack<int>s;

int isoperand(char x)
{
    if (x == '+' || x == '-' || x == '*' || x == '/')
        return 0;
    else
        return 1;
}

//Evaluate Postfix Expression
int Evaluate(string postfix)
{
    int i = 0;
    int x1, x2, r;

    for (i = 0; postfix[i] != '\0'; i++)
    {
        if (isoperand(postfix[i]))
            s.push(postfix[i] - '0');

        else
        {
            x2 = s.top();
            s.pop();
            x1 = s.top();
            s.pop();
            /*Output Explanation*/
            cout<<x1<<" "<<postfix[i]<<" "<<x2<<endl;
            switch (postfix[i])
            {
            case '+':
                r = x1 + x2;
                break;
            case '-':
                r = x1 - x2;
                break;
            case '*':
                r = x1 * x2;
                break;
            case '/':
                r = x1 / x2;
                break;
            }
           s.push(r);
        }
    }
    return s.top();
}

int main()
{
    string postfix = "234*+82/-";
    cout <<" On Evaluating we get : \n" << Evaluate(postfix);
    return 0;
}

Output

Conclusion

This post [Evaluate Reverse Polish Notation] is a part of my #30DaysChallenge to write a blog post every day on what I learn daily, Cheers~ Abhiram Reddy.

Program to Evaluate Postfix Expression – LeetCode