Workspace

Problem workspace

3 day streakD

Infix to Postfix

MediumStacksExpressions & parsing

The challenge

Convert a valid infix expression into space-separated postfix tokens.

Space-separated integer operands, parentheses, and binary + - * /. All operators are left-associative; unary minus is not supported.

Example

3 + 4 * ( 2 - 1 ) → 3 4 2 1 - * +.

Use the walkthrough below to inspect the input and each state change.

See Infix to Postfix, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.30+142*3(425-617)8Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 14

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: ["3","+","4","*","(","2","-","1",")"]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

Pop higher or equal precedence operators before pushing the next operator.

Indices are zero-based. C++ uses C++17 or later.

def solve(tokens):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    operators, output = [], []
    for token in tokens:
        if token.isdigit(): output.append(token)
        elif token == '(': operators.append(token)
        elif token == ')':
            while operators[-1] != '(':
                output.append(operators.pop())
            operators.pop()
        else:
            while (operators and operators[-1] != '(' and
                   precedence[operators[-1]] >= precedence[token]):
                output.append(operators.pop())
            operators.append(token)
    while operators:
        output.append(operators.pop())
    return ' '.join(output)

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap