Page 69 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Stacks are frequently used for converting INFIX form into equivalent PREFIX and POSTFIX
forms.

The whole logic is same as for Infix to Postfix except, before traversing the string reverse it by

strrev() function and then process as before, but instead of printing the expression take output in
another stack and then print the stack, at last reverses the string.

Process of
str Strrev (str) Prefix Expression
Conversion

Consider the following example.

Infix expression -> a + b * c + d

After reversing it -> d + c * b + a

Now apply the logic of Infix to Postfix conversion and store the output in another stack.

+
a
OPERATOR OUTPUT +
STACK * STACK *
+ + b
c
d

Now on printing the stack we have, + a + * b c d which is a prefix expression. Here is a C

implementation for converting infix into postfi x.
/* Convert infix expression into corresponding postfix expression */
/* Maximum length of the input expression allowed is 20 characters */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef struct
{
char data[20]; /* array to hold stack contents */
int top; /* top of the stack pointer */
}stk;
/* function prototypes */
void initStack(stk *stack);
void get_infix(char infix[]);
void convertToPostfix(char infix[], char postfix[]);
int isOperator(char c);
int precedence(char operator1, char operator2);
int pred_level(char ch);
void push(stk *stack, char value);

64 LOVELY PROFESSIONAL UNIVERSITY