DSA interview question

Prefix to Infix Conversion

Medium · Data structures · Topics: stack, string

The problem

A calculator app stores formulas in prefix (Polish) notation, like *-A/BC-/AKL, because it's unambiguous without parentheses. Users need to see them as ordinary fully parenthesised infix expressions, like ((A-(B/C))*((A/K)-L)). Scanning the prefix string from right to left with a stack of strings does it: operands are pushed as they are, and each operator pops its two operands (the top one is the left operand) and pushes "(" + left + op + right + ")".

Example: *-A/BC-/AKL → ((A-(B/C))*((A/K)-L)).

Function signature

string prefixToInfix(const string& pre);  // single-character operands; binary operators

Test cases

Input	Output	Explanation
`*-A/BC-/AKL`	`((A-(B/C))*((A/K)-L))`
`+ab`	`(a+b)`
`*+ab-cd`	`((a+b)*(c-d))`
`-+abc`	`((a+b)-c)`
`a`	`a`	A lone operand

(Confirm: the prefix expression is valid; operands are single letters or digits; every binary operation is wrapped in parentheses.)

How interviewers phrase it

"Given a prefix expression, convert it to infix" (GeeksforGeeks "Prefix to Infix Conversion").

Clarifying questions to ask

Fully parenthesised output, or minimal parentheses? (Fully, here.)
Only binary operators? (Yes.)
Single-character operands? (Yes; otherwise tokenise.)

Follow-ups to expect

"Why scan from right to left?"
"Which popped string is the left operand?"
"How do you check validity?"
"How would you get minimal parentheses?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview