4
\$\begingroup\$

I have implemented a simple calculator using the Shunting Yard algorithm. It takes infix expression as an input "3 + 5 * 2", which evaluates and returns the value 13.

public class ShuntingYardAlgorithm{
    private static  Map<String, Operator> operatorMap = initializeOperatorMap();

    private static Map<String, Operator> initializeOperatorMap()
    {
        operatorMap = new HashMap<>();
        operatorMap.put(Operator.ADD.sign, Operator.ADD);
        operatorMap.put(Operator.SUBTRACT.sign, Operator.SUBTRACT);
        operatorMap.put(Operator.MULTIPLY.sign, Operator.MULTIPLY);
        operatorMap.put(Operator.DIVIDE.sign, Operator.DIVIDE);
        return operatorMap;
    }

    public ShuntingYardAlgorithm()
    {
        // Default Constructor
    }


    private enum Operator
    {
        ADD(1, "+"),
        SUBTRACT(2, "-"),
        MULTIPLY(3, "*"),
        DIVIDE(4, "/");

        final int precedence;
        final String sign;

        Operator(int precedence, String sign)
        {
            this.precedence = precedence;
            this.sign = sign;
        }
    }

    private static boolean isHighPrecedence(String currentToken, String peekedOperator)
    {
        return operatorMap.containsKey(peekedOperator) && operatorMap.get(peekedOperator).precedence >= operatorMap.get(currentToken).precedence;
    }

    public static Integer evaluateExpression(String infix)
    {
        Stack<String> operatorStack = new Stack<>();
        Stack<Integer> outputStack = new Stack<>();

        for (String currentToken : infix.split("\\s"))
        {

            if ("(".equalsIgnoreCase(currentToken))
            {
                operatorStack.push(currentToken);
            } else if (operatorMap.containsKey(currentToken))
            {
                while (!operatorStack.isEmpty() && isHighPrecedence(currentToken, operatorStack.peek()))
                {
                    String higherPrecedenceOperator = operatorStack.pop();
                    Integer operandLeft = outputStack.pop();
                    Integer operandRight = outputStack.pop();
                    outputStack.push(evaluate(operandLeft, operandRight, higherPrecedenceOperator));

                }
                operatorStack.push(currentToken);
            } else if (currentToken.equalsIgnoreCase(")"))
            {
                while (!"(".equalsIgnoreCase(operatorStack.peek()))
                {
                    String higherPrecedenceOperator = operatorStack.pop();
                    Integer operandLeft = outputStack.pop();
                    Integer operandRight = outputStack.pop();
                    outputStack.push(evaluate(operandLeft, operandRight, higherPrecedenceOperator));
                }
                operatorStack.pop();
            } else
            {
                outputStack.push(Integer.valueOf(currentToken));
            }
        }


        while (!operatorStack.empty())
        {
            String higherPrecedenceOperator = operatorStack.pop();
            Integer operandRight = outputStack.pop();
            Integer operandLeft = outputStack.pop();
            outputStack.push(evaluate(operandLeft, operandRight, higherPrecedenceOperator));

        }
        return outputStack.pop();
    }

    private static Integer evaluate(Integer operandLeft, Integer operandRight, String operator)
    {
        BigDecimal retVal = BigDecimal.ZERO;
        BigDecimal left = BigDecimal.valueOf(operandLeft);
        BigDecimal right = BigDecimal.valueOf(operandRight);
        if (operator.equals(Operator.MULTIPLY.sign))
        {
            retVal = left.multiply(right);
        } else if (operator.equals(Operator.ADD.sign))
        {
            retVal = left.add(right);
        } else if (operator.equals(Operator.SUBTRACT.sign))
        {
            retVal = left.subtract(right);
        } else if (operator.equals(Operator.DIVIDE.sign))
        {
            retVal = left.divide(right);
        }
        return retVal.intValue();
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ the code return wrong values for input "1 * 5 - 3" \$\endgroup\$ – Sharon Ben Asher Nov 17 '19 at 9:59
  • 1
    \$\begingroup\$ Since it was a minor bug I took the liberty to just fix it in your question. See edit revision to figure out what exactly I changed :) \$\endgroup\$ – Imus Nov 18 '19 at 16:41
3
\$\begingroup\$

Minor remarks:

