《设计模式就该这样学》之这个无敌设计，可以解析并运算任意数学表达式

《设计模式就该这样学》之这个无敌设计，可以解析并运算任意数学表达式

本文节选自《设计模式就该这样学》

1　使用解释器模式解析数学表达式

下面用解释器模式来实现一个数学表达式计算器，包含加、减、乘、除运算。首先定义抽象表达式角色IArithmeticInterpreter接口。

public interface IArithmeticInterpreter {
    int interpret();
}

创建终结表达式角色Interpreter抽象类。

public abstract class Interpreter implements IArithmeticInterpreter {

    protected IArithmeticInterpreter left;
    protected IArithmeticInterpreter right;

    public Interpreter(IArithmeticInterpreter left, IArithmeticInterpreter right) {
        this.left = left;
        this.right = right;
    }
}

然后分别创建非终结符表达式角色加、减、乘、除解释器，加法运算表达式AddInterpreter类的代码如下。

public class AddInterpreter extends Interpreter {

    public AddInterpreter(IArithmeticInterpreter left, IArithmeticInterpreter right) {
        super(left, right);
    }

    public int interpret() {
        return this.left.interpret() + this.right.interpret();
    }
}

减法运算表达式SubInterpreter类的代码如下。

public class SubInterpreter extends Interpreter {
    public SubInterpreter(IArithmeticInterpreter left, IArithmeticInterpreter right) {
        super(left, right);
    }

    public int interpret() {
        return this.left.interpret() - this.right.interpret();
    }
}

乘法运算表达式MultiInterpreter类的代码如下。

public class MultiInterpreter extends Interpreter {

    public MultiInterpreter(IArithmeticInterpreter left, IArithmeticInterpreter right){
        super(left,right);
    }

    public int interpret() {
        return this.left.interpret() * this.right.interpret();
    }

}

除法运算表达式DivInterpreter类的代码如下。

public class DivInterpreter extends Interpreter {

    public DivInterpreter(IArithmeticInterpreter left, IArithmeticInterpreter right){
        super(left,right);
    }

    public int interpret() {
        return this.left.interpret() / this.right.interpret();
    }

}

数字表达式NumInterpreter类的代码如下。

public class NumInterpreter implements IArithmeticInterpreter {
    private int value;

    public NumInterpreter(int value) {
        this.value = value;
    }


    public int interpret() {
        return this.value;
    }
}

接着创建计算器GPCalculator类。

public class GPCalculator {
    private Stack stack = new Stack();

    public GPCalculator(String expression) {
        this.parse(expression);
    }

    private void parse(String expression) {
        String [] elements = expression.split(" ");
        IArithmeticInterpreter left,right;

        for (int i = 0; i < elements.length ; i++) {
            String operator = elements[i];
            if(OperatorUtil.ifOperator(operator)){
                left = this.stack.pop();
                right = new NumInterpreter(Integer.valueOf(elements[++i]));
                System.out.println("出栈" + left.interpret() + "和" + right.interpret());
                this.stack.push(OperatorUtil.getInterpreter(left,right,operator));
                System.out.println("应用运算符：" + operator);
            }else {
                NumInterpreter numInterpreter = new NumInterpreter(Integer.valueOf(elements[i]));
                this.stack.push(numInterpreter);
                System.out.println("入栈：" + numInterpreter.interpret());
            }

        }
    }

    public int calculate() {
        return this.stack.pop().interpret();
    }
}

工具类OperatorUtil的代码如下。

public class OperatorUtil {

    public static boolean isOperator(String symbol) {
        return (symbol.equals("+") || symbol.equals("-") || symbol.equals("*"));
    }

    public static Interpreter getInterpreter(IArithmeticInterpreter left, IArithmeticInterpreter 
    right, String symbol) {
        if (symbol.equals("+")) {
            return new AddInterpreter(left, right);
        } else if (symbol.equals("-")) {
            return new SubInterpreter(left, right);
        } else if (symbol.equals("*")) {
            return new MultiInterpreter(left, right);
        } else if (symbol.equals("/")) {
            return new DivInterpreter(left, right);
        }
        return null;
    }
}

最后编写客户端测试代码。

