DSA interview question

Infix to Prefix Conversion

Medium · Data structures · Topics: stack, string

The problem

A symbolic-algebra tool stores formulas in prefix notation (operator first), but users type ordinary infix like x+y*z/w+u. The classic conversion reuses the infix-to-postfix algorithm in a mirror: reverse the infix string, swap ( and ), run the shunting-yard with the associativity rule flipped, and reverse the result. The flip matters: in the mirrored string, left-associative operators must not pop equal-precedence operators, while right-associative ^ must.

Example: x+y*z/w+u → ++x/*yzwu.

Function signature

string infixToPrefix(const string& s);  // single-character operands; + - * / ^ and parentheses

Test cases

Input	Output	Explanation
`x+y*z/w+u`	`++x/*yzwu`	((x + ((y*z)/w)) + u)
`A*(B+C)/D`	`/*A+BCD`	(A*(B+C))/D
`(a+b)*(c-d)`	`*+ab-cd`
`a-b+c`	`+-abc`	Left-associative: (a−b)+c
`a^b^c`	`^a^bc`	Right-associative: a^(b^c)

(Confirm: operands are single characters; the expression is valid; precedence ^ > * / > + −, and only ^ is right-associative.)

How interviewers phrase it

"Convert an infix expression to prefix notation" (GeeksforGeeks "Infix to Prefix").

Clarifying questions to ask

Which operators, and what precedence and associativity?
Single-character operands?
Is the input guaranteed valid?

Follow-ups to expect

"Why reverse the string?"
"Why swap the parentheses?"
"Why flip the equal-precedence rule?"
"Alternative approach?"
"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