Qumulo Interview Question
Member Technical StaffsCountry: United States
Interview Type: In-Person
I'm curious how your code will perform agains the expresssion in question i.e. * - 6 5 7 = 7?
Strting from the left, your stack will contain one 7 before = expression is encountered, when you try to remove
2 operands from the stack, you only have 1 operand -> err
Instead I would suggest also pushing in the = operator into the stack
Both prefix and postfix can be implemented using a simple strategy using a stack(LIFO). We assume the
current prefix/postfix expression is present in a queue(FIFO)
A general algo is:
Till queue empty
Dequeue one element from queue
if element is a number/operand or an = expression
push it into the stack
else //element is an operand like + - * etc
pop top two elements from stack
perform the operation using the operand
push result onto stack
if(stack becomes empty before two elements can be popped)
error!
At this point, your queue will contain one element i.e. the answer
public static boolean isInteger(String token) {
if (token == null)
return false;
try {
Integer.parseInt(token);
} catch (NumberFormatException e) {
return false;
}
return true;
}
public static void main(String[] args) {
Deque<Character> stack = new ArrayDeque<>();
Scanner scanner = new Scanner(System.in);
Integer num1 = null, num2 = null;
String token;
while (scanner.hasNext()) {
token = scanner.next();
if (!isInteger(token)) {
stack.addFirst(token.charAt(0));
}
else {
if (num1 == null) {
num1 = new Integer(Integer.parseInt(token));
}
else {
num2 = new Integer(Integer.parseInt(token));
switch (stack.removeFirst()) {
case '+':
num1 = num1 + num2;
break;
case '-':
num1 = num1 - num2;
break;
case '*':
num1 = num1 * num2;
break;
case '/':
num1 = num1 / num2;
break;
default:
System.out.println("Unsupported operation");
return;
}
}
}
}
System.out.println("Answer: " + num1);
}
Google for this question and you will get many links. Below is just simple plain implementation.
- aka November 10, 2015