Topic 4

Infix to Postfix Conversion

Expression Conversion using Stack

Infix: Operators are between operands. e.g., A + B * C

Postfix: Operators are after operands. e.g., A B C * + (Computers love this because it removes the need for parentheses and precedence rules).

We use a Stack to temporarily hold operators and left parentheses while we process the expression from left to right.

Algorithm Rules

  1. If character is an Operand (A-Z, 0-9): Add it directly to the Postfix string.
  2. If character is a Left Parenthesis '(': Push it onto the stack.
  3. If character is a Right Parenthesis ')': Pop operators from the stack and add to Postfix until a '(' is found. Discard the '(' and ')'.
  4. If character is an Operator (+, -, *, /, ^):
    • While stack is not empty and precedence of top operator >= precedence of current operator, Pop and add to Postfix.
    • Then Push the current operator onto the stack.
  5. At end of expression, Pop any remaining operators from the stack into Postfix.
⚖️
Precedence: ^ (Highest) > * , / > + , - (Lowest)
📦
Stack only holds: Operators and Parentheses. Operands NEVER go into the stack for this conversion.
infix-postfix
#include <iostream>
#include <stack>
using namespace std;

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

bool isOperator(char ch) {
    return (ch == '+' || ch == '-' ||
            ch == '*' || ch == '/' || ch == '^');
}

string infixToPostfix(string infix) {
    stack<char> s;
    string postfix = "";

    for (char ch : infix) {
        if (isalnum(ch)) {
            postfix += ch;           // Operand -> output
        }
        else if (ch == '(') {
            s.push(ch);              // '(' -> push
        }
        else if (ch == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            s.pop();                 // Pop '('
        }
        else if (isOperator(ch)) {
            while (!s.empty() &&
                   precedence(s.top()) >= precedence(ch)) {
                postfix += s.top();
                s.pop();
            }
            s.push(ch);
        }
    }

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

    return postfix;
}

int main() {
    string infix = "A+B*(C^D-E)";
    cout << "Infix:   " << infix << endl;
    cout << "Postfix: " << infixToPostfix(infix) << endl;
    // Output: ABCD^E-*+
    return 0;
}