Infix to Prefix Conversion using Stack in C++

Infix to Prefix Expression Conversion:-

In this section today we will learn the infix to prefix conversion using stack in C++ in which an infix expression first is reversed including reversing the opening and closing parenthesis will also be reversed. Then the expression is in postfix after that reverse it to get prefix expression.

Infix to prefix conversion (2)

Definition:-

  • Infix Expression:- This kinds of notation is called an infix since the operator is in between the two operands under which it works.
  • Prefix Expression:- In this equations all operators must precede the two operands on which they are involved

Steps required for infix to prefix conversion using stack in C++

  • Initially reverse the expression given for the infix.
  • One by one scan of characters.
  • Is if character is an operand, then copy it to the output of the prefix notation.
  • When the character is a parenthesis closing then push it to the stack.
  • If the character is an opening parenthesis, pop the elements in the stack till we find the closing parenthesis that corresponds.
  • If a character scanned is operator.
  • If the operator has greater or equal precedence than the top of the stack, push the operator to the stack.
  • If the operator has less precedence than the top of the stack, pop the operator and output it to the output of the prefix notation, then check the above condition with the new top of the stack again.
  • After scanning all the characters, reverse the notation output for the prefix.
Infix to prefix conversion

C++ Program for Infix To Prefix Conversion using stack data structures:-

Run
#include <bits/stdc++.h>
using namespace std;
//definition of functions
struct Stack *create (int max);
int stackFull (struct Stack *stack);
int stackEmpty (struct Stack *stack);
void pushElement (struct Stack *stack, int item);
int popElement (struct Stack *stack);
int peekElement (struct Stack *stack);
int checkOperand (char ch);
int precedence (char ch);
int postfix (char *expression);
void reverse (char *exp);
void brackets (char *exp);
void conversionInfixToPrefix (char *exp);
// A structure to represent a stack
struct Stack
{
  int top;
  int maxSize;
  int *array;
};
int main ()
{
  int n = 10;
  cout << "The infix expression is: \n";
  char expression[] = "(P+(Q*R)/(S-T))";
  cout << expression << "\n";
  conversionInfixToPrefix (expression);
  cout << "The prefix expression is: \n";
  cout << expression;
  return 0;
}
//stack implementation
struct Stack * create (int max)
{
  struct Stack *stack = (struct Stack *) malloc (sizeof (struct Stack));
  stack->maxSize = max;
  stack->top = -1;
  stack->array = (int *) malloc (stack->maxSize * sizeof (int));
  return stack;
}

// Checking with this function is stack is full or not
int stackFull (struct Stack *stack)
{
  if (stack->top == stack->maxSize - 1)
    {
      cout << "Will not be able to push maxSize reached\n";
    }
  // We know array index from 0 and maxSize starts from 1
  return stack->top == stack->maxSize - 1;
}

// if Stack is empty when top is equal to -1 and return true
int stackEmpty (struct Stack *stack)
{
  return stack->top == -1;
}

// Push function it inserts value in stack and increments stack top by 1
void pushElement (struct Stack *stack, int item)
{
  if (stackFull (stack))
    return;
  stack->array[++stack->top] = item;
}

// pop Function it remove an item from stack and decreases top by 1 
int popElement (struct Stack *stack)
{
  if (stackEmpty (stack))
    return INT_MIN;
  return stack->array[stack->top--];
}

// Function to return the top from stack without removing it 
int peekElement (struct Stack *stack)
{
  if (stackEmpty (stack))
    return INT_MIN;
  return stack->array[stack->top];
}

// A function check the given character is operand 
int checkOperand (char ch)
{
  return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

// Fucntion to compare precedence if 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 function for infix to postfix conversion 
int postfix (char *expression)
{
  int i, j;
  struct Stack *stack = create (strlen (expression));
  if (!stack)		
    return -1;

  for (i = 0, j = -1; expression[i]; ++i)
    {
      // checking the character we scanned is operand or not
      if (checkOperand (expression[i]))
	expression[++j] = expression[i];

      // if we scan character push it to the stack
      else if (expression[i] == '(')
	pushElement (stack, expression[i]);

      //if we scan character we need to pop and print from the stack  
      else if (expression[i] == ')')
	{
	  while (!stackEmpty (stack) && peekElement (stack) != '(')
	    expression[++j] = popElement (stack);
	  if (!stackEmpty (stack) && peekElement (stack) != '(')
	    return -1;		// invalid expression              
	  else
	    popElement (stack);
	}
      else			// if an operator
	{
	  while (!stackEmpty (stack)
		 && precedence (expression[i]) <=
		 precedence (peekElement (stack)))
	    expression[++j] = popElement (stack);
	  pushElement (stack, expression[i]);
	}

    }

  // if all first expression characters are scanned
  // adding all left elements from stack to expression
  while (!stackEmpty (stack))
    expression[++j] = popElement (stack);
    expression[++j] = '\0';
    
    return 0;
}

void reverse (char *exp)
{				//reverse function for expression

  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 conversionInfixToPrefix (char *exp)
{
  int size = strlen (exp);
  reverse (exp);
  brackets (exp);
  postfix (exp);
  reverse (exp);
}
Output:-
The infix expression is: 
(P+(Q*R)/(S-T))
The prefix expression is: 
+P/*QR-ST

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java