Leetcode [224] Basic Calculator 基于语法树的解法

importjava.util.function.BooleanSupplier;
publicclassCalculator {
staticenumTokenType {
NUMBER,
PLUS_SIGN('+'),
MINUS_SIGN('-'),
LEFT_PARENTHESIS('('),
RIGHT_PARENTHESIS(')'),
END,
        ;
privatecharc;
TokenType(){
this.c=0;
        }
TokenType(charc){
this.c=c;
        }
staticTokenTypegetByChar(charc){
for(TokenTypetype : values()){
if(type.c!=0&&type.c==c){
returntype;
                }
            }
returnnull;
        }
    }
staticclassToken {
TokenTypetype;
Stringtext;
Token(){}
Token(TokenTypetype, Stringtext){
this.type=type;
this.text=text;
        }
    }
staticclassLexer {
Stringsource;
char[] chars;
intpos;
Tokennext;
Lexer(Stringsource){
this.source=source;
this.chars=source.toCharArray();
this.pos=0;
        }
TokengetNext(){
if(next!=null){
TokentheNext=next;
next=null;
returntheNext;
            }
while(pos<chars.length&&Character.isSpaceChar(chars[pos])){
pos++;
            }
if(pos==chars.length){
returnnewToken(TokenType.END, null);
            }
Tokentoken=newToken();
TokenTypetype;
if((type=TokenType.getByChar(chars[pos])) !=null){
token.type=type;
pos++;
            }else{
// 只能是一个数字 tokenintlen=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;
            }
returntoken;
        }
TokenpeekNext(){
if(this.next!=null){
returnthis.next;
            }
this.next=getNext();
returnthis.next;
        }
booleanisEnd(){
returnpos==source.length();
        }
    }
staticclassParser {
Lexerlexer;
Parser(Lexerlexer){
this.lexer=lexer;
        }
ExpressionparseAll(){
returnparseArithmeticExpression(()->this.lexer.isEnd());
        }
ExpressionparseArithmeticExpression(BooleanSupplierendFunc){
ArithmeticExpressionexp=newArithmeticExpression();
ExpressionunaryExp=parseUnaryExpression();
exp.leftExpression=unaryExp;
while(!endFunc.getAsBoolean()){
Tokenoperator=lexer.getNext();
exp.arithmeticType=ArithmeticType.getFromToken(operator);
exp.rightExpression=parseUnaryExpression();
ArithmeticExpressionexpWrapper=newArithmeticExpression();
expWrapper.leftExpression=exp;
exp=expWrapper;
            }
returnexp;
        }
ExpressionoccurError(TokencurrentToken){
returnEmptyExpression.getSingleton();
        }
ExpressionparseUnaryExpression(){
Tokentoken=lexer.getNext();
switch(token.type){
caseEND:{
returnEmptyExpression.getSingleton();
                }
caseNUMBER:{
returnnewConstExpression(token.text);
                }
caseLEFT_PARENTHESIS:{
returnparseParenthesisExpression();
                }
caseMINUS_SIGN:{
returnnewUnaryMinusExpression(parseUnaryExpression());
                }
default:{
returnoccurError(token);
                }
            }
        }
ExpressionparseParenthesisExpression(){
Expressionexp=parseArithmeticExpression(()->this.lexer.peekNext().type==TokenType.RIGHT_PARENTHESIS);
this.lexer.getNext(); // pass 右括号returnexp;
        }
    }
staticinterfaceExpression {
intevaluate();
    }
staticclassEmptyExpressionimplementsExpression{
privatestaticfinalEmptyExpressionexp=newEmptyExpression();
privateEmptyExpression(){}
@Overridepublicintevaluate(){
return0;
        }
publicstaticEmptyExpressiongetSingleton(){
returnexp;
        }
    }
staticclassConstExpressionimplementsExpression{
privateStringtext;
ConstExpression(Stringtext){
this.text=text;
        }
@Overridepublicintevaluate() {
returnInteger.valueOf(this.text);
        }
    }
staticenumArithmeticType{
NO,
PLUS,
MINUS,
        ;
staticArithmeticTypegetFromToken(Tokentoken){
if(token.type==TokenType.PLUS_SIGN){
returnArithmeticType.PLUS;
            }
if(token.type==TokenType.MINUS_SIGN){
returnArithmeticType.MINUS;
            }
returnArithmeticType.NO;
        }
    }
staticclassArithmeticExpressionimplementsExpression {
privateExpressionleftExpression;
privateExpressionrightExpression;
privateArithmeticTypearithmeticType=ArithmeticType.NO;
@Overridepublicintevaluate() {
switch(arithmeticType){
casePLUS: {
returnleftExpression.evaluate() +rightExpression.evaluate();
                }
caseMINUS :{
returnleftExpression.evaluate() -rightExpression.evaluate();
                }
caseNO:{
returnleftExpression.evaluate();
                }
            }
return0;
        }
    }
staticclassUnaryMinusExpressionimplementsExpression {
privateExpressionoperand;
UnaryMinusExpression(Expressionoperand){
this.operand=operand;
        }
@Overridepublicintevaluate() {
return-operand.evaluate();
        }
    }
publicintevaluate(Stringsource){
Parserparser=newParser(newLexer(source));
returnparser.parseAll().evaluate();
    }
}