Round 1
Questions: Convert the given postfix expression to the corresponding infix expression while minimizing the use of parentheses.
Example 1:
Input -> abc+*
Output -> a*(b+c)
Example 2:
Input -> abc*+
Output -> a+b*c
Constraint: Operators limited to addition (+) and multiplication (*).
Candidate's Approach
A minor tweak on the postfix to infix problem was utilized. Two stacks were used: one for operands and one for the corresponding operators. While popping the operands (simple or compound) from the operand stack, the corresponding operators were also popped to compare their precedence with the current operator. Operands were parenthesized accordingly.
Interviewer's Feedback
No feedback provided.
Extension
Questions: The operator constraint was removed to allow subtraction, division, and exponential operations.
Example:
Input -> abc--
Output -> a-(b-c)
Compared to example 2 of the original problem, one can observe how parentheses insertions can change based on the operator.
Candidate's Approach
Introduced the concept of associativity to the code to manage this. During the popping and precedence comparison of the operators, the associativity of the current operator was also considered to figure out whether/where to insert a parenthesis.
Interviewer's Feedback
No feedback provided.