Pergunta de entrevista da empresa Uber
// evalexpr(-4 - 3 * 2 / 2 + 4) -> result (float or double)
//
// [Token(NUM, -4.), Token(SUB), Token(NUM, 3), Token(MUL)…]
//
// input: an array/list of Tokens representing a VALID arithmetic expression
// output: the result as a float or double
//
// Token:
// type: one of NUM, ADD, SUB, MUL, DIV
// value: float or double it's only defined/relevant when the token as type NUM
//
// Todo:
// 1. implement the Token class/struct
// 2. implement evalexpr
Respostas da entrevista
That's not a fair question for a phone interview.
private void findExpr() {
Deque valueStack = new ArrayDeque();
Deque opStack = new ArrayDeque();
List list = new ArrayList();
list.add(new Token("NUM",-4.0));
list.add(new Token("SUB"));
list.add(new Token("NUM",3.0));
list.add(new Token("MUL"));
list.add(new Token("NUM",2.0));
list.add(new Token("DIV"));
list.add(new Token("NUM",2.0));
list.add(new Token("ADD"));
list.add(new Token("NUM",4.0));
for(Token t : list){
if(t.token.equals("NUM"))
{
valueStack.push((Double) t.data);
}
else{
while(opStack.isEmpty()==false && currTokenHasLowerPrecedence(t.token,opStack.peek())){
valueStack.push(makeOP(valueStack.pop(),valueStack.pop(),opStack.pop()));
}
opStack.push(t.token);
}
}
while(!opStack.isEmpty()){
valueStack.push(makeOP(valueStack.pop(),valueStack.pop(),opStack.pop()));
}
System.out.println("FINAL RES:"+ valueStack.pop());
}
private Double makeOP(Double val2, Double val1, String op) {
switch(op)
{
case "MUL":
return val1*val2;
case "ADD":
return val1+val2;
case "SUB":
return val1-val2;
case "DIV":
if(val2 == 0){
System.out.println("Error in Input String . Can't divide to Zero");
return null;
}
return val1/val2;
}
return 0.0;
}