|
When higher level programming languages came into existence one of the major hurdles faced by the computer scientists was to generate machine language instructions which would properly evaluate any arithmetic expression. To convert a complex assignment statement such as: X = A/B + C * D - F * G/Q into a correct instruction sequence was a formidable task. That it is no longer considered so formidable is a tribute to the elegant and simple solutions that the computer scientists came out with. As of today this conversion is considered to be one of the minor aspects of compiler writing. To fix the order of evaluation of an expression each language assigns to each operator a priority. Even after assigning priorities how can a compiler accept an expression and produce correct code? The answer is given by reworking the expression into a form we call postfix notation. If e is an expression with operators and operands, the conventional way of writing e is called infix, because the operators come in between the operands (Unary operators precede their operand). The postfix form of an expression calls for each operator to appear after its operands. For example: infix; A*B/C has a postfix form: AB*C/ If we study the postfix form we see that the multiplication comes immediately after its two operands A and B. Now imagine that A * B is computed and stored in T. Then we have the division operator '/' coming immediately after its two operands T and C. Notice three features of the postfix expression:
Given below is a program which converts an infix expression into its postfix form. #define MAX 1000
void main( )
{
static
char target[MAX], stack[MAX];
char*t,
str[MAX], *s, n1, n2, item, nn;
int p1,
p2, i, top = -1 ;
printf("\nEnter
the infix expression:");
gets(str)
;
s = str
;
t =
target ;
while(*s)
{
if (*s
== '`' || *s == '\t')
{
s++;
continue;
}
if(isdigit
(*s) || isalpha (*s))
{
while
(isdigit(*s) || isalpha (*s))
{
*t =
*s; t++; s++;
}
}
if(*s ==
'(')
{
push
(stack, &top, *s); s++;
}
if( *s
== ')')
{
n1 = pop
(stack, &top);
while
(n1)!='(' )
{
*t =
n1;
t++;
n1 =
pop (stack, &top) ;
}
s++;
}
if(*s
=='+' || *s =='*' || *s == '/' || *s == '%' )
{
if ( top
== -1)
push(stack,
&top, *s);
else
{
n1 =
pop (stack, &top);
while(
priority (n1) >= priority(*s ) )
{
*t =
n1;
t++;
n1 =
pop (stack, &top) ;
}
push(stack,
&top, n1);
push(stack,
&top, *s);
}
s++;
}
}
while
(top != -1)
{
n1 = pop
(stack, &top);
*t = n1;
t++;
}
*t =
'\0'; t=target;
while(*t)
{
printf("%c",
*t);
t++;
}
}
/*checks the priority of
the operators*/
int priority(char
ele)
{
int
pri;
char a,
b, c;
if ( ele
=='*' || ele == '/'|| ele == '%' )
pri =
2;
else
{
if(ele
== '+' || ele == '-')
pri =
1;
else
pri =
0;
}
return
pri ;
}
void push(char *stk,
int*sp, char item)
{
if (*sp
== MAX)
printf("\nStack
is full");
else
{
*sp =
*sp + 1;
stk[*sp]
= item;
}
}
char pop (char *stk,
int*sp)
{
int
item;
if(*sp
== -1)
{
printf("\nStack
is empty");
return(-1);
}
else
{
item =
stk[*sp];
*sp=*sp
- 1;
return
(item);
}
}
We know that it is convenient to work with expressions which are converted from the infix form to the postfix form.Below I am presenting a program which converts an infix expression into an equivalent prefix expression. Just to remind you, in the prefix form the operator appears before its operands. #define MAX 100
main( )
{
char
targ char n1; int p1, p2, i, top = -1, l ; static char stack[MAX]; clrscr( ) ; printf("\nEnter the infix expression;"); gets(str); s = str; strrev(str); l = strlen (str); t = target + ( l -1 );
while(*s) {
/*skip
whitespace if any*/
if(*s
==' '|| *s == `\t')
{
s++;
continue;
}
/*put
digit in target string*/
if(isdigit(*s)
|| isalpha (*s) )
{
while(isdigit(*s)
|| isalpha (*s))
{
*t =
*s;
t--;
s++;
}
}
if (*s
== `)')
{
push(stack,
&top, *s);
s++;
}
if(*s ==
`(')
{
n1 = pop
(stack, &top);
while(n1!=`)')
{
*t =
n1; t--;
n1 =
pop (stack, &top);
}
s++;
}
if(*s ==
`+'|| *s == `_' || *s == `/' || *s == `%')
{
if(top
== -1)
push(stack,
&top, *s);
else
{
n1 =
pop (stack, &top);
while(priority(n1)>=priority(*s)
)
{
*t=n1;
t--;
n1=pop(stack,
&top);
push(stack,
&top, n1);
push(stack,
&top, *s);
}
s++;
}
}
while(top!=
-1)
{
n1 =
pop(stack, &top);
*t = n1;
t--;
}
*(target
+ |) = `\0';
t++;
while
(*t)
{
printf("%c",
*t);
t++;
getch();
}
priority(char
ele)
{
int
char a,
b, c;
if(ele
== `+' || ele == `/' || ele == `%')
pri =
2;
{
if(ele
== `+' || ele == `_')
pri =
1;
else
pri =
0;
}
}
push(char*stk,
int*sp, char item)
{
if(*sp
== MAX)
printf("\nStack
is full");
else
{
*sp =
*sp + 1; stk[*sp] = item;
}
}
pop
(char *stk, int*sp)
{
int
item;
if(*sp
== -1)
{
printf("\nStack
is empty");
return(-1);
}
else
{
item =
stk[*sp];
*sp =
*sp - 1;
return(item);
}
}
} By now we know how to convert an expression in Infix form to either the Prefix or the Postfix form. Let us now concentrate on other conversions like Postfix to Prefix and Postfix to Infix. Here is a program which carries out the first conversion. /*Convert Postfix to Prefix */
#define MAX 100
void pop (char *a1);
void push(char *str);
char stack[MAX][MAX];
int top =-1;
main()
{
char
s[MAX], str1[MAX], str2[MAX], str[MAX];
char
s1[2], temp[2];
int i =
0;
clrscr();
printf("Enter
the postfix expression; ");
gets
(s);
while(s[i]!=`\0')
{
/*skip
whitespace, if any */
if (s[i]
== '')
i++;
if(s[i]
== `%' || s[i] == `*' || s[i] == `_' || s[i]== `+' || s[i] == `/')
{
pop
(str1);
pop
(str2);
temp[0]
= s[i];
temp[1]
= `\0';
strcpy
(str, temp);
strcat(str,
str2);
strcat(str,
str1);
push(str);
}
else
{
temp[0]
= s[i];
temp[1]
= `\0';
strcpy
(s1, temp);
push
(s1);
}
i++;
}
printf("\n%s",stack[0]);
}
void pop(char*a1)
{
if(top == -1)
{
printf("\nStack
is empty");
exit(1);
}
else
{
strcpy
(a1, stack[top]);
top--;
}
}
void push (char *str)
{
if(top
== MAX - 1)
printf("\nstack
is full");
else
{
top++;
strcpy(stack[top],
str);
}
} In the last of the expression conversion series I am presenting a program to convert a Postfix expression to an Infix expression. Here it is...
#define Max 100
void pop (char*);
void push(char*);
char stack[MAX]
[MAX];
int top = -1
main()
{
char
s[MAX], str1[MAX], str2[MAX], str[MAX];
char
s1[2],temp[2];
inti=0;
clrscr(
) ;
printf("\Enter
the postfix expression; ")
get(s);
while
(s[i]!`\0')
{
/*skip
whitespace, if any*/
if(s[i]
== ' ' )
i++;
if (s[i]
== `%' || s[i] == `*'|| s[i] == `-' || s[i] == `+' || s[i] == `/')
{
pop(str1);
pop(str2);
temp[0]
=`(';
temp[1]
=`\0';
strcpy(str,
temp);
strcat(str,
str2);
temp[0]
= s[i];
temp[1]
= `\0'
strcat(str,temp);
strcat(str,
str1);
temp[0]
=`)';
temp[1]
=`\0';
strcat(str,temp);
push(str);
}
else
{
temp[0]=s[i];
temp[1]=`\0';
strcpy(s1,
temp);
push(s1);
}
i++;
}
printf("\n%s",
stack[0]);
}
void pop(char *a1)
{
strcpy(a1,stack[top]);
top--;
}
void push (char*str)
{
if(top
== MAX - 1)
printf("\nstack
is full");
else
{
top++;
strcpy(stack[top],
str);
}
} So far we have seen programs which could translate expressions from infix to postfix to prefix notation to any such combination. The virtue of a postfix notation is that it enables easy evaluation of expressions. To begin with, the need for parentheses is eliminated. Secondly, the priority of the operators is no longer relevant. The expression may be evaluated by making a left to right scan, stacking operands, and evaluating operators using operands from the stack and finally placing the result onto the stack. This evaluation process is much simpler than attempting a direct evaluation of infix notation. The following program implements the postfix expression evaluation algorithm. #define MAX 25
void push ( int * , int * ,
int ) ;
int pop ( int *, int * )
;
main( )
{
char
str[MAX], *s ;
int n1,
n2, n3, nn ;
int
stack[MAX], top = -1 ;
clrscr();
printf (
"\nEnter the postfix expression to be evaluated: " ) ;
gets (
str ) ;
s = str
;
while (
*s )
{
/* skip
whitespace, if any */
if ( *s
== ' ' || *s == '\t' )
{
s++
;
continue
;
}
/* if
digit is encountered */
if ( *s
>= 48 && *s <= 57 )
{
nn = *s
- '0' ;
push (
stack, &top, nn ) ;
}
else
{ /* if operator is encountered */ n1 = pop ( stack, &top ) ; n2 = pop ( stack, &top ) ; switch ( *s ) {
case
'+' :
n3 = n2
+ n1 ;break ;
case
'-' :
n3 = n2
- n1 ;break ;
case
'/' :
n3 = n2
/ n1 ;break ;
case
'*' :
n3 = n2
* n1 ;break ;
case
'%' :
n3 = n2
% n1 ;break ;
default
:
printf
( "Unknown operator" ) ;
exit (
1 ) ;
push ( stack, &top, n3 ) ;
}
s++
;
}
printf (
"Result is : %d", pop ( stack, &top ) ) ;
}
void push ( int *stk, int
*sp, int item )
{
if ( *sp
== MAX )
printf (
"\nStack is full" ) ;
else
{
* stk[*sp]
= item ;
}
}
int pop ( int *stk, int *sp
)
{
int item
;
if ( *sp
== -1 )
{
printf (
"\nStack is empty" ) ;
return (
-1 ) ;
}
else
{
item =
stk[*sp] ;
*sp =
*sp - 1 ;
return (
item ) ;
}
} |
|
Designed and
Managed by |
|