Postfix Evaluation

Write a Program to Evaluate a given Postfix Expression. A Postfix Expression is one in which every operator follows its operands.

For example the Postfix Expression for the Infix expression a*(b-c) is abc-*. Here a, b and c are  called operands, and * ,- are called operators each representing a mathematical operation.

Use a stack to evaluate postfix expressions. Follow the below Algorithm as discussed in class to evaluate an expression given in postfix notation.

  • Scan the Postfix Expression from left to right.

  • If you encounter an operand put it into the stack. If it is an operator, calculate the value of expression 

    with the operator and top two elements of the stack in correct order. Remove those top two elements 

    from stack and add their result into the stack.

  • Do the above step till you scanned all the elements of the postfix expression. You will be left with result 

    of the given postfix expression.

The above algorithm can also be used to check if a given postfix expression is valid or not.

For example the expressions abc-*d , a+bc- are invalid postfix expressions. Consider the expression containing division by 0 also as invalid.

Note that all operators are binary operators. ( operator ‘-’ can also be used as unary to represent -ve numbers, but in our postfix expression we only consider ‘-’ as binary operator)

You will be provided with a simple Stack Implementation with methods that are needed for the task. You can use your own implementation of stack if required.

INPUT:

first line of input contains the total number of elements(operators and operands) in the postfix expression.(N)

Postfix expression  will be in the second line, with elements separated from one another by a whitespace character.

OUTPUT:

Print the result of the Postfix Expression, If it is valid. Else print “INVALID” as output.

CONSTRAINTS:

All operands are non-negative integers.

Allowed Operators are {*(multiplication), /(division) , +(addition), -(subtraction) } . All are left- associative by nature.

1 ≤ Number of Operators + Number of Operands ≤ 25

0≤ Input Operands≤ 10000

Hints:

Use atoi(const char *) to convert an array of characters to integer.

#include<iostream>
#include <stdlib.h>
using namespace std;

class IntStack {
 private:
  int *Data;
  int MAX_SIZE;
  int top;
 public: 
  IntStack(){
   top=-1;
   MAX_SIZE = 50;
   Data = new int[MAX_SIZE];
  }
  IntStack(int size) {
   top=-1;
   MAX_SIZE=size;
   Data=new int[MAX_SIZE]; 
  } 
  int isfull() {
   if(top==(MAX_SIZE-1)) return 1;
   else return 0; 
  } 
  int isempty() {
   if(top==-1) return 1; 
   else return 0; 
  } 
  int topData() {
   if(isempty()){
    cerr<<"Error:Stack Underflow"<<endl;
    return -1;
   }
   else return Data[top];
  } 
  void push(int elem) {
   if (isfull()){
    cerr<<"Error:Stack is Full"<<endl;
   }
   else{
    Data[++top] = elem;
   }
  } 
  int pop() {
   if(isempty()){
    cerr<<"Error:Stack Underflow"<<endl;
    return -1;
   }
   else {
    return Data[top--];
   }
  }
};
IntStack s;
int p;
void print(int p)
{
 if(p==1)
     cout<<"INVALID";
    else
     cout<<s.topData();
}
void operation(char x)
{
 int a, b;
 if(s.isempty()==1)
  p=1;
 else {
  b=s.pop();
 if(s.isempty()==1)
  p=1;
 else {
  a=s.pop();
 if(x=='+')
  s.push(a+b);
 if(x=='-')
  s.push(a-b);
 if(x=='*')
  s.push(a*b);
 if(x=='/')
  {
   if( b==0 )
    p=1;
   else
   s.push(a/b); 
  }}}   
}
int main()
{
 char ch[50][50];
 int n,i,c;
 cin>>n;
 for(i=0;i<n;i++)
 {
     cin>>ch[i];
  if( ch[i][0]=='+' || ch[i][0]=='-' || ch[i][0]=='*' || ch[i][0]=='/' )
   operation(ch[i][0]);
  else
  {
   c=atoi(ch[i]);
        s.push(c);
     }
    }
    i=s.pop();
 if(s.isempty()==0)
     p=1;
    s.push(i); 
    print(p);
    return 0;
}