Skip to content
Onsite
12 / 28

Infix to Postfix

MediumP3Coding

Convert an infix expression to postfix (reverse Polish) notation and return it as a string.

  • Operands are single lowercase letters or digits.
  • Operators are +, -, *, / and ^. Precedence from lowest to highest: + and - (equal), * and / (equal), ^.
  • +, -, *, / are left-associative; ^ is right-associative.
  • Parentheses ( and ) group sub-expressions.

The expression contains no spaces and is always valid. The output has no spaces either.

Example 1

Input
expr = "a+b*c"
Output
"abc*+"

Example 2

Input
expr = "(a+b)*c"
Output
"ab+c*"

Example 3

Input
expr = "a^b^c"
Output
"abc^^"

Constraints

  • 1 <= expr.length <= 10^4
  • The expression is valid

Hints

Run checks the 3 visible tests, Submit all 12.