Amazon Interview Question
Software Engineer / DevelopersTeam: General
Country: United States
Interview Type: In-Person
I suppose that the question is to construct an expression tree given an infix expression:
Infix: (6*2)/3
Convert this to postfix using the standard method involving a stack:
Postfix: 62*3/
Algo: (Create another empty stack)
1. Scan thpostfix string from left to right, for each element:
-If you encounter a number, create its treenode and pust it onto the stack
-if you encounter an operator(*/+-), create its treenode, pop twp nodes from the stack, and make them this operator node's children, then push the operator node into the stack.
2. Continue till the string is exhausted.
3. the Last node in the stack now is a tree representing the expression.
first transfer the infix to postfix, then use a stack to construct the expression tree using postfix.
- Anonymous November 08, 2011