Stack

Implmentation

• For stack implementation top begin with -1.
• For queue implementation front begin with 0 and rear begin with -1.

Infix → Postfix (Shunting Yard using Stack)

• If operand → add to result
• If ( → push to stack
• If ) → pop until (
• If operator → pop higher or equal precedence operators first

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

string infixToPostfix(string s) {
    stack<char> st;
    string result = "";

    for (char c : s) {

        // If operand
        if (isalnum(c)) {
            result += c;
        }

        // If '('
        else if (c == '(') {
            st.push(c);
        }

        // If ')'
        else if (c == ')') {
            while (!st.empty() && st.top() != '(') {
                result += st.top();
                st.pop();
            }
            st.pop(); // remove '('
        }

        // Operator
        else {
            while (!st.empty() && ((precedence(st.top()) > precedence(ch)) || (precedence(st.top()) == precedence(ch) && ch != '^'))) {
                result += st.top();
                st.pop();
            }
            st.push(c);
        }
    }

    while (!st.empty()) {
        result += st.top();
        st.pop();
    }

    return result;
}

Stack Trace

Step	Token	Stack	Result
1	A	[]	A
2	+	+	A
3	B	+	AB
4	*	+ *	AB
5	(	+ * (	AB
6	C	+ * (	ABC
7	-	+ * ( -	ABC
8	D	+ * ( -	ABCD
9	)	+ *	ABCD-
10	end	[]	ABCD-*+

Infix → Prefix

• Reverse string
• Swap ( and )
• Convert to Postfix
• Reverse result

string infixToPrefix(string s) {

    reverse(s.begin(), s.end());

    // Swap brackets
    for (char &c : s) {
        if (c == '(') c = ')';
        else if (c == ')') c = '(';
    }

    string postfix = infixToPostfix(s);

    reverse(postfix.begin(), postfix.end());

    return postfix;
}

Why this works

What changes in prefix vs postfix?

The difference is only where the operator appears:

Notation	Operator position
Infix	middle
Postfix	end
Prefix	start

Every expression is actually an expression tree:

      +
     / \
    A   *
       / \
      B   C

Traversals

Form	Tree traversal
Prefix	Preorder (Root → Left → Right)
Postfix	Postorder (Left → Right → Root)
Infix	Inorder

Why postfix is easier

• Postfix respects natural evaluation order: A B C * +
• You always see: operands first → operator later. So stack works naturally.

Reverse of infix expression became mirrored. Swapping (, ) make it complete mirror, so perform postorder of the mirror tree, and eventually reverse the mirrorred expression to get the exact result.

Postfix → Infix

• If operand → push as string
• If operator → pop two operands
• Form: (operand1 operator operand2)
• Push back

string postfixToInfix(string s) {
    stack<string> st;

    for (char c : s) {

        if (isalnum(c)) {
            st.push(string(1, c));
        }
        else {
            string op2 = st.top(); st.pop();
            string op1 = st.top(); st.pop();

            string temp = "(" + op1 + c + op2 + ")";
            st.push(temp);
        }
    }

    return st.top();
}

Prefix → Infix

• Traverse from right to left
• Same logic as postfix

string prefixToInfix(string s) {
    stack<string> st;

    for (int i = s.length() - 1; i >= 0; i--) {

        char c = s[i];

        if (isalnum(c)) {
            st.push(string(1, c));
        }
        else {
            string op1 = st.top(); st.pop();
            string op2 = st.top(); st.pop();

            string temp = "(" + op1 + c + op2 + ")";
            st.push(temp);
        }
    }

    return st.top();
}

Summary

Conversion	Method Used
Infix → Postfix	Stack + Precedence
Infix → Prefix	Reverse + Postfix
Postfix → Infix	Stack (L→R)
Prefix → Infix	Stack (R→L)

Monotonic Stack

A monotonic stack is just a normal stack with one extra rule:

• Monotonic Increasing Stack: elements are kept in increasing order
  (bottom → top: small → large)
• Monotonic Decreasing Stack: elements are kept in decreasing order
  (bottom → top: large → small)

When a new element breaks the order, we pop elements until the order is restored.

When processing an element:

1. Compare it with stack top
2. If it breaks monotonic order → pop
3. After popping, push current element
4. While popping, we often compute answers