Amazon Interview Question Software Engineer / Developers
Sorry that will fail in some cases.
We have to convert the infix expression into postfix and then evaluate the postfix.
Your solution is almost there. No need to convert infix to postfix.
- Read next 3 tokens - which will always be number, operator, number
- Add numbers to numStack, operator to opStack
While tokens still left
{
- Read next 2 tokens - number and operator
- Compare operator to topmost op in opStack. If lower in priority, add number to numStack, operator to opStack. If higher in priority, pop number from numStack, evaluate both numbers with operator, push result number onto number stack
}
While (elements still present in opStack)
{
- Pop from opStack, pop 2 numbers from numStack, evaluate. Push result to stack
}
Return result.
This seems to be going into an infinite loop if we get an operator whose priority is lower than top of operator stack.
this will work :-
correct me If i am wrong:
- Aditya October 23, 2010stack s1; symb = null; while( (c=getnextsymbol()) != NULL ) { if(is_number(c)) push(s1,c) else if( is_operator(c)) { if(priority(c)>priority(symb) ) push(s1,c) else { opr2 = s1.pop(); op = s1.pop(); opr1 = s1.pop(); push(s1, evaluate(opr1,op,opr2)); push(s1,c); } symb = c; } } while(numel(s1)>1 ) { opr2 = s1.pop(); op = s1.pop(); opr1 = s1.pop(); push(s1, evaluate(opr1,op,opr2)); } print "ans = " s1.top();