public static void main(String[] args) {
        System.out.println("result: " + new GPCalculator("10 + 30").calculate());
        System.out.println("result: " + new GPCalculator("10 + 30 - 20").calculate());
        System.out.println("result: " + new GPCalculator("100 * 2 + 400 * 1 + 66").calculate());
}

运行结果如下图所示。

当然，上面的简易计算器还没有考虑优先级，就是从左至右依次运算的。在实际运算中，乘法和除法属于一级运算，加法和减法属于二级运算。一级运算需要优先计算。另外，我们可以通过使用括号手动调整运算的优先级。我们再优化一下代码，首先新建一个枚举类。

public enum OperatorEnum {
    LEFT_BRACKET("("),
    RIGHT_BRACKET(")"),
    SUB("-"),
    ADD("+"),
    MULTI("*"),
    DIV("/"),
    ;
    private String operator;

    public String getOperator() {
        return operator;
    }

    OperatorEnum(String operator) {
        this.operator = operator;
    }
}

然后修改OperatorUtil的处理逻辑，设置两个栈。

public class OperatorUtil {

    public static Interpreter getInterpreter(Stack numStack, Stack operatorStack) {
        IArithmeticInterpreter right = numStack.pop();
        IArithmeticInterpreter left = numStack.pop();
        String symbol = operatorStack.pop();
        System.out.println("数字出栈：" + right.interpret() + "," + left.interpret() + ", *** 作符出栈:" + symbol);
        if (symbol.equals("+")) {
            return new AddInterpreter(left, right);
        } else if (symbol.equals("-")) {
            return new SubInterpreter(left, right);
        } else if (symbol.equals("*")) {
            return new MultiInterpreter(left, right);
        } else if (symbol.equals("/")) {
            return new DivInterpreter(left, right);
        }
        return null;
    }
}

修改GPCalculator的代码。

public class GPCalculator {

    //数字stack
    private Stack numStack = new Stack();
    // *** 作符stack
    private Stack operatorStack = new Stack();
    
    public GPCalculator(String expression) {
        this.parse(expression);
    }

    private void parse(String input) {
        //对表达式去除空字符 *** 作
        String expression = this.fromat(input);
        System.out.println("标准表达式：" + expression);
        for (String s : expression.split(" ")) {
            if (s.length() == 0){
                //如果是空格，则继续循环，什么也不 *** 作
                continue;
            }
            //如果是加减，因为加减的优先级最低，所以这里只要遇到加减号，无论 *** 作符栈中是什么运算符都要运算
            else if (s.equals(OperatorEnum.ADD.getOperator())
                    || s.equals(OperatorEnum.SUB.getOperator())) {
                //当栈不是空的，并且栈中最上面的一个元素是加减乘除的任意一个
                while (!operatorStack.isEmpty()
                        &&(operatorStack.peek().equals(OperatorEnum.SUB.getOperator())
                        || operatorStack.peek().equals(OperatorEnum.ADD.getOperator())
                        || operatorStack.peek().equals(OperatorEnum.MULTI.getOperator())
                        || operatorStack.peek().equals(OperatorEnum.DIV.getOperator()))) {
                    //结果存入栈中
                    numStack.push(OperatorUtil.getInterpreter(numStack,operatorStack));
                }
                //运算完后将当前的运算符入栈
                System.out.println(" *** 作符入栈:"+s);
                operatorStack.push(s);
            }
            //当前运算符是乘除的时候，因为优先级高于加减
           //所以要判断最上面的是否是乘除，如果是乘除，则运算，否则直接入栈
            else if (s.equals(OperatorEnum.MULTI.getOperator())
                    || s.equals(OperatorEnum.DIV.getOperator())) {
                while (!operatorStack.isEmpty()&&(
                        operatorStack.peek().equals(OperatorEnum.MULTI.getOperator())
                        || operatorStack.peek().equals(OperatorEnum.DIV.getOperator()))) {
                    numStack.push(OperatorUtil.getInterpreter(numStack,operatorStack));
                }
                //将当前 *** 作符入栈
                System.out.println(" *** 作符入栈:"+s);
                operatorStack.push(s);
            }
            //如果是左括号，则直接入栈，什么也不用 *** 作，trim()函数是用来去除空格的，由于上面的分割                  *** 作，可能会令 *** 作符带有空格
            else if (s.equals(OperatorEnum.LEFT_BRACKET.getOperator())) {
                System.out.println(" *** 作符入栈:"+s);
                operatorStack.push(OperatorEnum.LEFT_BRACKET.getOperator());
            }
            //如果是右括号，则清除栈中的运算符直至左括号
            else if (s.equals(OperatorEnum.RIGHT_BRACKET.getOperator())) {
                while (!OperatorEnum.LEFT_BRACKET.getOperator().equals(operatorStack.peek())) {
                    //开始运算
                    numStack.push(OperatorUtil.getInterpreter(numStack,operatorStack));
                }
                //运算完之后清除左括号
                String pop = operatorStack.pop();
                System.out.println("括号运算 *** 作完成，清除栈中右括号："+pop);
            }
            //如果是数字，则直接入数据的栈
            else {
                //将数字字符串转换成数字，然后存入栈中
                NumInterpreter numInterpreter = new NumInterpreter(Integer.valueOf(s));
                System.out.println("数字入栈："+s);
                numStack.push(numInterpreter);
            }
        }
        //最后当栈中不是空的时候继续运算，直到栈为空即可
        while (!operatorStack.isEmpty()) {
            numStack.push(OperatorUtil.getInterpreter(numStack,operatorStack));
        }
    }

    
    public int calculate() {
        return this.numStack.pop().interpret();
    }

    
    private String fromat(String expression) {
        String result = "";
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '(' || expression.charAt(i) == ')' ||
                expression.charAt(i) == '+' || expression.charAt(i) == '-' ||
                expression.charAt(i) == '*' || expression.charAt(i) == '/')
                //在操作符与数字之间增加一个空格
                result += (" " + expression.charAt(i) + " ");
            else
                result += expression.charAt(i);
        }
        return result;
    }
}

