Infix
to Postfix conversion
A+B -> Infix
AB+ -> Postfix
+AB -> Prefix
Algorithm
Step-1 Initialize the stack
Step-2 Scan the leftmost
symbol in the given infix expression and denote is as the current input symbol.
Step-3 Repeat through step-6
while infix expression
Step-4 Remove and output all
stack symbols whose precedence values are greater than or equal to the
precedence of the current input symbol.
Step-5 Push the current input
symbol onto the stack.
Step-6 Scan the leftmost
symbol in the infix expression and let it be the current symbol.
Program
To convert infix to postfix
//postfix program
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define Maxlen 64
static char infix [Maxlen+1],
stack[Maxlen], postfix[Maxlen+1];
static int top;
//symbol type
#define Operator (-10)
#define Operand (-20)
#define LeftParen (-30)
#define RightParen (-40)
static char *symbols =
"()+-*/";
//symbol precedence
#define LeftParenPrec 0 // (
#define AddPrec 1 // +
#define SubPrec 1 // -
#define MultPrec 2 // *
#define DivPrec 2 // /
#define RemPrec 2 // %
#define None 999 // all else
void
infix_to_postfix(void);
void
push(char symbol);
char
pop(void);
int
get_type(char);
int
grt_prec(char);
int
white_space(char);
void
main()
{
char
ans;
clrscr();
do
{
top=-1; //reset stack
printf("\nInfix
(up to %d chars ) : ",Maxlen);
gets(infix);
infix_to_postfix();
printf("\n
Infix : %s",infix);
printf("\n
Postfix : %s",postfix);
printf("\n
do you want to continue (y/n) : ");
ans=getchar();
}while(ans==
'y' || ans=='Y');
}
// function infix to postfix
conversion
void
infix_to_postfix(void)
{
int
i,p,len,type,precedence;
char
next;
//
i for infix and p for postfix
i=p=0;
len=strlen(infix);
//loop through input string
while(i<len)
{
if(!white_space(infix[i]))
{
type=get_type(infix[i]);
switch(type)
{
//push
left parenthesis onto stack
case
LeftParen:
push(infix[i]);
break;
//pop
stack until matching left parenthesis
case
RightParen:
while((next=pop())!='(')
{
postfix[p++]
= next;
}
break;
case
Operand:
postfix[p++]
= infix[i];
break;
/*
pop stack until first operator of higher
precedence
and then stack this operator */
case
Operator:
precedence
= get_prec(infix[i]);
//
anything on stack to pop
while(top
> -1 && precedence <= get_prec(stack[top]))
postfix[p++]
= pop();
push(infix[i]);
break;
}
}
i++; // next symbol in infix expression
}
//pop
any remaining operators
while(top
> -1)
{
postfix[p++]
= pop();
}
postfix[p]
= '\0'; //ensure astring
getch();
}
// function to find operator type
int
get_type(char symbol)
{
switch(symbol)
{
case
'(':
return
(LeftParen);
case
')':
return
(RightParen);
case
'+':
case
'-':
case
'%':
case
'*':
case
'/':
return
(Operator);
default
:
return
(Operand);
}
}
// find precedence of the operator
int
get_prec(char symbol)
{
switch(symbol)
{
case
'+':
return
(AddPrec);
case
'-':
return
(SubPrec);
case
'*':
return
(MultPrec);
case
'/':
return
(DivPrec);
case
'%':
return
(RemPrec);
case
'(':
return (LeftParenPrec);
default:
return
(None);
}
}
//function push
void
push(char symbol)
{
//
check for overflow
if(top
> Maxlen)
//full_stack();
printf("\n
Stack is full");
else
stack[++top]
= symbol;
}
// function pop
char
pop(void)
{
// check for underflow
if(top
<= -1)
{
printf("\n
Stack is empty");
return
' ';
}
else
return(stack[top--]);
}
// function white space checking
int
white_space(char symbol)
{
return(symbol
== ' ' || symbol == '\t' || symbol == '\0');
}
Posted By : Ruchita Pandya
No comments:
Post a Comment