Page 98 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 4: Queues

Notes
*tptr = 0;
printf( “t=%s.\n”, t );
for( -tptr; tptr!=t-1; -tptr ) {
*resptr++ = *tptr;
}
*resptr = 0;
return res;
}
int main() {
char s[N];

puts( “enter infix freespaces max 80.” );
gets(s);
while(*s) {
puts( in2pre(s) );
gets(s);
}
return 0;
}
Explanation

1. In an infix expression, a binary operator separates its operands (a unary operator
precedes its operand). In a postfix expression, the operands of an operator precede

the operator. In a prefix expression, the operator precedes its operands. Like postfi x, a

prefix expression is parenthesis-free, that is, any infix expression can be unambiguously

written in its prefix equivalent without the need for parentheses.

2. To convert an infix expression to reverse-prefix, it is scanned from right to left. A

queue of operands is maintained noting that the order of operands in infix and prefi x

remains the same. Thus, while scanning the infix expression, whenever an operand is
encountered, it is pushed in a queue. If the scanned element is a right parenthesis (‘)’),
it is pushed in a stack of operators. If the scanned element is a left parenthesis (‘(‘), the
queue of operands is emptied to the prefix output, followed by the popping of all the

operators up to, but excluding, a right parenthesis in the operator stack.
3. If the scanned element is an arbitrary operator o, then the stack of operators is checked
for operators with a greater priority then o. Such operators are popped and written to

the prefix output after emptying the operand queue. The operator o is fi nally pushed
to the stack.

4. When the scanning of the infix expression is complete, first the operand queue, and

then the operator stack, are emptied to the prefix output. Any whitespace in the infi x
input is ignored. Thus the prefix output can be reversed to get the required prefi x

expression of the infi x input.
Question
Write a C program to implement a queue by using an array.

LOVELY PROFESSIONAL UNIVERSITY 93