  • The java convention is to put the opening { on the same line, not on a new line. It's great that you're consistent in your style though!

  • If you're doing the calculations using BigDecimal anyway, why not do that all the way and store the intermediat values as BigDecimal's as well in your stack?

  • method name isHighPrecedence wasn't immediately clear to me which one was the higher precedence. Not sure how to fix this one easily though.

Bigger idea:

I like how you used an enum for the Operators. This gives a nice list of all the possible (known) operators and an easy place to check if things like precedence are implemented correctly.

What I would do though, is go a step further. In java, an Enum is still a full class (except that all instances are created on class loading, you can't create new instances). This means that you can also provide methods there. I would expect the precedence comparison to be put in there. Although initially this might still be a bit clunky with the bracket handling (more on that later).

Another nice candidate is parsing an operator from a string. This can easily be implemented as follows:

    public static Operator from(String oper) {
        for (Operator operator : Operator.values()) {
            if (operator.sign.equalsIgnoreCase(oper)) {
                return operator;
            }
        }
        return NIL;
    }

What most people don't know, is that you can also override methods for each of the instances. The evaluate is a perfect candidate for this one. For example:

private enum Operator
{
    ADD(1, "+") {
        @Override
        public BigDecimal evaluate(BigDecimal left, BigDecimal right) {
            return left.add(right);
        }
    },
    SUBTRACT(2, "-") {
        @Override
        public BigDecimal evaluate(BigDecimal left, BigDecimal right) {
            return left.subtract(right);
        }
    },
    ... [include all operators here]
    };

    final int precedence;
    final String sign;

    Operator(int precedence, String sign)
    {
        this.precedence = precedence;
        this.sign = sign;
    }

    public abstract BigDecimal evaluate(BigDecimal left, BigDecimal right);

That way, if you have an operator you can just call
outputStack.push(higherPrecedenceOperator.evaluate(operandLeft, operandRight));

Changing the operator stack to actually contain Operator instead of String got me in a little bit of trouble storing the opening bracket on there. Since the idea is to first parse the operand from the input string, let's also add an Operand for the closing bracket, and a default option for a missing operand (that we can abuse for number inputs as well).

    OPEN_BRACKET(0, "(") {
    @Override
        public BigDecimal evaluate(BigDecimal left, BigDecimal right) {
            throw new IllegalStateException("Cannot apply bracket operand to left and right numbers");
        }
    },
    CLOSE_BRACKET(0, ")") {
        @Override
        public BigDecimal evaluate(BigDecimal left, BigDecimal right) {
            throw new IllegalStateException("Cannot apply bracket operand to left and right numbers");
        }
    },
    NIL(0, "") {
        @Override
        public BigDecimal evaluate(BigDecimal left, BigDecimal right) {
            throw new IllegalStateException("trying to evaluate invalid operator");
        }
    };

updating the evaluateExpression method to work with Operators required a little bit of reordering to handle the numbers correctly again:

public static BigDecimal evaluateExpression(String infix)
{
    Stack<Operator> operatorStack = new Stack<>();
    Stack<BigDecimal> outputStack = new Stack<>();

    for (String currentToken : infix.split("\\s"))
    {
        Operator currentOperator = Operator.from(currentToken);
        if (currentOperator == Operator.OPEN_BRACKET)
        {
            operatorStack.push(currentOperator);
        } else if (currentOperator==Operator.CLOSE_BRACKET)
        {
            while (Operator.OPEN_BRACKET.equals(operatorStack.peek())) {
                Operator higherPrecedenceOperator = operatorStack.pop();
                BigDecimal operandLeft = outputStack.pop();
                BigDecimal operandRight = outputStack.pop();
                outputStack.push(higherPrecedenceOperator.evaluate(operandLeft, operandRight));
            }
            operatorStack.pop();
        } else if (currentOperator != Operator.NIL)
        {
            while (!operatorStack.isEmpty() && operatorStack.peek().isHigherPrecedence(currentOperator)) {
                Operator higherPrecedenceOperator = operatorStack.pop();
                BigDecimal operandLeft = outputStack.pop();
                BigDecimal operandRight = outputStack.pop();
                outputStack.push(higherPrecedenceOperator.evaluate(operandLeft, operandRight));
            }
            operatorStack.push(currentOperator);
        } else
        {
            outputStack.push(BigDecimal.valueOf(Integer.valueOf(currentToken)));
        }
    }

    while (!operatorStack.empty())
    {
        Operator higherPrecedenceOperator = operatorStack.pop();
        BigDecimal operandRight = outputStack.pop();
        BigDecimal operandLeft = outputStack.pop();
        outputStack.push(higherPrecedenceOperator.evaluate(operandLeft, operandRight));

    }
    return outputStack.pop();
}

This got me thinking. What do we have to change to allow the bracket operantors to just evaluate similarly to the other operators instead? We could first update the current evaluate method to take the outputStack instead of a left and right operand. That way the Operator can decide how many numbers it needs. Specifically for the brackets, we also need to pass in the Operator stack so that the opening bracket can just push itself on the stack, and the closing bracket can pop the stack untill it finds an opening bracket.

private enum Operator {
    ADD(1, "+") {
        @Override
        public void evaluate(Stack<BigDecimal> numbers, Stack<Operator> operatorStack) {
            BigDecimal right = numbers.pop();
            BigDecimal left = numbers.pop();
            numbers.push(left.add(right));
        }
    },
    SUBTRACT(2, "-") {
        @Override
        public void evaluate(Stack<BigDecimal> numbers, Stack<Operator> operatorStack) {
            BigDecimal right = numbers.pop();
            BigDecimal left = numbers.pop();
            numbers.push(left.subtract(right));
        }
    },
    MULTIPLY(3, "*") {
        @Override
        public void evaluate(Stack<BigDecimal> numbers, Stack<Operator> operatorStack) {
            BigDecimal right = numbers.pop();
            BigDecimal left = numbers.pop();
            numbers.push(left.multiply(right));
        }
    },
    DIVIDE(4, "/") {
        @Override
        public void evaluate(Stack<BigDecimal> numbers, Stack<Operator> operatorStack) {
            BigDecimal right = numbers.pop();
            BigDecimal left = numbers.pop();
            numbers.push(left.divide(right));
        }
    },
    OPEN_BRACKET(Integer.MIN_VALUE, "(") {
        @Override
        public void evaluate(Stack<BigDecimal> numbers, Stack<Operator> operatorStack) {
            operatorStack.push(this);
        }
    },
    CLOSE_BRACKET(Integer.MAX_VALUE, ")") {
        @Override
        public void evaluate(Stack<BigDecimal> numbers, Stack<Operator> operatorStack) {
            while (!operatorStack.isEmpty() && operatorStack.peek() != OPEN_BRACKET) {
                operatorStack.pop().evaluate(numbers, operatorStack);
            }
            if (operatorStack.isEmpty()) {
                //no open bracket found!
                throw new IllegalStateException("closing bracket requires earlier matching opening bracket");
            }
            operatorStack.pop();
        }
    },
    NIL(0, "") {
        @Override
        public void evaluate(Stack<BigDecimal> numbers, Stack<Operator> operatorStack) {
            throw new IllegalStateException("trying to evaluate invalid operator");
        }
    };

    private final int precedence;
    private final String sign;

    Operator(int precedence, String sign) {
        this.precedence = precedence;
        this.sign = sign;
    }

    public static Operator from(String oper) {
        for (Operator operator : Operator.values()) {
            if (operator.sign.equalsIgnoreCase(oper)) {
                return operator;
            }
        }
        return NIL;
    }

    public boolean isHigherPrecedence(Operator other) {
        return this.precedence <= other.precedence;
    }

    public abstract void evaluate(Stack<BigDecimal> numbers, Stack<Operator> operatorStack);
}

Quick note that I also updated the priority values for the open and close brackets so that they're handled correctly while going through the stack. This way we can greatly simplify the evaluateExpression implementation as well:

public static BigDecimal evaluateExpression(String infix) {
    Stack<Operator> operatorStack = new Stack<>();
    Stack<BigDecimal> outputStack = new Stack<>();

    for (String currentToken : infix.split("\\s")) {
        Operator currentOperator = Operator.from(currentToken);
        if (currentOperator == Operator.NIL) { //number (or error from unknown operator?)
            outputStack.push(BigDecimal.valueOf(Integer.valueOf(currentToken)));
        } else {
            while (!operatorStack.isEmpty() && !operatorStack.peek().isHigherPrecedence(currentOperator)) {
                Operator higherPrecedenceOperator = operatorStack.pop();
                higherPrecedenceOperator.evaluate(outputStack, operatorStack);
            }
            operatorStack.push(currentOperator);
        }
    }

    while (!operatorStack.empty()) {
        operatorStack.pop().evaluate(outputStack, operatorStack);
    }
    return outputStack.pop();
}

The best part about implementing the Operators this way? We can easily add new operators, and they're not limited to 2 operands either! For example, adding the following Operand to the enum class:

    ABS(5, "abs") {
        @Override
        public void evaluate(Stack<BigDecimal> numbers, Stack<Operator> operatorStack) {
            numbers.push(numbers.pop().abs());
        }
    },

is all we need to do to then input things like "abs -2" which gets resolved to "2".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.