Postfix Expression Evaluation by Stack














































Postfix Expression Evaluation by Stack



Introduction :

  • The Postfix notation is widely used to represent algebraic expressions. 
  • Advantage of the expressions written in postfix form is that they are evaluated faster compared to infix notation as parenthesis are not required in postfix. 
  • In this article, evaluation of postfix expressions is discussed.


Algorithm :

  • Create a stack to store operands and numbers provided in the postfix expression.
  • Scan the given expression and do following for every scanned element :
    • If the element is a number, push it into the stack
    • If the element is a operator, pop front two elements from the stack. Evaluate expression with scanned operator and push the result back to the stack.
  •  When the expression is ended, the number in the stack is the final answer, so return it to the calling function.

C++ Code :


#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<math.h>
#include<stdlib.h>
#define MAX 100
using namespace std;
struct postfix
{
int stack[MAX];
int top,n;
char *s;
}p;
void init_post()
{
p.top=-1;
}
void init_exp(char *str)
{
p.s=str;
}
void push(int number)
{
p.top++;
p.stack[p.top]=number;
}
int pop()
{
int number=p.stack[p.top];
p.top--;
return number;
}
void calculate()
{
int n1, n2, x;
while(*(p.s))
{
if(*(p.s)==' ' || *(p.s)==' ')
{
p.s++;
continue;
}
if(isdigit(*(p.s)))
{
p.n=*(p.s)-'0';
push(p.n);
}
else
{
n1=pop();
n2=pop();
switch(*(p.s))
{
case '+':
x=n2+n1 ; 
                                break;
case '-':
x=n2-n1 ; 
                                break;
case '*':
x=n2*n1 ; 
                                break;
case '/':
x=n2/n1 ; 
                                break;
case '%':
x=n2%n1 ; 
                                break;
case '^':
x=(int)pow(n2,n1) ; 
                                break;
default:
cout<<"Invalid operator !!\n" ; 
                                exit(1);
}
push(x);
}
p.s++;
}
}
void disp_result()
{
p.n=pop();
cout<<"\nResult = "<<p.n;
}
int main()
{
char exp[MAX];
init_post();
cout<<"Enter the postfix formed expression : ";
gets(exp);
init_exp(exp);

calculate();

disp_result();
return 0;
}
/* 
The stack-full conditions not checked here
*/
/*********   OUTPUT  *********/
/*
Enter the postfix formed expression : 231*+9-
Result = -4 
*/

Kindly Like the article if you find it worthy ...





More Articles of Keshav Kabra:

Name Views Likes
C++ MLPACK :: CharExtract 560 4
Star Pattern - 3 527 5
Things a Beginner Programmer MUST Do 635 12
Ramanujan Numbers 1416 2
Star Pattern - 4 540 8
Implementation of Stack using Singly Linked-List 2249 10
C++ MLPACK :: Recall 500 7
C++ MLPACK Introduction 652 13
Star Pattern - 1 638 13
C++ MLPACK :: ZCAWhitening 547 4
Factorial using Stack 5821 5
C++ MLPACK :: Installation 1611 7
C++ MLPACK :: DatasetMapper 505 6
C++ MLPACK :: AdaBoost 982 10
C++ MLPACK :: ImageInfo 442 3
C++ MLPACK :: F1-Score (F1) 1032 7
C++ MLPACK :: MedianImputation 472 5
C++ MLPACK :: Split 838 7
C++ MLPACK :: Clustering 789 4
C++ MLPACK :: MeanNormalization 548 6
C++ MLPACK :: SimpleCV 588 8
Postfix Expression Evaluation by Stack 4756 14
C++ Program to Identify People Invited in a Party 956 3
C++ MLPACK :: ListwiseDeletion 511 5
C++ MLPACK :: ColumnsToBlock 361 2
C++ MLPACK :: Confusion Matrix 1376 7
C++ MLPACK :: Binarize 555 5
Print Statement Without Using Semi-Colon 434 4
C++ MLPACK :: MinMaxScaler 1061 5
C++ MLPACK :: MeanShift 984 3
C++ MLPACK :: MSE (Mean Squared Error) 1731 6
C++ MLPACK :: Data-Normalization 728 3
Mistakes People do While Learning Programming 533 12
Shift 3 Numbers without using Extra Memory 460 7
C++ MLPACK :: Perceptron 1119 2
C++ MLPACK :: LinearSVM 916 11
Left-Shift and Right-Shift Operators 503 5
Circular Queue using Array 2386 8
C++ MLPACK :: LinearRegression 1950 15
C++ MLPACK :: NeighborSearch 632 14
C++ MLPACK :: StandardScaler 1053 4
Sorting a Singly Linked-List 506 2
Star Pattern - 7 517 5
C++ MLPACK :: Precision 535 8
C++ MLPACK :: MaxAbsScaler 556 4
C++ MLPACK :: KMeans 1656 4
C++ MLPACK :: NaiveBayesClassifier 1181 4
C++ MLPACK :: NaiveKMeans 420 3
C++ MLPACK :: MeanImputation 424 5
C++ MLPACK :: DBSCAN 2056 3
C++ MLPACK :: Accuracy 479 8
C++ MLPACK :: DecisionStump 479 2
C++ MLPACK :: Ensemble Learning 708 9
C++ MLPACK :: EMST :: DTBRules 375 3
C++ MLPACK :: RangeType 411 2
Reverse a Singly Linked-List 515 6
Star Pattern - 5 (Pascal Triangle) 734 3
C++ MLPACK :: Imputer 567 6
Move Text on Pressing Keys 607 4
C++ MLPACK :: PCAWhitening 508 3
Star Pattern - 2 486 8
C++ MLPACK :: EMST :: EdgePair 432 3
C++ MLPACK :: Over-Fitting and Under-Fitting 692 7
Pythagorean Triplets 3414 3
Merge Two Linked-Lists 2777 5
Singly Circular Linked-List 450 4
C++ MLPACK :: LogisticRegression 2131 15
C++ MLPACK :: KFoldCV 853 9
Star Pattern - 6 528 5
C++ MLPACK :: LoadCSV 699 6
Sieve of Eratosthenes 5304 4
C++ MLPACK :: StringEncoding 867 6
C++ MLPACK :: EMST :: DTBStat 351 3
C++ MLPACK :: SplitByAnyOf 462 4
C++ MLPACK :: GaussianDistribution 427 3
C++ MLPACK :: SoftmaxRegression 725 12
Armstrong Numbers 470 3

Comments