39-Infix-to-Postfix.md

Infix to Postfix

Problem Link

Practice Problem

---

Pattern

• Stack
• Expression Conversion

---

Approach

Use operator precedence and a stack to convert infix expressions into postfix notation.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    private int precedence(char c) {
        if (c == '+' || c == '-') return 1;
        if (c == '*' || c == '/') return 2;
        return 0;
    }

    public String infixToPostfix(String s) {
        StringBuilder ans = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) ans.append(c);
            else if (c == '(') stack.push(c);
            else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') ans.append(stack.pop());
                stack.pop();
            } else {
                while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(c)) ans.append(stack.pop());
                stack.push(c);
            }
        }
        while (!stack.isEmpty()) ans.append(stack.pop());
        return ans.toString();
    }
}