此时，再来看客户端测试代码。

public static void main(String[] args) {
        System.out.println("result: " + new GPCalculator("10+30/((6-4)*2-2)").calculate());
}

运行得到预期的结果，如下图所示。

2　解释器模式在JDK源码中的应用

先来看JDK源码中的Pattern对正则表达式的编译和解析。

public final class Pattern implements java.io.Serializable {
    ...
    private Pattern(String p, int f) {
        pattern = p;
        flags = f;

        if ((flags & UNICODE_CHARACTER_CLASS) != 0)
            flags |= UNICODE_CASE;


        capturingGroupCount = 1;
        localCount = 0;

        if (pattern.length() > 0) {
            compile();
        } else {
            root = new Start(lastAccept);
            matchRoot = lastAccept;
        }
    }
    ...
    public static Pattern compile(String regex) {
        return new Pattern(regex, 0);
    }
    public static Pattern compile(String regex, int flags) {
        return new Pattern(regex, flags);
    }

    ...
}

3　解释器模式在Spring源码中的应用

再来看Spring中的expressionParser接口。

public interface expressionParser {

    expression parseexpression(String expressionString) throws ParseException;

    expression parseexpression(String expressionString, ParserContext context) throws ParseException;

}

这里我们不深入讲解源码，通过我们前面编写的案例大致能够清楚其原理。不妨编写一段客户端代码验证一下。客户端测试代码如下。

public static void main(String[] args) {
    expressionParser parser = new SpelexpressionParser();
    expression expression = parser.parseexpression("100 * 2 + 400 * 1 + 66");
    int result = (Integer) expression.getValue();
    System.out.println("计算结果是：" + result);
}

运行结果如下图所示。

由上图可知，运行结果与预期的结果是一致的。

 设计模式系列文

《设计模式就该这样学》之彻底搞懂Spring状态机原理，实现订单与物流解耦

《设计模式就该这样学》之手写自定义迭代器，秒懂迭代器底层原理 

《设计模式就该这样学》之意外发现，原来你不知道自己每天都在用门面模式

《设计模式就该这样学》之实战案例，让抽象工厂不再抽象 

《设计模式就该这样学》之简单工厂模式那些你没有关注过的细节 

《设计模式就该这样学》之委派模式详解 

《设计模式就该这样学》之使用桥接模式设计复杂的消息系统 

《设计模式就该这样学》之使用策略模式重构电商折扣和支付场景 

《设计模式就该这样学》之趣谈装饰器模式，让你一辈子不会忘 

《设计模式就该这样学》之基于Guava API实现异步通知和事件回调