L3. Prefix, Infix, and Postfix Conversion | Stack and Queue Playlist

Arithmetic expressions form the foundation of how mathematical operations are parsed, evaluated, and compiled across programming languages and computer architectures. This chapter explores operators, operands, operator priority, and the structural transformations between Infix, Prefix (Polish Notation), and Postfix (Reverse Polish Notation) expressions using stacks.

1. Why Do We Need Expression Conversions?

Computers evaluate arithmetic expressions differently than humans. While human readers easily interpret standard mathematical notation where operators sit comfortably between numbers, compilers and stack-based calculators require rigid, ambiguity-free formatting to evaluate expressions without relying on complex operator precedence rules or parentheses.

• Infix Notation: Human-readable, heavily used in high-level programming languages (C++, Java, Python) where operators appear between operands (A + B). Requires explicit parenthesis handling and priority checks.
• Postfix Notation (RPN): Used in stack-based calculators and virtual machines. Operators appear after operands (A B +), eliminating the need for parentheses entirely.
• Prefix Notation (Polish Notation): Used in functional programming languages like Lisp and tree data structures. Operators appear before operands (+ A B).

2. Core Mental Model: Operators, Operands, and Priority

Before performing conversions, we must establish the basic building blocks of arithmetic expressions and their binding strengths.

Operators and Operands

• Operators: Symbols that dictate actions, such as exponentiation (^), multiplication (*), division (/), addition (+), and subtraction (-).
• Operands: The targets of the operators, typically represented by alphabetic characters (A to Z, a to z) and numeric digits (0 to 9).

Priority Order of Operators

Operators are processed based on their precedence. Higher priority operators must be evaluated before lower priority ones.

3. The Three Expression Formats Compared

Consider the standard infix expression: A + B * (C ^ D - E). Depending on where the operators are placed relative to their operands, the expression transforms:

• Infix: A + B * (C ^ D - E) (Operators reside in between operands)
• Prefix: + A * B - ^ C D E (Operators precede operands)
• Postfix: A B C D ^ E - * + (Operators follow operands)

4. Infix to Postfix Conversion Algorithm

To convert an infix expression to a postfix expression, we iterate through the expression from left to right using a Stack to hold operators and an Answer String to accumulate the result.

Step-by-Step Execution Rules

1. Operand Encountered: Append directly to the answer string. Do not push to the stack.
2. Opening Bracket ( Encountered: Push immediately onto the stack.
3. Closing Bracket ) Encountered: Pop operators from the stack and append them to the answer string until an opening bracket ( is encountered. Discard both brackets.
4. Operator Encountered:
   • While the stack is not empty and the top of the stack has greater than or equal priority compared to the current operator, pop from the stack and append to the answer.
   • Push the current operator onto the stack.
5. End of String: Pop all remaining operators from the stack and append them to the answer.

Code Implementation (Infix to Postfix)

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

string infixToPostfix(string s) {
    int i = 0;
    stack<char> st;
    string ans = "";
    
    while (i < s.length()) {
        char ch = s[i];
        
        // Check if operand (alphanumeric)
        if ((ch >= 'A' && ch <= 'Z') || 
            (ch >= 'a' && ch <= 'z') || 
            (ch >= '0' && ch <= '9')) {
            ans += ch;
        }
        else if (ch == '(') {
            st.push(ch);
        }
        else if (ch == ')') {
            while (!st.empty() && st.top() != '(') {
                ans += st.top();
                st.pop();
            }
            if (!st.empty()) st.pop(); // Pop opening bracket
        }
        else { // Operator encountered
            while (!st.empty() && getPriority(ch) <= getPriority(st.top())) {
                ans += st.top();
                st.pop();
            }
            st.push(ch);
        }
        i++;
    }
    
    while (!st.empty()) {
        ans += st.top();
        st.pop();
    }
    
    return ans;
}

5. Infix to Prefix Conversion Algorithm

Converting infix to prefix requires a controlled three-step transformation process to account for right-to-left evaluation order.

The 3-Step Transformation Workflow

1. Reverse the Infix String: Reverse the characters from right to left. During reversal, swap brackets: convert every opening bracket ( to a closing bracket ) and vice versa.
2. Modified Postfix Conversion: Run a modified postfix conversion algorithm on the reversed string. When evaluating operator priorities, handle exponentiation ^ strictly (pop only when strictly greater, or handle equal-priority rules carefully to maintain correct right-associativity).
3. Reverse the Result: Reverse the resulting string to obtain the final prefix expression.

Code Implementation (Infix to Prefix)

string infixToPrefix(string s) {
    // Step 1: Reverse string and swap brackets
    string rev = "";
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s[i] == '(') rev += ')';
        else if (s[i] == ')') rev += '(';
        else rev += s[i];
    }
    
    // Step 2: Run modified postfix conversion on reversed string
    stack<char> st;
    string ans = "";
    int i = 0;
    
    while (i < rev.length()) {
        char ch = rev[i];
        if (isalnum(ch)) {
            ans += ch;
        }
        else if (ch == '(') {
            st.push(ch);
        }
        else if (ch == ')') {
            while (!st.empty() && st.top() != '(') {
                ans += st.top();
                st.pop();
            }
            if (!st.empty()) st.pop();
        }
        else {
            // For prefix, handle power operator with strict inequality
            while (!st.empty() && getPriority(ch) < getPriority(st.top())) {
                ans += st.top();
                st.pop();
            }
            st.push(ch);
        }
        i++;
    }
    
    while (!st.empty()) {
        ans += st.top();
        st.pop();
    }
    
    // Step 3: Reverse final answer string
    reverse(ans.begin(), ans.end());
    return ans;
}

