PPractick

The problem

A spreadsheet's formula engine converts formulas like a+b*(c^d-e) into postfix (Reverse Polish Notation), where operators follow their operands, so they can be evaluated with a simple stack and no precedence rules. The conversion is Dijkstra's shunting-yard algorithm: operands go straight to the output, and operators wait on a stack until an operator of lower precedence, or a closing parenthesis, forces them out. ^ is right-associative (a^b^c means a^(b^c)); the others are left-associative.

Example: a+b*(c^d-e)^(f+g*h)-i → abcd^e-fgh*+^*+i-.

Function signature

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

Test cases

Input	Output	Explanation
a+b*(c^d-e)^(f+g*h)-i	abcd^e-fgh*+^*+i-
A*(B+C)/D	ABC+*D/
a-b+c	ab-c+	Left-associative: (a−b)+c
a^b^c	abc^^	Right-associative: a^(b^c)
(a+b)*(c-d)	ab+cd-*

(Confirm: operands are single letters or digits; the expression is valid; precedence is ^ > * / > + −, with ^ right-associative.)

How interviewers phrase it

• "Convert an infix expression to postfix notation" (GeeksforGeeks "Infix to Postfix").

Clarifying questions to ask

1. Which operators, and what precedence and associativity? (^ highest and right-associative.)
2. Are operands single characters? (Multi-character tokens need a tokenizer.)
3. Is the input always valid?

Follow-ups to expect

1. "When do you pop operators?"
2. "What does ')' do?"
3. "Why does ^ differ?"
4. "How would you evaluate the postfix?"
5. "Complexity?"

Related questions

• Remove Outermost Parentheses Medium
• Maximum Nesting Depth of the Parentheses Medium
• Prefix to Infix Conversion Medium
• Prefix to Postfix Conversion Medium
• Postfix to Prefix Conversion Medium
• Infix to Prefix Conversion Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in