Postfix Evaluation using Stack

/************************************************************
* Filename: postfix_evaluation.c
* Description: postfix evaluation using stack
* Author:Sarju S
* Date: 02-Dec-2011
*************************************************************/


#include
#include
#define MAX_EXPR_SIZE 100
#define MAX_STACK_SIZE 100 


typedef enum {eos,lparen, rparen, plus, minus, times, divide,mod,operand} precedence;
char postfixExpr[MAX_EXPR_SIZE];
int stack[MAX_STACK_SIZE];
int top=-1,postfixCount=0;


void stackFull()
{
fprintf(stderr, "Stack is full cannot add elements\n");
exit(EXIT_FAILURE);
}


void stackEmpty()
{
fprintf(stderr, "Stack is empty cannot delete elements\n");
exit(EXIT_FAILURE);
}


void push(int item)
{/* add an element to stack */
if(top>=MAX_STACK_SIZE-1)
stackFull();
top++;
stack[top] = item;
}


int pop()
{/*Delete top element from the stack*/
if(top==-1)
stackEmpty();
return stack[top--];
}




precedence getToken(char *symbol)
{ /* get the next token, symbol is the character representation,which is 
returned, the token is represented by its enumerated value, which is 
returned in the function name */
*symbol = postfixExpr[postfixCount];
postfixCount++;
switch(*symbol) {
case '\0': return eos;
case '(' : return lparen;
case ')' : return rparen;
case '+' : return plus;
case '-' : return minus;
case '/' : return divide;
case '*' : return times;
case '%' : return mod;
default  : return operand;
}
}




int postfixEvaluate(){
/* evaluate a postfix expression and returns the result */
precedence token;
char symbol;
int op1,op2;
token = getToken(&symbol);
while(token!=eos){
if(token==operand)
push(symbol-'0');

else{
/* pop two operands, perform operation and 
push result to stack */
op2 = pop();
op1 = pop();
switch(token){
case plus :push(op1+op2);
  break;
case minus :push(op1-op2);
  break;
case times :push(op1*op2);
  break;
case divide :push(op1/op2);
  break;
case mod :push(op1%op2);
 
}
}
token = getToken(&symbol);
}
return pop();/* return result */
}


void main(){
int result;
printf("\nEnter the POSTFIX expression:");
scanf("%s",postfixExpr);
result=postfixEvaluate(); /* Function Call*/
printf("\nThe Result is:%d",result);
}




OUTPUT

krishnakripa@krishnakripa-K8Upgrade-VM800:~$ gcc postfix_evaluation.c
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out


Enter the POSTFIX expression:62/3-42*+


The Result is:8
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ 

Read More

Infix to Postfix conversion using stack

/************************************************************
* Filename: infix_to_postfix.c
* Description: infix to postfix conversion using stack
* Author:Sarju S
* Date: 01-Dec-2011
*************************************************************/
#include
#include
#define MAX_EXPR_SIZE 100
#define MAX_STACK_SIZE 100 

typedef enum {eos,lparen, rparen, plus, minus, times, divide,mod,operand} precedence;
char infixExpr[MAX_EXPR_SIZE],postfixExpr[MAX_EXPR_SIZE];
precedence stack[MAX_STACK_SIZE];
int top=-1,infixCount=0,postfixCount=0;

void stackFull()
{
fprintf(stderr, "Stack is full cannot add elements\n");
exit(EXIT_FAILURE);
}

void stackEmpty()
{
fprintf(stderr, "Stack is empty cannot delete elements\n");
exit(EXIT_FAILURE);
}

void push(precedence item)
{/* add an element to stack */
if(top>=MAX_STACK_SIZE-1)
stackFull();
top++;
stack[top] = item;
}

precedence pop()
{/*Delete top element from the stack*/
if(top==-1)
stackEmpty();
return stack[top--];
}

void printToken(precedence token){
/* to print the symbol corresponding to token*/
switch(token) {
case 3 :postfixExpr[postfixCount]='+';
postfixCount++;
break;
case 4 :postfixExpr[postfixCount]='-';
postfixCount++;
break;
case 5 :postfixExpr[postfixCount]='*';
postfixCount++;
break; 
case 6 :postfixExpr[postfixCount]='/';
postfixCount++;
break;
case 7 :postfixExpr[postfixCount]='%';
postfixCount++;
}
}

precedence getToken(char *symbol)
{ /* get the next token, symbol is the character representation,which is 
returned, the token is represented by its enumerated value, which is 
returned in the function name */

*symbol = infixExpr[infixCount];
infixCount++;
switch(*symbol) {
case '\0': return eos;
case '(' : return lparen;
case ')' : return rparen;
case '+' : return plus;
case '-' : return minus;
case '/' : return divide;
case '*' : return times;
case '%' : return mod;
default  : return operand;
}
}

int checkPriority(precedence token){
switch(token) {
case plus   : 
case minus  : return 4;
case times  : 
case divide : return 6;
}

}

void infixToPostfix()
{/* output postfix of expression */
char symbol;
precedence token;
top = 0;
stack[0]= eos;
token = getToken(&symbol);
while(token!=eos){
if(token == operand){
postfixExpr[postfixCount]=symbol;
postfixCount++;
}

else if(token == rparen){
/*unstack tokens until left parenthesis */
while(stack[top]!= lparen)
printToken(pop());
pop(); /*remove left parenthesis */
}
else {
/*remove and print symbols whose in-stack precedence is greater than or 
 equal to the current tokens incoming precedence */
if(token!=1) /*Avoid Comparison of Left Paranthesis */
while(checkPriority(stack[top])>= checkPriority(token))
printToken(pop());
push(token);
}
token =getToken(&symbol);
} 
while((token = pop())!=eos)
printToken(token);
postfixExpr[postfixCount]='\0';
}

void main(){
printf("\nEnter the INFIX expression:");
scanf("%s",infixExpr);
infixToPostfix(); /* Function Call*/
printf("\nThe POSTFIX expression:");
printf("%s\n",postfixExpr);

}

OUTPUT

krishnakripa@krishnakripa-K8Upgrade-VM800:~$ gcc infix_to_postfix.c
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out

Enter the INFIX expression:((a/(b-c+d)))*(e-a)*c

The POSTFIX expression:abc-d+/ea-*c*
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ ./a.out

Enter the INFIX expression:a/b-c+d*e-a*c        

The POSTFIX expression:ab/c-de*+ac*-
krishnakripa@krishnakripa-K8Upgrade-VM800:~$ 

Read More