Program to Convert Infix to Postfix Expression in C++ using the Stack Data Structure

Infix notation is the standard way of writing expressions that most people are familiar with. However, it can be difficult for computers to evaluate expressions in infix notation, so it is often converted to postfix notation first. This program demonstrates how to convert an infix expression to postfix notation using the stack data structure in C++.

Syntax

string infixToPostfix(string expression)

The function takes an infix expression as input and returns the corresponding postfix expression as a string.

Example

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

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

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

int main() {
    string expression = "(a+b)*c/d+e-f";
    cout << "Infix expression: " << expression << endl;
    cout << "Postfix expression: " << infixToPostfix(expression) << endl;
    return 0;
}

Output

Infix expression: (a+b)*c/d+e-f
Postfix expression: ab+c*d/e-f+

Explanation

In the above example, the input infix expression is (a+b)*c/d+e-f. Using the stack data structure, the program converts it to the postfix expression ab+c*d/e-f+. Here is the step by step explanation of the program logic:

1. Traverse the infix expression from left to right.
2. If the current character is a letter or a digit, add it to the postfix expression.
3. If the current character is an opening parenthesis, push it onto the stack.
4. If the current character is a closing parenthesis, pop characters from the stack and add them to the postfix expression until an opening parenthesis is found. Discard the opening parenthesis.
5. If the current character is an operator, pop operators from the stack and add them to the postfix expression until an operator with lower precedence is found. Push the current operator onto the stack.
6. After all characters have been processed, pop any remaining operators from the stack and add them to the postfix expression.

Use

Converting infix expressions to postfix expressions is useful for evaluating expressions in computer programs. Postfix expressions are easier to evaluate because the order of operations is unambiguous and there are no parentheses to deal with.

Important Points

• The precedence of operators (such as * and /) affects the order in which they are evaluated.
• Opening and closing parentheses affect the order in which operators are evaluated.
• The stack data structure is used to keep track of the operators in the infix expression.

Summary

In summary, this program demonstrates how to convert an infix expression to postfix notation using the stack data structure in C++. The resulting postfix expression is unambiguous and easier to evaluate than the original infix expression.