Evaluating Postfix Expression Using Stack

• Previous
• Next

The postfix expression is a notation for expression used in computers where operator comes after the operands in the expression. It is also known as reverse polish notation. In this example, you will learn evaluating postfix expression using stack.

Advertisements

Suppose A and B are two operand and '+' is the operator. We humans write the infix expression which is A + B. However, the computer must convert the infix expression into postfix so that it can compute the expression.

Advertisements

It is the way computer look at expression.

Algorithm To Evaluate Postfix Expression

Let’s call this postfix expression as P and the stack as S. To evaluate P, the program must use following algorithm.

1. Add a right parenthesis ‘)’ at the end of expression P . It marks the end of the expression.
2. Start scanning the expression P until ‘)’ is reached.
3. If an operand is found, push that to stack S.
4. If an operator <span style="color:#cf2e2e" class="tadv-color">op</span> is found.
   1. Remove top two element of stack S, where A is topmost, and second to top is B.
   2. Evaluate <span style="color:#cf2e2e" class="tadv-color">B op A</span>.
   3. Push the result back to stack S.
5. Keep repeating step 3 and 4 until the end ‘)’ has reached.
6. The final result is top of the stack.
7. Stop the program.

Program Code:

/* Program to evaluate postfix
expression and output result */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <conio.h>
#define MAXSIZE 100

/* Stack array and top variables in structure */
struct stack
{
	int stack[];
	int Top;
};

/* type definition for user-defined 
data types */
typedef struct stack NODE;

/* This function will add an element
to Top of the stack */
void push(NODE *pu, int item)
{
	
	if (pu->Top== MAXSIZE-1)
	{
		printf("\nThe Stack is Full");
		getch();
	}
	else
	{
		
		pu->stack[++pu->Top] = item;
	}
}
/* This function will delete an element
from the top of the stack */
int pop(NODE *po)
{
	int item;
	/* If the Top pointer points to
	NULL then there is not element to
	delete */
	if(po->Top ==-1)
	{
		printf("\nThe Stack is Empty");
	}
	/*Otherwise delete the top of the stack
	and decrement the top pointer */
	else
	{
		item=po->stack[po->Top--];

		
	}
	return item;
}
/*Postfix evaluation*/
int Postfix_Eval(char postfix[])
{
	int a,b,temp,len;
	/* declaring a pointer variabe
	of type structure NODE */
	NODE *ps;
	int i;
	/* Initializing the Top pointer to NULL*/
	ps->Top=-1;
	push(ps,'#');
	/* Find length of the string */
	len = strlen(postfix);
	
	for(i=0;i<len;i++)
	{
		if(postfix[i]<='9'&&postfix[i]>='0')
		{
			/*Operand is pushed to stack*/
			push(ps,(postfix[i]-48));
		}
		else
		{
				/* Pop the two top operands for
				operation */
				a = pop(ps);
				b = pop(ps);
				
				switch(postfix[i])
				{
					case '+':
						temp=b+a;
						break;
					case '-':
						temp=b-a;
						break;
					case '*':
						temp=b*a;
						break;
					case '/':
						temp=b/a;
						break;
					case '%':
						temp=b%a;
						break;
					case '^':
						temp=pow(b,a);

				}/* End of switch*/
				push(ps,temp);
		}

	}
			      return(pop(ps));
}

int main() {
	
	char choice,postfix[MAXSIZE];
	do
	{
		clrscr();
		printf("\n\nEnter the Postfix expression=");
		fflush(stdin);
		gets(postfix);
		printf("\n\nThe Postfix Evaluation is = %d",Postfix_Eval(postfix));
		printf("\n\nDo you want to continue(Y/y)=");
		fflush(stdin);
		scanf("%c",&choice);
		}while(choice=='Y'||choice=='y');
return 0;
	}

Output

Enter the Postfix expression=46+9*

The Postfix Evaluation is = 90
Do you want to continue(Y/y)=_

• Previous
• Next