I need to make calculator that takes infix expression and uses rpn to evaluate it.
Java code:
public RpnCalculator() {
}
public float eval(float arg1, float arg2, String operator) {
switch (operator) {
case PLUS:
return arg1 + arg2;
case MINUS:
return arg2 - arg1;
case MULTIPLICATION:
return arg1 * arg2;
case DIVISION:
return arg2 / arg1;
default:
return 0;
}
}
public String evaluateInfixExpression(String expression) {
Stack<String> operators = new Stack<>();
String[] args = expression.split(SPACE);
Stack<String> values = new Stack<>();
for (String arg : args) {
if (isANumber(arg)) {
values.push(arg);
continue;
}
if (operators.isEmpty()) {
operators.push(arg);
} else if (precedence(arg) <= precedence(operators.peek())) {
float result = eval(Float.parseFloat(values.pop()), Float.parseFloat(values.pop()), operators.pop());
values.push(String.valueOf(result));
operators.push(arg);
} else if (precedence(arg) > precedence(operators.peek())) {
operators.push(arg);
}
}
while (!operators.isEmpty()) {
float result = eval(Float.parseFloat(values.pop()), Float.parseFloat(values.pop()), operators.pop());
values.push(String.valueOf(result));
}
return expression;
}
public int precedence(String operator){
if (operator.equals(PLUS) || operator.equals(MINUS)){
return 1;
}
return 2;
}
public boolean isANumber(String number) {
if (number.matches("-?\\d+")) {
return true;
}
return false;
}
}
and it works well, except it gives wrong answers sometimes... It seems for me i'am following the shunting yard algorithm principles, but as you can see I don't actually convert infix to postfix but I try to evaluate arguments on the go, and maybe that is a problem.
For example the expression -2 + 6 * 8 / 3 * 18 - 33 / 3 - 11 evaluates to 286 instead of 264. There should be some mistake I am not able to notice, and it's been two days already so please help me. Also I read whole lot of threads about RPN here on stack, but it seems that everybody has different problem with it so I didn't find an answer for my case.
Thank you.
Here is a concise solution to do the calculation on the fly:
public class RpnCalculator {
public static Float evaluateInfixExpression(String inflixExpression) {
Stack<Float> operands = new Stack<>();
Stack<Operator> operators = new Stack<>();
for (String token : inflixExpression.split("\\s")) {
if (isOperator(token)) {
while (!operators.isEmpty() && operators.peek().hasHigherPrecedenceThan(token))
operands.add(eval(operands.pop(), operands.pop(), operators.pop()));
operators.push(fromString(token));
} else {
operands.add(new Float(token));
}
}
while (!operators.isEmpty())
operands.add(eval(operands.pop(), operands.pop(), operators.pop()));
return operands.pop();
}
private static Float eval(float arg2, float arg1, Operator operator) {
switch (operator) {
case ADD:
return arg1 + arg2;
case SUBTRACT:
return arg1 - arg2;
case MULTIPLY:
return arg1 * arg2;
case DIVIDE:
return arg1 / arg2;
default:
throw new IllegalArgumentException("Operator not supported: " + operator);
}
}
}
And the Operator
class:
public enum Operator {
ADD(1), SUBTRACT(1), MULTIPLY(2), DIVIDE(2);
final int precedence;
Operator(int p) { precedence = p; }
private static Map<String, Operator> ops = new HashMap<String, Operator>() {{
put("+", Operator.ADD);
put("-", Operator.SUBTRACT);
put("*", Operator.MULTIPLY);
put("/", Operator.DIVIDE);
}};
public static Operator fromString(String token){
return ops.get(token);
}
public static boolean isOperator(String token) {
return ops.containsKey(token);
}
public boolean hasHigherPrecedenceThan(String token) {
return isOperator(token) && this.precedence >= fromString(token).precedence;
}
}