Infix To Postfix Conversion using Stack in C++

Infix To Postfix Conversion

In the process of Infix To Postfix Converting using Stack in C++, we will use the stack data structure. By scanning the infix expression from left to right, when we will get any operand, simply add them to the postfix form, and for the operator and parenthesis, add them in the stack maintaining the precedence of them.

C++ code for infix to postfix conversion

Basic:-

  • Infix Expression: The operator is in between the two operands
    • Example: A + B is known as infix expression.
  • Postfix Expression: The operator is after the two operands
    • Example: BD + is known as postfix expression.

Steps needed for infix to postfix conversion using stack in C++:-

  1. First Start scanning the expression from left to right
  2. If the scanned character is an operand, output it, i.e. print it
  3. Else
    • If the precedence of the scanned operator is higher than the precedence of the operator in the stack(or stack is empty or has'(‘), then push operator in the stack
    • Else, Pop all the operators, that have greater or equal precedence than the scanned operator. Once you pop them push this scanned operator. (If we see a parenthesis while popping then stop and push scanned operator in the stack)
  4. If the scanned character is an ‘(‘, push it to the stack.
  5. If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
  6. Now, we should repeat steps 2 – 6 until the whole infix i.e. whole characters are scanned.
  7. Print output
  8. Do the pop and output (print) until the stack is not empty

Below are two examples of how Infix to Postfix can be calculated –

Infix to Postfix Conversion in C++
Infix to postfix conversion in C++

Postfix expression over infix expression

  • In postfix any formula can be expressed without parenthesis.
  • It is very useful for evaluating formulas on computers with stacks.
  • Infix operators have precedence

Infix To Postfix Conversion using Stack in C++

We will look at the following three methods you can choose any of them as per your wish

  • Method 1: Stack implemented via inbuilt stack library in C++
  • Method 2: Stack created using custom class creation in C++
  • Method 3: Global array-based stack implementation

This method uses inbuilt stack library to create stack

// Using inbuilt stack library to create stack
#include <iostream>
#include <stack> using namespace std; int priority (char alpha){ if(alpha == '+' || alpha =='-') return 1; if(alpha == '*' || alpha =='/') return 2; if(alpha == '^') return 3; return 0; } string convert(string infix) { int i = 0; string postfix = ""; // using inbuilt stack< > from C++ stack library stack s; while(infix[i]!='\0') { // if operand add to the postfix expression if(infix[i]>='a' && infix[i]<='z'|| infix[i]>='A'&& infix[i]<='Z') { postfix += infix[i]; i++; } // if opening bracket then push the stack else if(infix[i]=='(') { s.push(infix[i]); i++; } // if closing bracket encounted then keep popping from stack until // closing a pair opening bracket is not encountered else if(infix[i]==')') { while(s.top()!='('){ postfix += s.top(); s.pop(); } s.pop(); i++; } else { while (!s.empty() && priority(infix[i]) <= priority(s.top())){ postfix += s.top(); s.pop(); } s.push(infix[i]); i++; } } while(!s.empty()){ postfix += s.top(); s.pop(); } cout << "Postfix is : " << postfix; //it will print postfix conversion return postfix; } int main() { string infix = "((a+(b*c))-d)"; string postfix; postfix = convert(infix); return 0; }

This method uses custom class for stack creation in C++

// custom class based stack implimentation
#include <bits/stdc++.h>
using namespace std;

class Stack {
    int top;
    int MAX;
    int* a;
 
public:

    Stack(int size){
        top = -1;
        MAX = size;
        a = new int [MAX];
    }
    bool push(int x);
    int pop();
    int peek();
    bool isEmpty();
    bool isFull();
};

bool Stack::isEmpty(){
    return (top < 0); 
}
bool Stack::isFull(){
return (top == MAX - 1);
}
int Stack::peek(){
return a[top];
}
bool Stack::push(int x) {
if (top >= (MAX - 1)) { cout << "Stack Overflow"; return false; } else { top++; a[top] = x; return true; } } int Stack::pop() { if (top < 0) { cout << "Stack Underflow";
return INT_MIN;
}
else {
int x = a[top];
top--; return x;
}
}

int priority (char alpha)
{
if(alpha == '+' || alpha =='-')
return 1;
if(alpha == '*' || alpha =='/')
return 2;
if(alpha == '^')
return 3;

return 0;
}

string convert(string infix)
{
int i = 0;
string postfix = "";

Stack s(20);
while(infix[i]!='\0')
{
// if operand add to the postfix expression
if(infix[i]>='a' && infix[i]<='z'|| infix[i]>='A'&& infix[i]<='Z') { postfix += infix[i]; i++; } // if opening bracket then push the stack else if(infix[i]=='(') { s.push(infix[i]); i++; } // if closing bracket encounted then keep popping from stack until // closing a pair opening bracket is not encountered else if(infix[i]==')') { while(s.peek()!='(') postfix += s.pop(); s.pop(); i++; } else { while (!s.isEmpty() && priority(infix[i]) <= priority(s.peek())){ postfix += s.pop(); } s.push(infix[i]); i++; } } while(!s.isEmpty()){ postfix += s.pop(); } cout << "Postfix is : " << postfix; //it will print postfix conversion return postfix; } // Note can also use std::string::insert to add to string // check here - https://www.cplusplus.com/reference/string/string/insert/ // the expression : postfix += infix[i] can also be written as // postfix.insert(postfix.end(),infix[i]); int main() { string infix = "((a+(b*c))-d)"; string postfix; postfix = convert(infix); return 0; }

This method uses global array implementation of stack in C++

// global array based stack implementation
#include<iostream>
#include<string>
#define MAX 20 using namespace std; char stk[20]; int top = -1; bool isEmpty(){ return top == -1; } bool isFull(){ return top == MAX - 1; } char peek(){ return stk[top]; } // Push function here, inserts value in stack and increments stack top by 1 void push(char oper){ if(isFull()) cout << "Stack Full!!!!"; else{ top++; stk[top] = oper; } } // Function to remove an item from stack. It decreases top by 1 char pop(){ if(isEmpty()) cout << "Stack Empty!!!!";
else{
char ch = stk[top];
top--; return(ch);
}
return 0;
}
int priority (char alpha)
{
if(alpha == '+' || alpha =='-')
return 1;
if(alpha == '*' || alpha =='/')
return 2;
if(alpha == '^')
return 3;

return 0;
}

string convert(string infix)
{
int i=0;
string postfix = "";

while(infix[i]!='\0')
{

// if operand add to the postfix expression
if(infix[i]>='a' && infix[i]<='z'|| infix[i]>='A'&& infix[i]<='Z') { postfix += infix[i]; i++; } // if opening bracket then push the stack else if(infix[i]=='(') { push(infix[i]); i++; } // if closing bracket encounted then keep popping from stack until // closing a pair opening bracket is not encountered else if(infix[i]==')') { while(stk[top]!='(') postfix += pop(); pop(); i++; } else { while (!isEmpty() && priority(infix[i]) <= priority(peek())){ postfix += pop(); } push(infix[i]); i++; } } while(!isEmpty()){ postfix += pop(); } cout << "Postfix is : " << postfix; //it will print postfix conversion return postfix; } // Note can also use std::string::insert to add to string // check here - https://www.cplusplus.com/reference/string/string/insert/ // the expression : postfix += infix[i] can also be written as // postfix.insert(postfix.end(),infix[i]); int main() { string infix = "((a+(b*c))-d)"; string postfix; postfix = convert(infix); return 0; }

Output

Postfix is : abc*+d-