Infix to Postfix

Problem

Convert a list of expression tokens from infix order to postfix (reverse Polish) order and return the resulting token list.

Use the shunting-yard rule: operands go straight to the output, operators wait on a stack until lower or equal precedence operators are popped, and parentheses control the stack. Operators + and - share precedence, with * and / higher, and all are left-associative.

Hint

Left-associative equal precedence is what makes the comparison greater-or-equal.

Test cases

case 1

in: [["A","+","B","*","C"]]

expected: ["A","B","C","*","+"]

case 2

in: [["(","A","+","B",")","*","C"]]

expected: ["A","B","+","C","*"]

case 3

in: [["A","+","B"]]

expected: ["A","B","+"]

case 4

in: [["A"]]

expected: ["A"]

case 5

in: [["A","*","B","+","C","*","D"]]

expected: ["A","B","*","C","D","*","+"]

Starter codePython

def infix_to_postfix(tokens):
    # Your code here
    pass

5 test cases · run your code against them in the editor