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
- 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)
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
string solve(const vector<string>& tokens) {
vector<string> operators, output;
auto precedence = [](const string& op) { return op == "+" || op == "-" ? 1 : 2; };
auto pop = [&]() { output.push_back(operators.back()); operators.pop_back(); };
for (const auto& token : tokens) {
if (token[0] >= '0' && token[0] <= '9') output.push_back(token);
else if (token == "(") operators.push_back(token);
else if (token == ")") {
while (operators.back() != "(") pop();
operators.pop_back();
} else {
while (!operators.empty() && operators.back() != "(" &&
precedence(operators.back()) >= precedence(token)) pop();
operators.push_back(token);
}
}
while (!operators.empty()) pop();
string result;
for (const auto& token : output) {
if (!result.empty()) result += ' ';
result += token;
}
return result;
}