I wanted to create a method, that interprets this List (The method "words" splits a String into a list of words, that are seperated by \s.) in postfix-notation. This is what I got, by I am wondering if there is a shorter way to solve this, as I am repeating myself quite often there.
public static double eval(String expr) {
return eval_(new ListStack<Double>() , words(expr));
}
private static double eval_(Stack<Double> s, List<String> expr) {
if (expr.isEmpty()) {
return s.top();
} else if (expr.head().equals("+")) {
Double fstValue = s.top();
s = s.pop();
Double sndValue = s.top();
s = s.pop();
s = s.push(add.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("-")) {
Double fstValue = s.top();
s = s.pop();
Double sndValue = s.top();
s = s.pop();
s = s.push(sub.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("*")) {
Double fstValue = s.top();
s = s.pop();
Double sndValue = s.top();
s = s.pop();
s = s.push(mul.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("/")) {
Double fstValue = s.top();
s = s.pop();
Double sndValue = s.top();
s = s.pop();
s = s.push(div.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("^")) {
Double fstValue = s.top();
s = s.pop();
Double sndValue = s.top();
s = s.pop();
s = s.push(pow.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("!")) {
Double fstValue = s.top();
s = s.pop();
s = s.push(fact.apply(fstValue));
return eval_(s, expr.tail());
} else {
Double value = Double.parseDouble(expr.head());
s = s.push(value);
return eval_(s, expr.tail());
}
}
I tried this to shorten it a little:
private static double eval_(Stack<Double> s, List<String> expr) {
Double fstValue;
Double sndValue;
if (expr.isEmpty()) {
return s.top();
} else if (!expr.isEmpty()) {
fstValue = s.top();
s = s.pop();
sndValue = s.top();
s = s.pop();
if (expr.head().equals("+") && !expr.isEmpty()) {
s = s.push(add.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("-") && !expr.isEmpty()) {
s = s.push(sub.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("*") && !expr.isEmpty()) {
s = s.push(mul.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("/") && !expr.isEmpty()) {
s = s.push(div.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("^") && !expr.isEmpty()) {
s = s.push(pow.apply(fstValue).apply(sndValue));
return eval_(s, expr.tail());
} else if (expr.head().equals("!") && !expr.isEmpty()) {
s = s.push(fact.apply(fstValue));
return eval_(s, expr.tail());
}
else {
Double value = Double.parseDouble(expr.head());
s = s.push(value);
return eval_(s, expr.tail());
}
} else {
Double value = Double.parseDouble(expr.head());
s = s.push(value);
return eval_(s, expr.tail());
}
}
Edit:
Input:
System.out.println(eval(5 6 + 8 *));
'Interpreted as (5+6) * 8 = 11 * 8'
Output: "88"
private static final Function<Double, Function<Double, Double>> add = x -> y -> x + y;
private static final Function<Double, Function<Double, Double>> sub = x -> y -> x - y;
private static final Function<Double, Function<Double, Double>> mul = x -> y -> x * y;
private static final Function<Double, Function<Double, Double>> div = x -> y -> x / y;
private static final Function<Double, Function<Double, Double>> pow = x -> y -> Math.pow(x,y);
private static final Function<Double, Double> fact = Postfix::fact;
public static double fact(double i){
return i > 1 ? i * fact(i - 1) : 1;
}
Neither its working nor is it really short. (My prof told me I could do it in one line tho). I appreciate you helping me!
Edit 2: I tried what @Rocco answered (and simplified it using IntelliJ)
private static double eval(String expr) {
switch (expr) {
case "+" -> s.push(add.apply(s.popTop().fst).apply(s.popTop().fst));
case "-" -> s.push(sub.apply(s.popTop().fst).apply(s.popTop().fst));
case "*" -> s.push(mul.apply(s.popTop().fst).apply(s.popTop().fst));
case "/" -> s.push(div.apply(s.popTop().fst).apply(s.popTop().fst));
case "^" -> {
double exp = s.popTop().fst;
s.push(Math.pow(s.popTop().fst, exp));
}
case "!" -> {
s.push(fact.apply(s.popTop().fst));
}
default -> s.push(Double.valueOf(String.valueOf(expr)));
}
return s.popTop().fst;
}
It always throws a "NumberFormatException". (Probably because it cant parse "+" as Double)
I think that your prof is kidding you, but yes, you make it shorter (not a single line, unless you just remove all LFs).
Just to explain, this is a minimal implementation of a shift-reduce parser, when you have a number just push it to the stack (shift), when an operator replace the topmost operands with the result of the operation.
Note that I'm not checking errors here, so an incorrect expression can return a wrong value.
import java.util.Stack;
public class PostFixEprParser {
public static double eval(String expr) {
Stack<Double> s=new Stack<>();
for (String token: expr.split("\\s+")) {
switch (token) {
case "+":
s.push(s.pop()+s.pop());
break;
case "-":
s.push(s.pop()-s.pop());
break;
case "*":
s.push(s.pop()*s.pop());
break;
case "/":
s.push(s.pop()/s.pop());
break;
case "^":
{
double exp=s.pop();
s.push(Math.pow(s.pop(), exp));
}
break;
case "!":
//TODO Here define your factorial function s.push(fact(s.pop()));
break;
default:
s.push(Double.valueOf(token));
}
}
return s.pop();
}