ExpressionCalculator.java

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Expression Calculator
 */
public class ExpressionCalculator {
    private final Stack<Operand> operandStack = new Stack<Operand>();
    private final Stack<Operator> operatorStack = new Stack<Operator>(); // possible: operator or left bracket

    /**
     * pop operator and calculate it, then save result to operand stack
     */
    private void calculate() {
        Operator operator = (Operator) operatorStack.pop();
        Operand operand2 = operandStack.pop();
        Operand operand1 = operandStack.pop();
        int result = operator.calculate(operand1, operand2);
        operandStack.push(Operand.valueOf(result));
    }

    /**
     * calculate the entire expression
     *
     * @param infix
     * @return
     */
    public double calculate(Element[] infix) {
        for(Element element : infix) {
//            System.out.print("=> ");
//            ArrayUtil.print(operandStack.toArray());
//            System.out.print("<= ");
//            ArrayUtil.print(operatorStack.toArray());
//            System.out.println();
            if(element instanceof Operand) {
                Operand operand = (Operand) element;
                operandStack.push(operand);
            }
            else if(element == Operator.LEFT_BRACKET) {
                Operator leftBrace = (Operator) element;
                operatorStack.push(leftBrace);
            }
            else if(element == Operator.RIGHT_BRACKET) { // right bracket
                boolean leftBracketFound = false;
                while (!operatorStack.empty()) {
                    Operator top = operatorStack.peek();
                    if(top != Operator.LEFT_BRACKET) {
                        calculate();
                    } else {
                        leftBracketFound = true;
                        operatorStack.pop(); // remove left bracket
                        break;
                    }
                }
                if(!leftBracketFound) {
                    throw new IllegalArgumentException("cannot find left brace for a right brace");
                }
            }
            else { // Operator
                Operator operator = (Operator) element;
                while (!operatorStack.empty()) {
                    Operator top = operatorStack.peek();
                    if(operator.priority <= top.priority) {
                        calculate();
                    } else {
                        break;
                    }
                }
                operatorStack.push(operator);



            }
        }
        while (!operatorStack.empty()) {
            calculate();
        }

        return operandStack.pop().value;
    }


    /**
     * get its postfix expression
     *
     * @param infix
     * @return
     */
    public Element[] postfix(Element[] infix) {

        List<Element> postfix = new ArrayList<Element>();
        for (Element element : infix) {
            if(element instanceof Operand) {
                postfix.add(element);
            }
            else if(element == Operator.LEFT_BRACKET) {
                operatorStack.push((Operator)element);
            }
            else if(element == Operator.RIGHT_BRACKET) {
                boolean leftBracketFound = false;
                while (!operatorStack.empty()) {
                    Operator top = operatorStack.peek();
                    if(top != Operator.LEFT_BRACKET) {
                        operatorStack.pop();
                        postfix.add(top);
                    } else {
                        leftBracketFound = true;
                        operatorStack.pop(); // remove left bracket
                        break;
                    }
                }
                if(!leftBracketFound) {
                    throw new IllegalArgumentException("cannot find left brace for a right brace");
                }
            }
            else if(element instanceof Operator) {
                Operator operator = (Operator) element;
                while (!operatorStack.empty()) {
                    Operator top = operatorStack.peek();
                    if(operator.priority <= top.priority) { // * -
                        operatorStack.pop();
                        postfix.add(top);
                    } else {
                        break;
                    }
                }
                operatorStack.push(operator);
            }
        }
        while (!operatorStack.empty()) {
            postfix.add(operatorStack.pop());
        }

        return postfix.toArray(new Element[postfix.size()]);
    }

    public double calculatePostfix(Element[] postfix) {
        for(Element element : postfix) {
            if(element instanceof Operand) {
                operandStack.push((Operand) element);
            }
            else if(element instanceof Operator) {
                operatorStack.push((Operator) element);
                calculate();
            }
        }
        return operandStack.pop().value;
    }

    private static abstract class Element {}

    private static class Operand extends Element {
        int value;

        private Operand(int value) { this. value = value; }
        public static Operand valueOf(int value) {
            return new Operand(value);
        }

        public String toString() {
            return String.valueOf(value);
        }
    }

    private static class Operator extends Element {

        public final static Operator PLUS = new Operator('+', 1, 2);
        public final static Operator MINUS = new Operator('-', 1, 2);
        public final static Operator MULTIPLY = new Operator('*', 2, 2);
        public final static Operator DIVIDE = new Operator('/', 2, 2);
        public final static Operator MODULO = new Operator('%', 2, 2);

        public final static Operator LEFT_BRACKET = new Operator('(', 0, 0);
        public final static Operator RIGHT_BRACKET = new Operator(')', 100, 0);

        char value;
        int priority;
        int operandCount;

        private Operator(char value, int priority, int operands) {
            this.value = value;
            this.priority = priority;
            this.operandCount = operands;
        }

        public int calculate(Operand...operands) {
            assert operands != null && operands.length == operandCount;
            if(this.value == '+') return operands[0].value + operands[1].value;
            if(this.value == '-') return operands[0].value - operands[1].value;
            if(this.value == '*') return operands[0].value * operands[1].value;
            if(this.value == '/') return operands[0].value / operands[1].value;
            if(this.value == '%') return operands[0].value % operands[1].value;
            throw new UnsupportedOperationException("unsupported operator");
        }

        public static Operator valueOf(char value) {
            if(value == '+') return PLUS;
            if(value == '-') return MINUS;
            if(value == '*') return MULTIPLY;
            if(value == '/') return DIVIDE;
            if(value == '%') return MODULO;

            if(value == '(') return LEFT_BRACKET;
            if(value == ')') return RIGHT_BRACKET;

            throw new UnsupportedOperationException("unsupported operator");
        }

        public String toString() {
            return String.valueOf(value);
        }
    }

    public static Element[] fromString(String expression) {
        char[] chars = expression.toCharArray();
        Element[] elements = new Element[chars.length];
        for(int i = 0; i < chars.length; ++i) {
            char ch = chars[i];
            if(Character.isDigit(ch)) {
                elements[i] = Operand.valueOf(Integer.parseInt(String.valueOf(ch)));
            } else {
                elements[i] = Operator.valueOf(ch);
            }
        }
        return elements;
    }

    public static void print(Element[] elements) {
        for(int i=0; i < elements.length; ++i) {
            System.out.print(elements[i]);
        }
        System.out.println();
    }

    @Test
    public void test() {
        Element[] infix1 = fromString("5-(5-3*1+4)-6/3*4");
        print(infix1);
        System.out.println(calculate(infix1));

        Element[] postfix1 = postfix(infix1);
        print(postfix1);
        System.out.println(calculatePostfix(postfix1));

        Element[] infix2 = fromString("5-(5-3*1+4)-(6/3*(8/2-3)-4)");
        print(infix2);
        System.out.println(calculate(infix2));

        Element[] postfix2 = postfix(infix2);
        print(postfix2);
        System.out.println(calculatePostfix(postfix2));

        Element[] infix3 = fromString("5-(5-3*1+4)-(6/3*(8%3-3)-4)");
        print(infix3);
        System.out.println(calculate(infix3));

        Element[] postfix3 = postfix(infix3);
        print(postfix3);
        System.out.println(calculatePostfix(postfix3));
    }
}