Java Evaluating RPN using Shunting Yard Algorithm

Tags: , ,



I have the shunting yard algorithm that I found online:

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class ShuntingYardAlgorithm {

private enum Operator {
    ADD(1), SUBTRACT(2), MULTIPLY(3), DIVIDE(4);
    final int precedence;
    Operator(int p) {
        precedence = p;
    }
}

private Map<String, Operator> operatorMap = new HashMap<String, Operator>() {/**
     * 
     */
    private static final long serialVersionUID = 1L;

{
    put("+", Operator.ADD);
    put("-", Operator.SUBTRACT);
    put("*", Operator.MULTIPLY);
    put("/", Operator.DIVIDE);
}};

private boolean isHigherPrec(String op, String sub) {
    return (operatorMap.containsKey(sub) &&
            operatorMap.get(sub).precedence >= operatorMap.get(op).precedence);
}

public String shuntingYard(String infix) {
    StringBuilder output = new StringBuilder();
    Stack<String> stack = new Stack<String>();

    for (String token : infix.split("")) {
        //operator
        if (operatorMap.containsKey(token)) {
            while ( ! stack.isEmpty() && isHigherPrec(token, stack.peek())) {
                output.append(stack.pop()).append(' ');
            }
            stack.push(token);
        }
        //left parenthesis
        else if (token.equals("(")) {
            stack.push(token);
        }
        //right parenthesis
        else if (token.equals(")")) {
            while ( ! stack.peek().equals("(")) {
                output.append(stack.pop()).append(' ');
            }
            stack.pop();
        }
        //digit
        else {
            output.append(token).append(' ');
        }
    }

    while ( ! stack.isEmpty()) {
        output.append(stack.pop()).append(' ');
    }

    return output.toString();
}

}

And the evaluator:

private static int evalRPN(String[] tokens) {
    int returnValue = 0;
    String operators = "+-*/";

    Stack<String> stack = new Stack<String>();

    for (String t : tokens) {
        if (!operators.contains(t)) {
            stack.push(t);
        } else {
            int a = Integer.valueOf(stack.pop());
            int b = Integer.valueOf(stack.pop());
            switch (t) {
            case "+":
                stack.push(String.valueOf(a + b));
                break;
            case "-":
                stack.push(String.valueOf(b - a));
                break;
            case "*":
                stack.push(String.valueOf(a * b));
                break;
            case "/":
                stack.push(String.valueOf(b / a));
                break;
            }
        }
    }

    returnValue = Integer.valueOf(stack.pop());

    return returnValue;
}

And they work good so far but I have a problem with the evaluation where the delimiter is split by “”, which does not allow two digit numbers, such as 23, or above. What can you suggest that I can do to improve the evaluation method?

String output = new ShuntingYardAlgorithm().shuntingYard(algExp);
        algExp = output.replaceAll(" ", "");
        String[] outputArray = algExp.split("");
        return evalRPN(outputArray);

Such as I input: 256+3 result: 2 5 6 3 + Evaluation: 6 + 3 = 9, ignores 2 and 5

Answer

Your shuntingYard function is discarding the contents of output when an operator or a parenthesis is encountered.

You need to add checks for contents of output before processing the current character.

    if (operatorMap.containsKey(token)) {
        // TODO: Check output here first, and create a token as necessary
        while ( ! stack.isEmpty() && isHigherPrec(token, stack.peek())) {
            output.append(stack.pop()).append(' ');
        }
        stack.push(token);
    }
    //left parenthesis
    else if (token.equals("(")) {
        // TODO: Check output here first, and create a token as necessary
        stack.push(token);
    }
    //right parenthesis
    else if (token.equals(")")) {
        // TODO: Check output here first, and create a token as necessary
        while ( ! stack.peek().equals("(")) {
            output.append(stack.pop()).append(' ');
        }
        stack.pop();
    }

Also, splitting using the empty string is equivalent to just iterating the String one character at a time. Iterating infix using toCharArray() might be more readable

   for (char c : infix.toCharArray())


Source: stackoverflow