| Conversion Of Expressions | |
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:
-
The operands maintain the same order as in the equivalent infix expression.
-
Parentheses are not needed to designate the expression unambiguously.
-
While evaluating the postfix expression the priority of the operators is no longer relevant.
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);
}
}
| | Infix To Prefix Conversion | |
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 target[MAX], *t, str[MAX], *s;
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 pri;
char a, b, c;
if(ele == `+' || ele == `/' || ele == `%')
pri = 2;
else
{
if(ele == `+' || ele == `_')
pri = 1;
else
pri = 0;
}
return pri;
}
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
{
*sp = *sp + 1 ;
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 ) ;
}
}
No comments:
Post a Comment