Infix to Postfix — Medium Problem & Solution

Problem statement

Convert the infix expression s to postfix (reverse Polish) notation, where every operator follows its two operands.

Operands are single characters — a letter or a digit. The operators are +, -, *, / and ^, and parentheses group sub-expressions. Precedence, from highest: ^, then * and /, then + and -. Operators of equal precedence group left to right, except ^, which groups right to left (a^b^c means a^(b^c)).

Return the postfix expression as a string with no spaces; parentheses never appear in it.

Example 1

Input: s = "a+b*c"
Output: "abc*+"

Example 2

Input: s = "(A-B)/C+D^E^F"
Output: "AB-C/DEF^^+"
Explanation: `^` is right-associative, so `D^E^F` becomes `DEF^^`.

Example 3

Input: s = "x-y-z"
Output: "xy-z-"
Explanation: `-` is left-associative: `(x-y)-z`.

Constraints

• 1 <= s.length <= 10^5
• s is a valid infix expression of single-character operands (letters or digits), the operators + - * / ^ and parentheses
• s contains no spaces

How to solve Infix to Postfix

The shunting-yard algorithm: operands stream to the output, operators wait on a stack until an operator of lower precedence (or a closing parenthesis) proves they must be applied first.

Approach

1. Scan s. An operand is appended to the output.
2. ( is pushed. ) pops operators to the output until the matching (, which is discarded.
3. For an operator o, pop to the output while the top is an operator with higher precedence than o, or equal precedence and o is left-associative. Then push o.
4. At the end, pop every remaining operator to the output.

Why it works

An operator on the stack is emitted exactly when its right operand is complete: a following operator of lower precedence (or equal, for left-associative ones) cannot bind tighter, so the stacked operator's sub-expression ends there. For ^, an equal-precedence ^ binds tighter (right-associativity), so the stacked one must wait. Parentheses act as a fence that makes the inner expression complete at ).

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Treating ^ as left-associative turns a^b^c into ab^c^.
• Never pop past a ( when handling an operator.
• Remember to flush the stack at the end of the input.

Reference solution

Python

def infixToPostfix(s: str) -> str:
    prec = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    out = []
    st = []
    for c in s:
        if c.isalnum():
            out.append(c)
        elif c == '(':
            st.append(c)
        elif c == ')':
            while st[-1] != '(':
                out.append(st.pop())
            st.pop()
        else:
            while st and st[-1] != '(' and (prec[st[-1]] > prec[c] or (prec[st[-1]] == prec[c] and c != '^')):
                out.append(st.pop())
            st.append(c)
    while st:
        out.append(st.pop())
    return ''.join(out)

JavaScript

var infixToPostfix = function(s) {
    var prec = { "+": 1, "-": 1, "*": 2, "/": 2, "^": 3 };
    var out = [], st = [];
    for (var i = 0; i < s.length; i++) {
        var c = s[i];
        if (/[A-Za-z0-9]/.test(c)) {
            out.push(c);
        } else if (c === "(") {
            st.push(c);
        } else if (c === ")") {
            while (st[st.length - 1] !== "(") out.push(st.pop());
            st.pop();
        } else {
            while (st.length > 0 && st[st.length - 1] !== "(") {
                var top = st[st.length - 1];
                if (prec[top] > prec[c] || (prec[top] === prec[c] && c !== "^")) out.push(st.pop());
                else break;
            }
            st.push(c);
        }
    }
    while (st.length > 0) out.push(st.pop());
    return out.join("");
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Ambiguous Coordinates Medium
• Generate Binary Strings Without Adjacent Zeros Medium
• Splitting a String Into Descending Consecutive Values Medium
• Letter Case Permutation Medium
• Lexicographically Smallest Equivalent String Medium
• Extra Characters in a String Medium