Installation and Configuration
Programming Methodology

Infix to Postfix Expression Conversion Using Stack in C++

In this C++ exercise, you will develop a program that converts an infix expression (e.g., A + B) to a postfix expression (e.g., A B +) using a stack. Infix expressions are the standard way of writing mathematical expressions, while postfix expressions are more efficient for evaluation in computer systems. The goal of this exercise is to implement an algorithm that handles the precedence of operators and uses a stack to store intermediate results during the conversion process.

Group

Data Structures: Stacks, Queues in C++

Objective

1. Write a program that reads an infix expression.
2. Use a stack to help convert the infix expression to a postfix expression.
3. Implement operator precedence to ensure correct conversion.
4. Output the resulting postfix expression.

Develop a program that converts an infix expression to postfix using a stack.

Example C++ Exercise

 Copy C++ Code 
#include <iostream> // Include for input/output operations
#include <stack>     // Include for stack data structure
#include <cctype>    // Include for isdigit and isalpha functions
#include <string>    // Include for string handling

using namespace std;

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

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

// Function to convert infix expression to postfix
string infixToPostfix(string infix) {
    stack<char> s;   // Stack to store operators
    string postfix = "";  // String to store the postfix expression

    for (int i = 0; i < infix.length(); i++) {
        char c = infix[i];

        // If the character is an operand (letter or digit), add it to the postfix expression
        if (isalnum(c)) {
            postfix += c;
        }
        // If the character is an open parenthesis, push it to the stack
        else if (c == '(') {
            s.push(c);
        }
        // If the character is a closing parenthesis, pop from the stack to the postfix expression until an open parenthesis is found
        else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            s.pop(); // Pop the open parenthesis
        }
        // If the character is an operator, pop operators with higher or equal precedence and add them to the postfix expression
        else if (isOperator(c)) {
            while (!s.empty() && precedence(s.top()) >= precedence(c)) {
                postfix += s.top();
                s.pop();
            }
            s.push(c); // Push the current operator to the stack
        }
    }

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

    return postfix;
}

// Main function
int main() {
    string infix;
    cout << "Enter an infix expression: ";
    getline(cin, infix); // Read the entire line as an infix expression

    string postfix = infixToPostfix(infix); // Convert the infix expression to postfix

    cout << "Postfix expression: " << postfix << endl; // Output the result
    return 0;
}

 Output

Enter an infix expression: A+(B*C-D)
Postfix expression: ABC*D-+

Share this C++ Exercise


More C++ Programming Exercises of Data Structures: Stacks, Queues in C++

Explore our set of C++ Programming Exercises! Specifically designed for beginners, these exercises will help you develop a solid understanding of the basics of C++. From variables and data types to control structures and simple functions, each exercise is crafted to challenge you incrementally as you build confidence in coding in C++.