Leetcode [224] Basic Calculator 基于文法樹的解法

代碼

import java.util.function.BooleanSupplier;


public class Calculator {

    static enum TokenType {
        NUMBER,
        PLUS_SIGN('+'),
        MINUS_SIGN('-'),
        LEFT_PARENTHESIS('('),
        RIGHT_PARENTHESIS(')'),
        END,
        ;

        private char c;
        TokenType(){
            this.c = 0;
        }
        TokenType(char c){
            this.c = c;
        }

        static TokenType getByChar(char c){
            for(TokenType type : values()){
                if(type.c != 0 && type.c == c){
                    return type;
                }
            }
            return null;
        }
    }
    static class Token {
        TokenType type;
        String text;
        Token(){}
        Token(TokenType type, String text){
            this.type = type;
            this.text = text;
        }
    }
    static class Lexer {
        String source;
        char[] chars;
        int pos;
        Token next;
        Lexer(String source){
            this.source = source;
            this.chars = source.toCharArray();
            this.pos = 0;
        }
        Token getNext(){
            if(next != null){
                Token theNext = next;
                next = null;
                return theNext;
            }
            while(pos < chars.length && Character.isSpaceChar(chars[pos])){
                pos++;
            }
            if(pos == chars.length){
                return new Token(TokenType.END, null);
            }
            Token token = new Token();
            TokenType type;
            if((type = TokenType.getByChar(chars[pos])) != null){
                token.type = type;
                pos++;
            }else{
                // 隻能是一個數字 token
                int len = 1;
                while(pos+len < chars.length && Character.isDigit(chars[pos+len])){
                    len++;
                }
                token.type = TokenType.NUMBER;
                token.text = this.source.substring(pos, pos+len);
                pos += len;
            }
            return token;
        }
        Token peekNext(){
            if(this.next != null){
                return this.next;
            }
            this.next = getNext();
            return this.next;
        }
        boolean isEnd(){
            return pos == source.length();
        }
    }
    static class Parser {
        Lexer lexer;
        Parser(Lexer lexer){
            this.lexer = lexer;
        }
        Expression parseAll(){
            return parseArithmeticExpression(()->this.lexer.isEnd());
        }

        Expression parseArithmeticExpression(BooleanSupplier endFunc){
            ArithmeticExpression exp = new ArithmeticExpression();
            Expression unaryExp = parseUnaryExpression();
            exp.leftExpression = unaryExp;
            while(!endFunc.getAsBoolean()){
                Token operator = lexer.getNext();
                exp.arithmeticType = ArithmeticType.getFromToken(operator);
                exp.rightExpression = parseUnaryExpression();
                ArithmeticExpression expWrapper = new ArithmeticExpression();
                expWrapper.leftExpression = exp;
                exp = expWrapper;
            }
            return exp;
        }

        Expression occurError(Token currentToken){
            return EmptyExpression.getSingleton();
        }

        Expression parseUnaryExpression(){
            Token token = lexer.getNext();
            switch(token.type){
                case END:{
                    return EmptyExpression.getSingleton();
                }
                case NUMBER:{
                    return new ConstExpression(token.text);
                }
                case LEFT_PARENTHESIS:{
                    return parseParenthesisExpression();
                }
                case MINUS_SIGN:{
                    return new UnaryMinusExpression(parseUnaryExpression());
                }
                default:{
                    return occurError(token);
                }
            }
        }

        Expression parseParenthesisExpression(){
            Expression exp = parseArithmeticExpression(()->this.lexer.peekNext().type == TokenType.RIGHT_PARENTHESIS);
            this.lexer.getNext(); // pass 右括号
            return exp;
        }
    }


    static interface Expression {
        int evaluate();
    }

    static class EmptyExpression implements Expression{
        private static final EmptyExpression exp = new EmptyExpression();
        private EmptyExpression(){}
        @Override
        public int evaluate(){
            return 0;
        }
        public static EmptyExpression getSingleton(){
            return exp;
        }
    }

    static class ConstExpression implements Expression{
        private String text;
        ConstExpression(String text){
            this.text = text;
        }
        @Override
        public int evaluate() {
            return Integer.valueOf(this.text);
        }
    }

    static enum ArithmeticType{
        NO,
        PLUS,
        MINUS,
        ;
        static ArithmeticType getFromToken(Token token){
            if(token.type == TokenType.PLUS_SIGN){
                return ArithmeticType.PLUS;
            }
            if(token.type == TokenType.MINUS_SIGN){
                return ArithmeticType.MINUS;
            }
            return ArithmeticType.NO;
        }
    }
    static class ArithmeticExpression implements Expression {
        private Expression leftExpression;
        private Expression rightExpression;
        private ArithmeticType arithmeticType = ArithmeticType.NO;

        @Override
        public int evaluate() {
            switch(arithmeticType){
                case PLUS: {
                    return leftExpression.evaluate() + rightExpression.evaluate();
                }
                case MINUS :{
                    return leftExpression.evaluate() - rightExpression.evaluate();
                }
                case NO:{
                    return leftExpression.evaluate();
                }
            }
            return 0;
        }
    }

    static class UnaryMinusExpression implements Expression {
        private Expression operand;
        UnaryMinusExpression(Expression operand){
            this.operand = operand;
        }
        @Override
        public int evaluate() {
            return - operand.evaluate();
        }
    }

    public int evaluate(String source){
        Parser parser = new Parser(new Lexer(source));
        return parser.parseAll().evaluate();
    }
    
}