C++ Program to Convert Infix Expression to Postfix

by

Converting infix expressions (where operators are between operands, such as A+B) to postfix expressions (where operators follow their operands, such as AB+) is a fundamental problem in computer science, especially in the fields of compiler construction and expression evaluation. This process simplifies the parsing and evaluation of expressions. In this comprehensive guide, we will explore different methods to convert infix expressions to postfix using C++. We will cover three distinct solutions, each with detailed explanations and outputs. Before diving into the examples, let’s review the prerequisites necessary for this article.

Prerequisites

To follow along with this guide, you should have:

  • Basic knowledge of C++ programming
  • A C++ compiler installed on your machine
  • Familiarity with stack data structures and standard template libraries (STL)

1. Using Stack Data Structure

1.1. Example 1: Basic Conversion

In this example, we will use a stack to convert a simple infix expression to a postfix expression.

Code

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

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

std::string infixToPostfix(const std::string &infix) {
    std::stack<char> stack;
    std::string postfix;

    for (char ch : infix) {
        if (isalnum(ch)) {
            postfix += ch;
        } else if (ch == '(') {
            stack.push(ch);
        } else if (ch == ')') {
            while (!stack.empty() && stack.top() != '(') {
                postfix += stack.top();
                stack.pop();
            }
            stack.pop();
        } else {
            while (!stack.empty() && precedence(stack.top()) >= precedence(ch)) {
                postfix += stack.top();
                stack.pop();
            }
            stack.push(ch);
        }
    }

    while (!stack.empty()) {
        postfix += stack.top();
        stack.pop();
    }

    return postfix;
}

int main() {
    std::string infix = "A+B*C";
    std::string postfix = infixToPostfix(infix);
    std::cout << "Postfix expression: " << postfix << std::endl;
    return 0;
}

Explanation

  • Precedence Function: We define a function to return the precedence of operators.
  • Conversion Function: We define the infixToPostfix function to convert the infix expression to postfix using a stack.
  • Stack Operations: The function uses stack operations to manage the precedence of operators and parentheses.
  • Testing: We test the function with the expression “A+B*C” and print the result.

Output

C++
Postfix expression: ABC*+

1.2. Example 2: Handling Multiple Operators

In this example, we extend the previous function to handle more complex expressions with multiple operators and parentheses.

Code

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

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

std::string infixToPostfix(const std::string &infix) {
    std::stack<char> stack;
    std::string postfix;

    for (char ch : infix) {
        if (isalnum(ch)) {
            postfix += ch;
        } else if (ch == '(') {
            stack.push(ch);
        } else if (ch == ')') {
            while (!stack.empty() && stack.top() != '(') {
                postfix += stack.top();
                stack.pop();
            }
            stack.pop();
        } else {
            while (!stack.empty() && precedence(stack.top()) >= precedence(ch)) {
                postfix += stack.top();
                stack.pop();
            }
            stack.push(ch);
        }
    }

    while (!stack.empty()) {
        postfix += stack.top();
        stack.pop();
    }

    return postfix;
}

int main() {
    std::string infix = "(A+B)*C-(D-E)*(F+G)";
    std::string postfix = infixToPostfix(infix);
    std::cout << "Postfix expression: " << postfix << std::endl;
    return 0;
}

Explanation

  • Enhanced Expression: We use the same functions as in Example 1 but test them with a more complex expression.
  • Testing: We test the function with the expression “(A+B)C-(D-E)(F+G)” and print the result.

Output

C++
Postfix expression: AB+C*DE-FG+*-

2. Using Class and Inheritance

2.1. Example 3: Class-Based Conversion

In this example, we encapsulate the logic for converting infix expressions to postfix within a class.

Code

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

class InfixToPostfixConverter {
private:
    int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0;
    }

public:
    std::string convert(const std::string &infix) {
        std::stack<char> stack;
        std::string postfix;

        for (char ch : infix) {
            if (isalnum(ch)) {
                postfix += ch;
            } else if (ch == '(') {
                stack.push(ch);
            } else if (ch == ')') {
                while (!stack.empty() && stack.top() != '(') {
                    postfix += stack.top();
                    stack.pop();
                }
                stack.pop();
            } else {
                while (!stack.empty() && precedence(stack.top()) >= precedence(ch)) {
                    postfix += stack.top();
                    stack.pop();
                }
                stack.push(ch);
            }
        }

        while (!stack.empty()) {
            postfix += stack.top();
            stack.pop();
        }

        return postfix;
    }
};

int main() {
    InfixToPostfixConverter converter;
    std::string infix = "A+(B*C-(D/E^F)*G)*H";
    std::string postfix = converter.convert(infix);
    std::cout << "Postfix expression: " << postfix << std::endl;
    return 0;
}

Explanation

  • Class Definition: We define a class InfixToPostfixConverter with a method convert to encapsulate the logic.
  • Conversion Method: The convert method performs the infix to postfix conversion.
  • Testing: We test the class with the expression “A+(B*C-(D/E^F)*G)*H” and print the result.

Output

C++
Postfix expression: ABC*DEF^/G*-H*+

Conclusion

In this comprehensive guide, we explored various methods to convert infix expressions to postfix using C++. We demonstrated how to use a stack data structure for simple and complex expressions and encapsulated the logic using a class-based approach. Each method offers a unique approach to solving the problem, catering to different needs and complexities. By mastering these techniques, you can efficiently convert infix expressions to postfix in C++, enhancing your data processing and algorithm development skills.