Infix to Postfix

Medium
1420.

Infix to Postfix

Infix to Postfix is a medium coding problem on strings and stack, asked in Amazon, Microsoft, TCS and Samsung interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var infixToPostfix = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Infix to Postfix — Solution in Python, Java & C++

Infix to Postfix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings and stack.

Infix to Postfix is a medium coding problem on strings and stack, asked in Amazon, Microsoft, TCS and Samsung interviews.

  • Difficulty: Medium
  • Topics: Strings, Stack
  • Asked at: Amazon, Microsoft, TCS, Samsung
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Infix to Postfix

  1. Hint 1

    Operands go straight to the output in the order they appear; only the operators need reordering.

  2. Hint 2

    Hold operators on a stack. Before pushing a new operator, which operators already on the stack must be emitted first?

  3. Hint 3

    Pop operators with higher precedence, and those with equal precedence when the new operator is left-associative (not ^); stop at (. A ) pops until its (.

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)

Java

private static int precOf(char c) {
    if (c == '^') return 3;
    if (c == '*' || c == '/') return 2;
    if (c == '+' || c == '-') return 1;
    return 0;
}

public static String infixToPostfix(String s) {
    StringBuilder out = new StringBuilder();
    char[] st = new char[s.length() + 1];
    int top = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isLetterOrDigit(c)) {
            out.append(c);
        } else if (c == '(') {
            st[top++] = c;
        } else if (c == ')') {
            while (st[top - 1] != '(') out.append(st[--top]);
            top--;
        } else {
            while (top > 0 && st[top - 1] != '(' && (precOf(st[top - 1]) > precOf(c) || (precOf(st[top - 1]) == precOf(c) && c != '^'))) {
                out.append(st[--top]);
            }
            st[top++] = c;
        }
    }
    while (top > 0) out.append(st[--top]);
    return out.toString();
}

C++

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

string infixToPostfix(string s) {
    string out;
    vector<char> st;
    for (char c : s) {
        if (isalnum((unsigned char)c)) {
            out += c;
        } else if (c == '(') {
            st.push_back(c);
        } else if (c == ')') {
            while (st.back() != '(') { out += st.back(); st.pop_back(); }
            st.pop_back();
        } else {
            while (!st.empty() && st.back() != '(' && (precOf(st.back()) > precOf(c) || (precOf(st.back()) == precOf(c) && c != '^'))) {
                out += st.back();
                st.pop_back();
            }
            st.push_back(c);
        }
    }
    while (!st.empty()) { out += st.back(); st.pop_back(); }
    return 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure