Editor

Infix to Postfix

#610 · Stacks and queues · Intermediate · 90 XP · about 18 min

We usually write formulas in infix form, with each operator between its two operands, like A+B*C. In postfix form every operator comes after its operands, and brackets are never needed: A+B*C becomes ABC*+. A stack of operators does the conversion.

Write to_postfix(expression) that converts an infix expression to postfix and returns it as a string with no spaces.

  • Operands are single letters or single digits.
  • The operators are +, -, * and /. * and / are done before + and -, and operators of the same rank are done from left to right.
  • Round brackets ( and ) group parts of the expression.
  • Spaces in expression are ignored.

Examples

to_postfix('A+B*C')      # returns 'ABC*+'
to_postfix('(A+B)*C')    # returns 'AB+C*'
to_postfix('A-B+C')      # returns 'AB-C+'
to_postfix('A*(B+C)/D')  # returns 'ABC+*D/'

In A-B+C the minus comes first, so it is applied first: AB- then C+.

Constraints

  • expression is always a valid infix expression of at most 10,000 characters.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.