6. Postfix to Infix Conversion Algorithm

To convert a postfix expression back into human-readable infix notation, we scan from left to right using a stack that stores strings rather than individual characters.

Step-by-Step Flow Walkthrough

1. Operand Encountered: Push it directly onto the stack as a string.
2. Operator Encountered:
   • Pop the top element as T1 (First Top).
   • Pop the next element as T2 (Second Top).
   • Form a new combined string: (T2 + Operator + T1).
   • Push the new string back onto the stack.
3. Completion: The sole remaining element in the stack is the complete Infix expression.

Code Implementation (Postfix to Infix)

string postfixToInfix(string exp) {
    stack<string> st;
    int i = 0;
    
    while (i < exp.length()) {
        char ch = exp[i];
        
        if (isalnum(ch)) {
            st.push(string(1, ch));
        } else {
            string t1 = st.top(); st.pop();
            string t2 = st.top(); st.pop();
            string con = "(" + t2 + ch + t1 + ")";
            st.push(con);
        }
        i++;
    }
    return st.top();
}

7. Prefix to Infix Conversion Algorithm

Prefix to Infix conversion is similar to Postfix to Infix, with two key differences: iterate from right to left, and combine operands as (T1 + Operator + T2) where T1 is popped first.

Execution Summary

1. Iterate backwards from N - 1 down to 0.
2. If an operand is encountered, push it onto the string stack.
3. If an operator is encountered:
   • Pop T1 (Top 1).
   • Pop T2 (Top 2).
   • Construct string: (T1 + Operator + T2).
   • Push back onto the stack.

8. Postfix to Prefix Conversion Algorithm

Converting a Postfix expression directly to a Prefix expression scans left to right using a string stack without wrapping expressions in parentheses.

Execution Rules

1. Operand Encountered: Push onto the stack.
2. Operator Encountered:
   • Pop T1 (Top 1).
   • Pop T2 (Top 2).
   • Form combined string: Operator + T2 + T1.
   • Push back onto the stack.

string postfixToPrefix(string exp) {
    stack<string> st;
    int i = 0;
    
    while (i < exp.length()) {
        char ch = exp[i];
        if (isalnum(ch)) {
            st.push(string(1, ch));
        } else {
            string t1 = st.top(); st.pop();
            string t2 = st.top(); st.pop();
            string con = ch + t2 + t1;
            st.push(con);
        }
        i++;
    }
    return st.top();
}

9. Prefix to Postfix Conversion Algorithm

Prefix to Postfix conversion scans right to left using a string stack.

Execution Rules

1. Iterate backwards from N - 1 down to 0.
2. Operand Encountered: Push onto stack.
3. Operator Encountered:
   • Pop T1 (Top 1).
   • Pop T2 (Top 2).
   • Form combined string: T1 + T2 + Operator.
   • Push back onto stack.

string prefixToPostfix(string exp) {
    stack<string> st;
    int i = exp.length() - 1;
    
    while (i >= 0) {
        char ch = exp[i];
        if (isalnum(ch)) {
            st.push(string(1, ch));
        } else {
            string t1 = st.top(); st.pop();
            string t2 = st.top(); st.pop();
            string con = t1 + t2 + ch;
            st.push(con);
        }
        i--;
    }
    return st.top();
}

10. Summary and Master Complexity Matrix

The following table synthesizes the time and space complexities across all six arithmetic expression conversions.

Summary and Key Takeaways

• Operators & Operands: Operators (+, -, *, /, ^) act upon operands (A-Z, 0-9) following strict precedence rules.
• Precedence Hierarchy: Exponentiation (3) > Multiplication/Division (2) > Addition/Subtraction (1).
• Infix Notation: Standard human-readable format with operators placed between operands, requiring operator precedence rules and parentheses.
• Postfix Notation: Eliminates parentheses by placing operators after operands, ideal for stack-based machine evaluation.
• Prefix Notation: Places operators before operands, frequently used in functional languages and expression trees.
• Stack Data Structure: Serves as the core engine for all conversions, temporarily holding operators or sub-expression strings during parsing.
• String Concatenation Impact: In expression-to-expression conversions (e.g., Postfix to Infix), string building can scale up to $O(N^2)$ in languages with immutable strings due to repeated reallocation.
• Interview Perspective: While direct memorization formulas are rarely tested in isolation, mastering these algorithms builds robust stack manipulation intuition applicable across complex parsing problems.