Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
Just maintain two stacks, one for operand and one for symbol. Below code must do the trick. (NOTE: Haven't verified it, just wrote it to explain the logic)
/*Function to convert from infix to post fix */
char* infix_to_postfx(char *infix) {
int i=0;
stack<char> symbol_stack;
stack<char*> operand_stack;
while(infix[i++] != ‘\0’) {
if(is_char_symbol(infix[i-1])) {
/*symbol*/
if(is_cur_symbol_high_precedense(infix[i-1], symbol_stack.top()) {
/*Push the symbol*/
symbol_stack.push(infix[i-1])
} else {
while(is_cur_symbol_high_precedense(infix[i-1], symbol_stack.top()) {
char operand1 = operand_stack.pop();
char operand2 = operand_stack.pop();
char symbol = symbol_stack.pop();
char *result = new char[sizeof(operand1) + sizeof(operand2) + sizeof(symbol)];
sprint(result, “%c%c%c”, operand1, operand2, symbol);
operand_stack.push(result)
delete operand1;
delete operand2;
} /*end while*/
} /*end else*/
}/*end if-else*/
} else {
/*operand*/
char *operand = new char[2];
operand[2] = ‘\0’;
operand[1] = infix[i-1];
operand_stack.push(operand);
}/*end if-else*/
}
bool is_char_symbol(char c) {
if((c==’+’) || (c == ‘-‘) || (c==’*”) || (c==’/)) {
return(true);
} else {
return(false);
}
}
bool is_cur_symbol_high_precedense(char cur, char in_stack) {
switch(cur) {
case ‘+’ :
if((in_stack==’+’ || in_stack == ‘-‘) {
return(0);
} else if(in_stack==’*‘ || in_stack == ‘/’) {
return(1);
}
case ‘-’ :
if((in_stack==’+’ || in_stack == ‘-‘) {
return(0);
} else if(in_stack==’*‘ || in_stack == ‘/’) {
return(1);
}
case ‘*’ :
return(0);
case ‘/’ :
return(0);
}
}
we can use simple stack method here
algo-:
1>read the input string from index 0 if input pointer points to a operand print it.
2> else push each operator into a stack till stack[top] has a priority less than currrent operator pointed by input pointer and after that pop till stack[top] has higher priority than current operator.
3> as soon as closing bracket encountered pop till the opening bracket is also popped.
I feel, Having only one stack for operators would be sufficient for this. Here goes the approach.
foreach element of the infix expression :
if (element is operand)
Add it to the postfix string.
if (element is operator)
check if the operator on top of the stack has higher precedence
if (yes)
pop the stack and add the operator to the postfix string.
else
push the operator on the stack.
pop all elements from the stack and add them to the postfix string.
We can take care of () as well.
scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/index.htm
- prince May 26, 2012