Cover Image for Program to convert infix to postfix expression in C++
74 views

Program to convert infix to postfix expression in C++

Converting an infix expression to a postfix expression (also known as Reverse Polish Notation or RPN) can be achieved using the stack data structure in C++. Here’s a C++ program to perform the conversion:

C++
#include <iostream>
#include <stack>
#include <string>

// Function to check if a character is an operator
bool isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

// Function to determine the precedence of an operator
int precedence(char c) {
    if (c == '+' || c == '-')
        return 1;
    if (c == '*' || c == '/')
        return 2;
    return 0; // Assuming '(' has the lowest precedence
}

// Function to convert infix expression to postfix
std::string infixToPostfix(const std::string& infix) {
    std::string postfix = "";
    std::stack<char> operatorStack;

    for (char c : infix) {
        if (isalnum(c)) {
            postfix += c; // If it's an operand, add to the postfix expression
        } else if (c == '(') {
            operatorStack.push(c); // Push '(' onto the stack
        } else if (c == ')') {
            // Pop operators from the stack and add to postfix until '(' is encountered
            while (!operatorStack.empty() && operatorStack.top() != '(') {
                postfix += operatorStack.top();
                operatorStack.pop();
            }
            // Pop '(' from the stack (removing the matching '(')
            if (!operatorStack.empty() && operatorStack.top() == '(') {
                operatorStack.pop();
            }
        } else if (isOperator(c)) {
            // Pop operators with higher or equal precedence from the stack and add to postfix
            while (!operatorStack.empty() && operatorStack.top() != '(' &&
                   precedence(c) <= precedence(operatorStack.top())) {
                postfix += operatorStack.top();
                operatorStack.pop();
            }
            // Push the current operator onto the stack
            operatorStack.push(c);
        }
    }

    // Pop any remaining operators from the stack and add to postfix
    while (!operatorStack.empty()) {
        postfix += operatorStack.top();
        operatorStack.pop();
    }

    return postfix;
}

int main() {
    std::string infixExpression;
    std::cout << "Enter an infix expression: ";
    std::cin >> infixExpression;

    std::string postfixExpression = infixToPostfix(infixExpression);
    std::cout << "Postfix expression: " << postfixExpression << std::endl;

    return 0;
}

In this program:

  1. isOperator function checks if a character is one of the four basic arithmetic operators: ‘+’, ‘-‘, ‘*’, or ‘/’.
  2. precedence function determines the precedence of operators. The higher the number returned, the higher the precedence.
  3. infixToPostfix function converts the infix expression to postfix using a stack to keep track of operators.
  4. The main function reads an infix expression, calls infixToPostfix to convert it to postfix, and then displays the resulting postfix expression.

Compile and run this program, and you can input infix expressions like “2 + 3 * (4 – 1)” and get the corresponding postfix expression as output.

YOU MAY ALSO LIKE...

The Tech Thunder

The Tech Thunder

The Tech Thunder


COMMENTS