C++ Program to Convert Infix Expression to Postfix Expression

1. Introduction

In computer science, infix notation is the standard arithmetic and logical formulation we use in our day-to-day lives, where operators are written between operands. For example: A + B. On the other hand, postfix notation, also known as Reverse Polish Notation (RPN), places the operator after the operands, like A B +. 

Postfix notation has the advantage that it does not require any parentheses as long as the number of operands for every operator is fixed. 

In this post, we will create a C++ program to convert an infix expression to a postfix expression using a stack data structure.

2. Program Overview

Our infix to postfix converter program will:

1. Utilize a stack to hold operators and ensure they are placed in the postfix expression in the correct order.

2. Iterate over the infix expression from left to right.

3. Place operands directly to the postfix expression.

4. Use the stack to manage operators and handle the precedence between them.

5. At the end of the iteration, pop any remaining operators from the stack to the postfix expression.

3. Code Program

#include<iostream>
#include<stack>
using namespace std;

int precedence(char op) {
    if(op == '^') return 3;
    else if(op == '*' || op == '/') return 2;
    else if(op == '+' || op == '-') return 1;
    return -1;
}

string infixToPostfix(string infix) {
    stack<char> s;
    string postfix = "";
    for(int i = 0; i < infix.length(); i++) {
        char c = infix[i];
        if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
            postfix += c;
        } else if(c == '(') {
            s.push(c);
        } else if(c == ')') {
            while(!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            if(!s.empty()) s.pop();
        } else {
            while(!s.empty() && precedence(s.top()) >= precedence(c)) {
                postfix += s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    while(!s.empty()) {
        postfix += s.top();
        s.pop();
    }
    return postfix;
}

int main() {
    string infix;
    cout << "Enter infix expression: ";
    cin >> infix;
    string postfix = infixToPostfix(infix);
    cout << "Postfix expression: " << postfix << endl;
    return 0;
}

Output:

Enter infix expression: A+B*(C^D-E)
Postfix expression: ABCD^E-*+

4. Step By Step Explanation

1. The precedence function determines the priority of operators.

2. In the infixToPostfix function:

- Operands (alphabets) are directly added to the postfix expression.- Operators are pushed onto the stack, but before pushing, higher or equal precedence operators at the top of the stack are popped to the postfix expression.- Parentheses are handled by pushing '(' onto the stack and popping operators for ')' until '(' is encountered.

3. At the end of the iteration, the remaining operators on the stack are popped to the postfix expression.

4. The main function is responsible for taking input from the user and displaying the converted postfix expression.