Converting an expression from infix to prefix notation might look a bit tricky when seeing the examples, but it's a straightforward process once you get the hang of it. It reverses the expression's order and turns the operators into their prefix counterparts. Then, finally, swapping the positions of the operands. The result is a clean prefix expression where the operator comes first and appears before its operands. Let’s explore how infix to prefix program in c works step by step.
But first, we look into the basics: what is the infix notation? The infix is the usual format in which an expression is written. Some examples of it are A+B, A*B, A/B, and so on. As you can see, the operators +,* and / come between the operands. Hence, the syntax of infix notation is:
<operand> <operator> <operand>
When parsing is performed on the expression, two things become important: Operator Precedence and Associativity.
The operator precedence simply refers to which operation has to be done first according to the rules of mathematics. If there is an expression A+B*C, then the order with which the expression is to be evaluated is A + (B*C) since multiplication takes higher precedence over addition. Therefore, B*C is evaluated first and then added to A. Here is the precedence order of different operators:
Associativity is used when there are multiple operators with the same precedence in an expression. Take the expression A + B - C, for example. Both '+' and '-' have the same precedence, so we use associativity to determine the order of evaluation. We know that by convention, both operators are left-associative. Therefore, we should evaluate it from left to right. So we first compute (A + B), then subtract C.
This table shows the associativity order used in c:
Example
Consider this expression: 2 + 2*3 + 20/5
Multiplication operator (*) and division operator (/) have the same precedence. Therefore, we will have to use the associativity order to evaluate the expression. The table above shows that the associativity for ( * and / ) is from left to right. Therefore, the leftmost operator will be performed first.
The expression then becomes: 2 + 6 + 4 = 12.
The prefix notation is a different way of expressing that does not require precedence and associativity. In prefix, the operator is placed before the operands. Therefore, the notation looks like this:
<operator> <operand> <operand>
Consider the example 5+1, which is an infix expression. The prefix expression of the same is +51.
If the expression is A*B+C, the prefix becomes
*AB + C in the first scan
+*abc in the second scan.
To convert an infix expression to prefix notation, we can use a stack data structure. Here’s how the process works:
Step 1: Reverse the infix expression. While doing so, make sure to swap the parentheses. That means you have to change every '(' to ')' and vice versa.
Step 2: Convert the reversed infix expression into a "nearly" postfix expression. When handling operators, instead of popping operators with equal or higher precedence, you only pop those with higher precedence from the stack.
Step 3: Finally, reverse the postfix expression to get the desired prefix result.
Consider the infix expression X+(Y*Z). The flow chart shows how it’s converted to prefix notation:
There are two methods to convert infix to prefix:
Method 1 – Using Array
Method 2 – Dynamically created Stack
Let's take the example infix expression to see how the infix to prefix algorithm works:
((a/b)+c)-(d+(e*f))
Step 1: Reverse the Infix Expression and Swap Parentheses
Original Infix: ((a/b)+c)-(d+(e*f))
Reversed String: ))f*e(+d(-)c+)b/a((
Swap Parentheses: ((f*e)+d)-(c+(b/a))
Step 2: Convert Reversed Infix to Postfix
Now, let's convert ((f*e)+d)-(c+(b/a)) to a postfix expression.
Here's the step-by-step table for this process:
Final prefix: -+/abc+d*ef
In this infix to prefix algorithm,
The code for converting an infix expression to a prefix expression using an array works by following three key steps: reversing the infix expression, converting it to postfix, and then reversing the postfix to obtain the prefix. Here’s how it goes:
1. Reversing the Infix Expression
2. Converting Reversed Infix to Postfix
3. Reversing the Postfix to Get Prefix:
#include<stdio.h>
#include<string.h>
#include<limits.h>
#include<stdlib.h>
#define MAX 100
int top = -1;
char stack[MAX];
// checking if stack is full
int isFull ()
{
return top == MAX - 1;
}
// checking is stack is empty
int isEmpty ()
{
return top == -1;
}
void push (char item)
{
if (isFull ())
return;
top++;
stack[top] = item;
}
// Function to remove an item from stack. It decreases top by 1
int pop ()
{
if (isEmpty ())
return INT_MIN;
// decrements top and returns what has been popped
return stack[top--];
}
// Function to return the top from stack without having to remove it
int peek ()
{
if (isEmpty ())
return INT_MIN;
return stack[top];
}
// A utility function: It is to check if the provided character is operand
int checkIfOperand (char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
// Fucntion to compare precedence
// If we return bigger value, it means higher precedence
int precedence (char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
// The driver function for infix to postfix conversion
int getPostfix (char *expression)
{
int i, j;
for (i = 0, j = -1; expression[i]; ++i)
{
if (checkIfOperand (expression[i]))
expression[++j] = expression[i];
else if (expression[i] == '(')
push (expression[i]);
else if (expression[i] == ')')
{
while (!isEmpty (stack) && peek (stack) != '(')
expression[++j] = pop (stack);
if (!isEmpty (stack) && peek (stack) != '(')
return -1; // invalid expression
else
pop (stack);
}
else // if an opertor
{
while (!isEmpty (stack)
&& precedence (expression[i]) <= precedence (peek (stack)))
expression[++j] = pop (stack);
push (expression[i]);
}
}
// Once all inital expression characters are traversed
// adding all left elements from stack to exp
while (!isEmpty (stack))
expression[++j] = pop (stack);
expression[++j] = '\0';
}
void reverse (char *exp)
{
int size = strlen (exp);
int j = size, i = 0;
char temp[size];
temp[j--] = '\0';
while (exp[i] != '\0')
{
temp[j] = exp[i];
j--;
i++;
}
strcpy (exp, temp);
}
void brackets (char *exp)
{
int i = 0;
while (exp[i] != '\0')
{
if (exp[i] == '(')
exp[i] = ')';
else if (exp[i] == ')')
exp[i] = '(';
i++;
}
}
void InfixtoPrefix (char *exp)
{
int size = strlen (exp);
// reverse string
reverse (exp);
//change brackets
brackets (exp);
//get postfix
getPostfix (exp);
// reverse string again
reverse (exp);
}
int main ()
{
printf ("The infix is: ");
char expression[] = "((a/b)+c)-(d+(e*f))";
printf ("%s\n", expression);
InfixtoPrefix (expression);
printf ("The prefix is: ");
printf ("%s\n", expression);
return 0;
}Output:
The infix is: ((a/b)+c)-(d+(e*f))
The prefix is: -+/abc+d*efThe stack-based approach for converting infix to prefix is similar to the array-based method. Both methods follow the same basic steps: reversing the infix expression, converting it to postfix, and then reversing the postfix to obtain the prefix. The main difference is in how the intermediate steps are handled:
1. In the array, the postfix expression is directly constructed within an array. In the stack method, a stack is used to store operators and manage their precedence during the conversion to postfix.
2. With the array, operators are directly added to the output array as they are processed. In the stack, operators are pushed and popped from the stack based on precedence.
#include<stdio.h>
#include<string.h>
#include<limits.h>
#include<stdlib.h>
#define MAX 100
int top = -1;
char stack[MAX];
// checking if stack is full
int isFull ()
{
return top == MAX - 1;
}
// checking is stack is empty
int isEmpty ()
{
return top == -1;
}
void push (char item)
{
if (isFull ())
return;
top++;
stack[top] = item;
}
// Function to remove an item from stack. It decreases top by 1
int pop ()
{
if (isEmpty ())
return INT_MIN;
// decrements top and returns what has been popped
return stack[top--];
}
// Function to return the top from stack without having to remove it
int peek ()
{
if (isEmpty ())
return INT_MIN;
return stack[top];
}
// A utility function: It is to check if the provided character is operand
int checkIfOperand (char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
// Fucntion to compare precedence
// If we return larger value means higher precedence
int precedence (char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
// The driver function for infix to postfix conversion
int getPostfix (char *expression)
{
int i, j;
for (i = 0, j = -1; expression[i]; ++i)
{
if (checkIfOperand (expression[i]))
expression[++j] = expression[i];
else if (expression[i] == '(')
push (expression[i]);
else if (expression[i] == ')')
{
while (!isEmpty (stack) && peek (stack) != '(')
expression[++j] = pop (stack);
if (!isEmpty (stack) && peek (stack) != '(')
return -1; // invalid expression
else
pop (stack);
}
else // if an opertor
{
while (!isEmpty (stack)
&& precedence (expression[i]) <= precedence (peek (stack)))
expression[++j] = pop (stack);
push (expression[i]);
}
}
// Once all inital expression characters are traversed
// adding all left elements from stack to exp
while (!isEmpty (stack))
expression[++j] = pop (stack);
expression[++j] = '\0';
}
void reverse (char *exp)
{
int size = strlen (exp);
int j = size, i = 0;
char temp[size];
temp[j--] = '\0';
while (exp[i] != '\0')
{
temp[j] = exp[i];
j--;
i++;
}
strcpy (exp, temp);
}
void brackets (char *exp)
{
int i = 0;
while (exp[i] != '\0')
{
if (exp[i] == '(')
exp[i] = ')';
else if (exp[i] == ')')
exp[i] = '(';
i++;
}
}
void InfixtoPrefix (char *exp)
{
int size = strlen (exp);
// reverse string
reverse (exp);
//change brackets
brackets (exp);
//get postfix
getPostfix (exp);
// reverse string again
reverse (exp);
}
int main ()
{
printf ("The infix is: ");
char expression[] = "((a/b)+c)-(d+(e*f))";
printf ("%s\n", expression);
InfixtoPrefix (expression);
printf ("The prefix is: ");
printf ("%s\n", expression);
return 0;
}Output:
The infix is: ((a/b)+c)-(d+(e*f))
The prefix is: -+/abc+d*ef
=== Code Execution Successful ===
The processes for converting infix to prefix and prefix to infix are quite different, although both involve rearranging operators and operands. In an infix to prefix conversion, you have to rearrange the expression so that operators precede their operands. In a prefix to infix conversion, the goal is to turn back a prefix expression to its standard infix form. A prefix to infix converter simplifies this by following operator precedence rules to rebuild the correct infix expression.
Understanding infix and prefix conversion is crucial for budding coders as it forms the foundation for evaluating expressions in programming. It will help you learn operator precedence, expression evaluation, and how compilers process code. The same concepts are essential when dealing with complex algorithms, so the infix to prefix algorithms in c build practice for long-term coding projects. Learning them in C is especially valuable because C is a powerful, low-level language that helps build strong coding fundamentals. Mastering C sharpens logical thinking and opens doors to advanced programming.
Going further, understanding how to convert prefix to infix is an equally important topic. You can later go into concepts like prefix to infix converter, which uses a similar approach in reverse.
To build your foundation towards a successful software career, join the CCBP Academy 4.0 program to supplement your education and become job-ready.
Infix notation is the standard mathematical way of writing expressions (like A + B). Prefix notation places the operator before the operands (like + A B).
Converting infix to prefix is essential in computers because prefix expressions are easier for machines to process. It helps avoid ambiguity in operator precedence and is used in compiler design and expression evaluation.
A stack helps store operators temporarily while converting expressions. It ensures that operators are applied in the correct order based on precedence, making the conversion process fast and accurate.
Reversing the expression helps simplify the process of conversion. It allows you to apply the same rules for converting infix to postfix. But it is done in the same way that aligns with the prefix notation, where the operator appears before the operands.
Operators are placed between operands (e.g., A + B) in infix notation, while in prefix notation, the operator comes before the operands (e.g., + A B).
