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, else remove it from the container
  (bottom → top: small → large)

  Because when a new element is smaller, it breaks the increasing order → you pop until order is restored.
  That popping tells you: “this new element is the next smaller for those popped elements.”

• Monotonic Decreasing Stack: elements are kept in decreasing order, else remove it from the container
  (bottom → top: large → small)

  Because when a new element is larger, it breaks the decreasing order → you pop.
  That popping means: “this new element is the next greater for those popped elements.”

When a new element breaks the order, we pop elements until the order is restored. The stack will always be sorted.

When you need to handle duplicates, store indices instaead of value.

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