Evaluation av Postfix!
Hej!
Jag håller på med att göra en metod som evaluerar en Postfix och som returnerar ett värde (int).
Vid testning av koden så fick jag False vid tre olika tillfällen. Bifogar koden och testet.
double evalPostfix(List<String> postfix) {
Deque<Integer> s = new ArrayDeque<>();
for (int i = 0; i < postfix.size(); i++){
String token = postfix.get(i);
if (!isOperator(token)){
int numToken = Integer.parseInt(token); //String to Integer.
s.push(numToken);
}else if (isOperator(token)){
double op2 = s.peek();
s.pop();
double op1 = s.peek();
s.pop();
s.push((int) applyOperator(token, op2, op1));
}
}
return s.peek();
}
double applyOperator(String op, double d1, double d2) {
switch (op) {
case "+":
return d1 + d2;
case "-":
return d2 - d1;
case "*":
return d1 * d2;
case "/":
if (d1 == 0) {
throw new IllegalArgumentException(DIV_BY_ZERO);
}
return d2 / d1;
case "^":
return pow(d2, d1);
}
throw new RuntimeException(OP_NOT_FOUND);
}
Testet:
// Evaluation ------------------------------
resultat:
e("123", 123); 123.0 True
// Basic operations
e("1 + 10", 11); 11.0 True
e("1 + 0", 1); 1.0 True
e("1 - 10", -9); -9.0 True
e("10 - 1", 9); 9.0 True
e("60 * 10", 600); 600.0 True
e("60 * 0", 0); 0.0 True
e("3 / 2", 1.5); 1.0 False
e("1 / 2", 0.5); 0.0 False
e("2 ^ 4 ", 16); 16.0 True
e("2 ^ 0 ", 1); 1.0 True
// Associativity
e("10 - 5 - 2", 3); 3.0 True
e("20 / 2 / 2", 5); 5.0 True
e("4 ^ 2 ^ 2", 256); 256.0 True
// Precedence
e("3 * 10 + 2", 32); 32.0 True
e("3 + 10 * 2", 23); 23.0 True
e("30 / 3 + 2", 12); 12.0 True
e("1 + 30 / 3", 11); 11.0 True
e("3 * 2 ^ 2", 12); 12.0 True
e("3 ^ 2 * 2", 18); 18.0 True
// Parentheses
e("10 - (5 - 2)", 7); 7.0 True
e("1 * (2 + 3)", 5); 5.0 True
e("20 / (10 / 2)", 4); 4.0 True
e("(3 ^ 2) ^ 2", 81); 81.0 True
e("3 * (10 + 2)", 36); 36.0 True
e("30 / (3 + 2)", 6); 6.0 True
e("(3 + 2) ^ 2", 25); 25.0 True
e(" 2 ^ (1 + 1)", 4); 4.0 True
e(" ((((1 + 1))) * 2)", 4); 4.0 True
// Mix priority and right and left associativity
e(" 1 ^ 1 ^ 1 ^ 1 - 1", 0); 1.0 False
e(" 4 - 2 - 1 ^ 2 ", 1); 1.0 True
Process finished with exit code 0
Bra om testfallet, alltså givet, förväntat och utfall, skrivs ut före true/false, jobbigt matcha.
Programmeraren skrev:Bra om testfallet, alltså givet, förväntat och utfall, skrivs ut före true/false, jobbigt matcha.
Yes, jag kommer att ändra inlägget.
Programmeraren skrev:Bra om testfallet, alltså givet, förväntat och utfall, skrivs ut före true/false, jobbigt matcha.
Har nu ändrat inlägget.
e("3 / 2", 1.5); 1.0 False
Ser konstig ut. Själva konverteringen till postfix vore bra att veta att den gått rätt, har du testat det ordentligt?
För säkerhets skull, lägg till så att testerna också skriver ut uttrycket i postfix innan evaluering.
Programmeraren skrev:
e("3 / 2", 1.5); 1.0 FalseSer konstig ut. Själva konverteringen till postfix vore bra att veta att den gått rätt, har du testat det ordentligt?
För säkerhets skull, lägg till så att testerna också skriver ut uttrycket i postfix innan evaluering.
Har debuggat, och Postfix i detta fall var 32/. Vilket ser bra ut va?
Ja. Men svårt se koden ovan göra det till 1.0
Skriva ut op, d1, d2 i applyOperator kanske. Divisionen beter sig som om det var "int":ar. Vilket inte är möjligt.
Ah ser felet, du castar till int i push():
s.push((int) applyOperator(token, op2, op1));
Programmeraren skrev:Ja. Men svårt se koden ovan göra det till 1.0
Skriva ut op, d1, d2 i applyOperator kanske. Divisionen beter sig som om det var "int":ar. Vilket inte är möjligt.
Vid applyOperator så ser det bra ut d2/d1 => 3/2, men resultatet i det fallet blir 1.
Programmeraren skrev:Ah ser felet, du castar till int i push():
s.push((int) applyOperator(token, op2, op1));
Jaha, ska jag inte göra det ? Här ger jag type int till token om det är ett nummer. Är det fel?
int numToken = Integer.parseInt(token);Nu är det inte tokens längre, nu räknar du tal.
3 2 / --> 1.5
(int) 1.5 --> 1
Din parsning kommer bara klara heltal. Verkar bättre med:double num = Double.parseDouble(token)
Programmeraren skrev:Nu är det inte tokens längre, nu räknar du tal.
3 2 / --> 1.5
(int) 1.5 --> 1Din parsning kommer bara klara heltal. Verkar bättre med:
double num = Double.parseDouble(token)
double evalPostfix(List<String> postfix) {
Deque<Double> s = new ArrayDeque<>();
for (int i = 0; i < postfix.size(); i++){
String token = postfix.get(i);
if (token.matches("[0-9]+")){
double numToken = Double.parseDouble(token);
s.push(numToken);
}else if (isOperator(token)){
double op1 = s.peek();
s.pop();
double op2 = s.peek();
s.pop();
s.push( applyOperator(token, op1, op2));
}
}
return s.peek();
}
Det löste sig för de fall med div.
Men byt tilldouble num = Double.parseDouble(token)
så klarar du även decimaltal.
Nu är det detta fall som min kod ger False på:
e(" 1 ^ 1 ^ 1 ^ 1 - 1", 0);När jag debuggar så får jag Postfix uttrycket till att vara
[1, 1, 1, 1, ^, 1, -, ^, ^]Vilket ser inte bra ut va, Det verkar att rätt postfix i detta fall skall vara
11^1^1^1-Programmeraren skrev:Men byt till
double num = Double.parseDouble(token)
så klarar du även decimaltal.
Japp, gjorde det.
Exakt. Kanske nåt med din höger-association för ^ som gör att du glömmer sätta in ^
Programmeraren skrev:Exakt. Kanske nåt med din höger-association för ^ som gör att du glömmer sätta in ^
Det kan vara något som är fel med min infixTopostfix kod som göra att jag får fel Postfix nu. Det är ganska märkligt då min infixTopostfix kod klarade alla tester som är nödvändiga för nästa steg.
Programmeraren skrev:Exakt. Kanske nåt med din höger-association för ^ som gör att du glömmer sätta in ^
Skulle du kunna ta och kika på min infixTopostfix kod,
List<String> infix2Postfix(List<String> infix) {
List<String> resultPostfix = new ArrayList<>();
Deque<String> s = new ArrayDeque<>();
for (int i = 0; i < infix.size(); i++) {
String token = infix.get(i);
if (token.matches("[0-9]+")) { //if token is operand.
resultPostfix.add(token); //add to postfix list.
} else if (isOperator(token)) {
if (s.isEmpty() || s.peek().equals("(")) {
s.push(token);
} else if (!s.isEmpty() && (getPrecedence(token) < getPrecedence(s.peek()))) {
resultPostfix.add(s.peek());
s.pop();
s.push(token);
} else if (!s.isEmpty() && (getPrecedence(token) > getPrecedence(s.peek()))) {
s.push(token);
} else if (!s.isEmpty() && (getPrecedence(token) == getPrecedence(s.peek()))
&& (getAssociativity(s.peek()) == Assoc.LEFT)) {
resultPostfix.add(s.peek());
s.pop();
s.push(token);
} else if (!s.isEmpty() && (getPrecedence(token) == getPrecedence(s.peek()))
&& (getAssociativity(s.peek()) == Assoc.RIGHT)) {
s.push(token);
}
}
else if (token.equals("(")){
s.push(token);
}else if (token.equals(")")){
if (!s.isEmpty() && !Objects.equals(s.peek(), "(")){
resultPostfix.add(s.peek());
s.pop();
}
s.pop();
}
}
while (!s.isEmpty()) {
resultPostfix.add(s.peek()); //finally, we add left tokens to list and pop.
s.pop();
}
return resultPostfix;
}
boolean isOperator(String st) {
switch (st) {
case "^":
case "/":
case "*":
case "+":
case "-":
return true;
default:
return false;
}
}
int getPrecedence(String op) { //order of operations
if ("+-".contains(op)) {
return 2;
} else if ("*/".contains(op)) {
return 3;
} else if ("^".contains(op)) {
return 4;
} else {
throw new RuntimeException(OP_NOT_FOUND);
}
}
Assoc getAssociativity(String op) {
if ("+-*/".contains(op)) {
return Assoc.LEFT;
} else if ("^".contains(op)) {
return Assoc.RIGHT;
} else {
throw new RuntimeException(OP_NOT_FOUND);
}
}
enum Assoc {
LEFT,
RIGHT
}Har inte läst men kan det vara så att din högerassociation av ^ inte kollar att det är ^ till vänster? Och därför hamnar de till höger om "-"?
