In this article, we discuss about writing a C program to convert infix expression to prefix expression. The infix expression is of form operand operator operand and it is converted to operator operand operand form.
Consider the following example.
// Infix expression
((A + B) * C)
// Prefix expression
*+ABCProblem Definition
The user enters an infix expression and the C program converts the infix expression to prefix equivalent expression.
The program uses a character array to receive the<span style="color:#cf2e2e" class="tadv-color"> input expression</span> and another character array to output the final prefix expression. The program use a <span style="color:#cf2e2e" class="tadv-color">stack S</span> to keep track of operators and parenthesis of the expression.
Here is the algorithm to convert infix expression to prefix expression.
- Scan the infix expression right to left.
- If the character is right parenthesis “)”, push to stack S.
- If the character is left parenthesis “(“, then start popping stack one by one and put the characters into prefix array.
- If the scanned character is operator , compare with the operator on stack and continuously pop operators from stack if scanned operator has less precedence than the operator on the top of the stack. If scanned operator has higher precedence than top of the stack. Put the operator on the stack.
- If scanned character is an operand, directly put it in the prefix array.
- If all scanned character is finished , start popping stack and put the operators in prefix array one by one.
For example, suppose we want to convert the infix expression ((A + B) * C) into prefix expression.
Step 1: Start scanning from right to left of the infix expression.
Step 2: Identify the character and put it in stack or prefix array accordingly.
Scanned character Type Stack Prefix array Stack Operation
--------------------------------------------------------------------------
) operator ) push(')')
C operand C n/a
* operator * push('*')
) operator ) push(')')
B operand B n/a
+ operator + push('+')
A operator A n/a
( operator + pop()
* pop()
( operator ( pop()
Prefix Array :- *+ABCFunctions Used In the Program
The program uses functions to perform scan, pop from stack, push to stack, check the precedence of operators, etc. Each of these function is discussed in the following sections.
Stack Functions
void push(char sym)
{
top = top + 1;
s[top] = sym;
}char pop ()
{
char item;
item = s[top];
top = top-1;
return item;
}Identify priority of scanned character
You need to identify the priority level of scanned character so that we can compare it with the operator on the top of the stack . The function will return a number for each scanned character.
int G (char symbol)
{
switch (symbol)
{
case '+':
case '-': return 2;
case '*':
case '/': return 4;
case '^':
case '$': return 5;
case '(': return 0;
case ')': return 9;
default : return 7;
}
}Identify priority of character on the top of the stack
This function will return the priority of a character on the top of the stack. We must compare it with the priority of the scanned character. If scanned character has higher priority , push it into the stack.
Else start popping characters from stack and push them into prefix array until scanned character priority become higher.
int F (char symbol)
{
switch (symbol)
{
case '+':
case '-': return 1;
case '*':
case '/': return 3;
case '^':
case '$': return 6;
case '(': return 0;
case '#': return -1;
default : return 8;
}
}Infix expression to prefix expression converter
This the main function that does character by character scan of infix expression. Let’s look at the variable declarations.
/* Global Declarations */
int pos = 0;
int top; /* top of the stack pointer */
int length; /* length of the expression */
char symbol; /* scanned character */
char temp; /* when item is popped from stack we will keep it in temp */
char s[30]; /* stack of type character */
char infix; /* infix expression */
char prefix; /* prefix array for prefix expression */
/* void infix_prefix (char infix[], char prefix[])
{
int i, t1;
top = -1; /* stack is empty */
length = strlen(infix); /* length of infix expression */
length = length - 1; /* The length of the expression
pos = length; is used for prefix array
t1 = length; and infix array */
/* start scanning the infix expression */
while ( length >= 0)
{
symbol = infix[length];
switch(symbol)
{
/* if ) push to stack */
case ')': push(symbol);
break;
/* if ( start popping from
stack unless a matching )
not found */
case '(':
temp = pop();
while( temp != ')')
{
prefix[pos] = temp;
pos--;
temp = pop();
}
if (temp != ')')
{
prefix[pos--] = pop();
}
break;
case '+':
case '-':
case '*':
case '$':
case '/':
case '^': while(F(s[top]) >= G(symbol)) /* if priority of stack is more than
{ scanned symbol, then keep
popping stack until priority
of stack top become less than
the scanned character */
temp = pop();
prefix[pos] = temp;
pos--;
}
push(symbol);
break;
default:
prefix[pos--] = symbol;
break;
}
length--; /*after scanning each character
decrement length to the
next character */
{
while(s[] != '#') /* when all characters are
scanned, then start popping
{ stack and put every thing
temp = pop(); prefix array */
prefix[pos--] = temp;
}
for (i = 0; i < t1; i++) /* reverse the expression in prefix
{ array to get the correct result */
prefix[i] = prefix[i + pos + 1];
}
Flowchart – infix to prefix
Program Code – Infix To Prefix
#include <stdio.h>
#include <string.h>
#include <conio.h>
/* Global Declarations */
int pos = 0;
int top;
int length;
char symbol;
char temp;
char s[30];
char infix;
char prefix;
void push(char sym)
{
top = top + 1;
s[top] = sym;
}
char pop ()
{
char item;
item = s[top];
top = top-1;
return item;
}
int G (char symbol)
{
switch (symbol)
{
case '+':
case '-': return 2;
case '*':
case '/': return 4;
case '^':
case '$': return 5;
case '(': return 0;
case ')': return 9;
default : return 7;
}
}
int F (char symbol)
{
switch (symbol)
{
case '+':
case '-': return 1;
case '*':
case '/': return 3;
case '^':
case '$': return 6;
case '(': return 0;
case '#': return -1;
default : return 8;
}
}
void infix_prefix (char infix[], char prefix[])
{
int i, t1;
top = -1;
length = strlen(infix); expression */
length = length - 1;
pos = length;
t1 = length;
while ( length >= 0)
{
symbol = infix[length];
switch(symbol)
{
case ')': push(symbol);
break;
case '(':
temp = pop();
while( temp != ')')
{
prefix[pos] = temp;
pos--;
temp = pop();
}
if (temp != ')')
{
prefix[pos--] = pop();
}
break;
case '+':
case '-':
case '*':
case '$':
case '/':
case '^': while(F(s[top]) >= G(symbol))
{
temp = pop();
prefix[pos] = temp;
pos--;
}
push(symbol);
break;
default:
prefix[pos--] = symbol;
break;
}
length--;
{
while(s[] != '#')
{
temp = pop();
prefix[pos--] = temp;
}
for (i = 0; i < t1; i++)
{
prefix[i] = prefix[i + pos + 1];
}
/* MAIN PROGRAM */
void main ()
{
clrscr();
printf("Enter the valid infix expression\n');
scanf("%s",infix);
infix_prefix(infix, prefix);
printf("The prefix expression \n");
printf("%s\n",prefix);
getch();
}Output
*+ABC