问题由来在我做过的一个针对网络设备和主机的数据采集系统中某些采集到的数据需要经过一定的计算后才保存入库而不是仅仅保存其原始值为了提供给用户最大的灵活性我设想提供一个用户界面允许用户输入计算表达式（或者称为计算公式）这样除了需要遵从少量的规则用户可以得到最大的灵活性 这样的表达式具有什么特点呢？它一般不是纯的可立即计算的表达式（简单的如+*）它含有我称为变量的元素变量一般具有特殊的内定的语法例如可能用@totalmemory表示设备或主机（下面简称为设备）的物理内存总数那么表达式(@totalmemory@freememory)/@totalmemory*就表示设备当前内存使用率百分比如果与告警系统联系起来监测此值超过系统就发出Warning那么这就成为一件有意义的事情不同种类的采集数据入库前可能需要经过复杂度不同的计算但显然最后求值的时候必须将那些特定的变量用具体数值（即采集到的具体数值）替换否则表达式是不可计算的这个过程是在运行时发生的 问题的一般性我认为表达式计算是个一般性的话题并且也不是一个新的话题我们可能在多处碰到它我在读书的时候编写过一个表达式的转换和计算程序当时作为课余作业我看到过一些报表系统不管它是单独的还是包含在MIS系统财务软件中很多都支持计算公式我认为这些系统中的计算公式和我所遇到的问题是大致相同的对我来说我在数据采集项目中遇到这个问题下次可能还会在其他项目中遇到它既然已经不止一次了我希望找到一个一般性的解决方案 一些已有的设计和实现不能满足要求在设计和实现出第一个版本之后我自己感觉不很满意随后我花点时间上网搜索了一下（关键字表达式 中缀 后缀 or Expression Infix Postfix）令人稍感失望的是所找到的一些关于表达式的转换计算的程序不能满足我的要求不少这样的程序仅仅支持纯的可立即计算的表达式不支持变量而且表达式解析和计算是耦合在一起的很难扩展增加新的运算符（或新的变量语法）几乎必定要修改源代码在我看来这是最大的缺陷了（实际上当年我编写的表达式转换和计算的程序虽然当时引以自豪但是现在看来也具有同样的缺陷）但是表达式的转换和计算本身有成熟的基于栈的的经典算法许多计算机书籍或教材上都有论述人们以自然方式书写的表达式是中缀形式的先要把中缀表达式转换为后缀表达式然后计算后缀表达式的值我打算仍然采用这个经典的过程和算法 我的设计想法和目标既然表达式的转换和计算的核心算法是成熟的我渴望把它们提取出来去除（与解析相关的）耦合性！试想如果事物具有相对完整的内涵和独立性会产生这个需要并且也能够通过形式上的分离和提取来把内涵给表现出来这个过程离不开抽象我不久意识到自己实际上在设计一个小规模的关于表达式计算的框架 表达式要支持加减乘除运算符这是基本的立即想到的或许还应该支持平方开方（sqrt）三角运算符如sincos等那么如果还有其它怎么办包括自定义的运算符？你能确定考虑完备了吗？像自定义的运算符是完全存在的合理的需求在数据采集系统中我一度考虑引入一个diff运算符表明同一个累加型的采集量在相距最近的两次（即采集周期）采集的差值以上的思考促使我决定运算符的设计必须是开放的用户（这里指的是用户程序员下同）可以扩展增加新的运算符 表达式中允许含有变量对于变量的支持贯穿到表达式解析转换计算的全过程在解析阶段应该允许用户使用适合他/她自己的变量语法我不应该事先实现基于某种特定语法的变量识别 由于支持可扩展的运算符未知的变量语法甚至连基本的数值（象E）理论上也有多种类型和精度（Integer/Long/Float/Double/BigInteger/BigDecimal）这决定了无法提供一个固化的表达式解析方法表达式解析也是需要可扩展的最好的结果是提供一个容易使用和扩展的解析框架对于新的运算符新的变量语法用户在这个框架上扩展以提供增强的解析能力从抽象的角度来看我打算支持的表达式仅由四种元素组成括号（包括左右括号）运算符数值和变量一个最终用户给出的表达式字符串解析通过后可能生成了一个内部表示的便于后续处理的表达式组成这个表达式的每个元素只能是以上四种之一 数值一开始我写了一个表达数值的类叫做Numeral我为Numeral具体代表的是整数浮点数还是双精度数而操心从比较模糊的意义上我希望它能表达以上任何一种类型和精度的数值但是我也希望它能够明确表达出代表的具体是哪种类型和精度的数值如果需要的话甚至我想到Numeral最好也能表达BigInteger和BigDecimal（设想恰巧在某种场合下我们需要解析和计算一个这样的表达式它允许的数值的精度和范围很大以至于Long或Double容纳不下）否则在特别的场合下我们将遇到麻烦在可扩展性上数值类不大像运算符类它应该是成熟的因而几乎是不需要扩展的 经过反复尝试的混乱（Numeral后来又经过修改甚至重写）我找到了一个明智的办法直接用javalangNumber作为数值类（实际上这是一个接口）我庆幸地看到在Java中IntegerLongFloatDouble甚至BigIntegerBigDecimal等数值类都实现了javalangNumber（下面简称Number）接口使用者把Number作为何种类型和精度来看待和使用权利掌握在他/她的手中我不应该提前确定数值的类型和精度选择由Number类来表达数值这看来是最好的代价最小的选择了并且保持了相当的灵活性作为一个顺带的结果Numeral类被废弃了 括号在表达式中括号扮演的角色是不可忽视的它能改变运算的自然优先级按照用户所希望的顺序进行计算我用Bracket类来表示括号这个类可以看作是final因为它不需要扩展括号分作括号和右括号我把它们作为Bracket类的两个静态实例变量（并且是Bracket类仅有的两个实例变量） public class Bracket{ private String name; private Bracket(String name) { thisname = name; } public static final Bracket LEFT_BRACKET = new Bracket(() RIGHT_BRACKET = new Bracket()); public String toString() { return name; }} 运算符运算符的设计要求是开放的这几乎立即意味着它必须是抽象的我一度犹豫运算符是作为接口还是抽象类定义最后我选择的是抽象类 public abstract class Operator{ private String name; protected Operator(String name) { thisname = name; } public abstract int getDimension(); public abstract Number eval(Number[] oprands int offset); // throws ArithmeticException ? public Number eval(Number[] oprands) { return eval(oprands); } public String toString() { return name; }} 这个运算符的设计包含二个主接口方法通过getDimention()接口它传达这么一个信息运算符是几元的？即需要几个操作数显然最常见的是一元和二元运算符这个接口方法似乎也意味着允许有多于二元的运算符但是对于多于二元的运算符我没有作更深入的考察我不能十分确定基于栈的表达式的转换和计算算法是否完全支持二元以上的运算符尽管有这么一点担忧我还是保留目前的接口方法 运算符最主要的接口方法就是eval()这是运算符的计算接口反映了运算符的本质在这个接口方法中要把所有需要的操作数传给它运算符是几元的就需要几个操作数这应该是一致的然后执行符合运算符含义的计算返回结果如果增加新的运算符用户需要实现运算符的上述接口方法 变量从某种意义上说变量就是待定的数值我是否应该设计一个Variable类（或接口）？我的确这样做了变量什么时候被什么具体数值替代这些过程我不知道应该留给用户来处理我对于变量的知识几乎是零因此Variable类的意义就不大了如果继续保留这个类/接口还给用户带来一个限制他/她必须继承或实现Varibale类/接口因此不久之后我丢弃了Variable我只是声明和坚持这么一点在一个表达式中如果一个元素不是括号不是数值也不是运算符那么我就把它作为变量看待 表达式解析接口表达式解析所要解决的基本问题是对于用户给出的表达式字符串要识别出其中的数值运算符括号和变量然后转换成为内部的便于后续处理的表达式形式我提供了一个一般的表达式解析接口如下 public interface Parser{ Object[] parse(String expr) throws IllegalExpressionException;} 在这个解析接口中我只定义了一个方法parse()表达式串作为输入参数方法返回一个数组Object[]作为解析结果如果解析通过的话可以肯定数组中的元素或者是Number或者Operator或者Bracket如果它不是以上三种之一就把它视为变量 也许这样把表达式解析设计的过于一般了因为它回避了如何解析这个关键的问题而显得对于用户帮助不大表达式究竟如何解析在我看来是一个复杂的甚至困难的问题 主要困难在于无法提供一个现成的适用于各种表达式的解析实现请考虑用户可能会增加新的运算符引入新的变量语法甚至支持不同类型和精度的数值处理如前面所提到的如果能设计出一个表达式解析框架就好了让用户能够方便地在这个框架基础上扩展但是我没能完全做到这一点后面将提到已经实现的一个缺省的解析器（SimpleParser）这个缺省实现试图建立这样一个框架我觉得可能有一定的局限性 中缀表达式到后缀的转换这是通过一个转换器类Converter来完成的我能够把转换算法（以及下面的计算算法）独立出来让它不依赖于运算符或变量的扩展这得益于先前所做的基础工作对于表达式元素（数值括号运算符和变量）的分析和抽象算法的基本过程是这样的（读者可以从网上或相关书籍中查到我略作改动因为支持变量的缘故）创建一个工作栈和一个输出队列从左到右读取表达式当读到数值或变量时直接送至输出队列当读到运算符t时将栈中所有优先级高于或等于t的运算符弹出送到输出队列中然后t进栈读到左括号时总是将它压入栈中读到右括号时将靠近栈顶的第一个左括号上面的运算符全部依次弹出送至输出队列后再丢弃左括号在Converter类中核心方法convert()执行了上述的算法其输入是中缀表达式输出是后缀表达式完成了转换的过程
public abstract class Converter { public abstract int precedenceCompare(Operator op Operator op) throws UnknownOperatorException; public Object[] convert(Object[] infixExpr) throws IllegalExpressionException UnknownOperatorException { return convert(infixExpr infixExprlength); } public Object[] convert(Object[] infixExpr int offset int len) throws IllegalExpressionException UnknownOperatorException { if (infixExprlength offset < len) throw new IllegalArgumentException(); // 创建一个输出表达式用来存放结果 ArrayList output = new ArrayList(); // 创建一个工作栈 Stack stack = new Stack(); int currInputPosition = offset; // 当前位置（于输入队列） Systemoutprintln( Begin conversion procedure );//TEMP! while (currInputPosition < offset + len) { Object currInputElement = infixExpr[currInputPosition++]; if (currInputElement instanceof Number) // 数值元素直接输出 { outputadd(currInputElement); Systemoutprintln(NUMBER:+currInputElement);//TEMP! } else if (currInputElement instanceof Bracket) // 遇到括号进栈或进行匹配 { Bracket currInputBracket = (Bracket)currInputElement; if (currInputBracketequals(BracketLEFT_BRACKET)) { // 左括号进栈 stackpush(currInputElement); } else { // 右括号寻求匹配（左括号） // 弹出所有的栈元素(运算符)直到遇到(左)括号 Object stackElement; do { if (!stackempty()) stackElement = stackpop(); else throw new IllegalExpressionException(bracket(s) mismatch); if (stackElement instanceof Bracket) break; outputadd(stackElement); Systemoutprintln(OPERATOR POPUP:+stackElement);//TEMP! } while (true); } } else if (currInputElement instanceof Operator) { Operator currInputOperator = (Operator)currInputElement; // 弹出所有优先级别高于或等于当前的所有运算符 // (直到把满足条件的全部弹出或者遇到左括号) while (!stackempty()) { Object stackElement = stackpeek(); if (stackElement instanceof Bracket) { break;// 这一定是左括号没有可以弹出的了 } else { Operator stackOperator = (Operator)stackElement; if (precedenceCompare(stackOperator currInputOperator) >= ) { // 优先级高于等于当前的弹出（至输出队列） stackpop(); outputadd(stackElement); Systemoutprintln(OPERATOR:+stackElement);//TEMP! } else { // 优先级别低于当前的没有可以弹出的了 break; } } } // 当前运算符进栈 stackpush(currInputElement); } else //if (currInputElement instanceof Variable) // 其它一律被认为变量变量也直接输出 { outputadd(currInputElement); Systemoutprintln(VARIABLE:+currInputElement);//TEMP! } } // 将栈中剩下的元素(运算符)弹出至输出队列 while (!stackempty()) { Object stackElement = stackpop(); outputadd(stackElement); Systemoutprintln(LEFT STACK OPERATOR:+stackElement);//TEMP! } Systemoutprintln( End conversion procedure );//TEMP! return outputtoArray(); }} 读者可能很快注意到Converter类不是一个具体类既然算法是成熟稳定的并且我们也把它独立出来了为什么Converter类不是一个稳定的具体类呢？因为在转换过程中我发觉必须要面对一个运算符优先级的问题这是一个不可忽视的问题按照惯例如果没有使用括号显式地确定计算的先后顺序那么计算的先后顺序是通过比较运算符的优先级来确定的因为我无法确定用户在具体使用时他/她的运算符的集合有多大其中任意两个运算符之间的优先级顺序是怎样的这个知识只能由用户来告诉我说错了告诉给Converter类所以Converter类中提供了一个抽象的运算符比较接口precedenceCompare()由用户来实现 在一段时间内我为如何检验表达式的有效性而困惑我意识到转换通过了并不一定意味着表达式是必定合乎语法的有效的甚至接下来成功计算出后缀表达式的值也并不能证明原始表达式是有效的当然在某些转换失败或者计算失败的情况下例如运算符的元数与操作数数量不匹配左右括号不匹配等则可以肯定原始表达式是无效的但是证明一个表达式是有效的条件要苛刻的多遗憾的是我没能找到检验表达式有效性的理论根据 计算后缀表达式这是通过一个计算器类Calculator来完成的Calculator类的核心方法是eval()传给它的参数必须是后缀表达式在调用本方法之前如果表达式中含有变量那么应该被相应的数值替换掉否则表达式是不可计算的将导致抛出IncalculableExpressionException异常算法的基本过程是这样的创建一个工作栈从左到右读取表达式读到数值就压入栈中读到运算符就从栈中弹出N个数计算出结果再压入栈中N是该运算符的元数重复上述过程最后输出栈顶的数值作为计算结果结束
public class Calculator{ public Number eval(Object[] postfixExpr) throws IncalculableExpressionException { return eval(postfixExpr postfixExprlength); } public Number eval(Object[] postfixExpr int offset int len) throws IncalculableExpressionException { if (postfixExprlength offset < len) throw new IllegalArgumentException(); Stack stack = new Stack(); int currPosition = offset; while (currPosition < offset + len) { Object element = postfixExpr[currPosition++]; if (element instanceof Number) { stackpush(element); } else if (element instanceof Operator) { Operator op = (Operator)element; int dimensions = opgetDimension(); if (dimensions < || stacksize() < dimensions) throw new IncalculableExpressionException( lack operand(s) for operator +op+); Number[] operands = new Number [dimensions]; for (int j = dimensions ; j >= ; j) { operands[j] = (Number)stackpop(); } stackpush(opeval(operands)); } else throw new IncalculableExpressionException(Unknown element: +element); } if (stacksize() != ) throw new IncalculableExpressionException(redundant operand(s)); return (Number)stackpop(); }} 缺省实现前面我主要讨论了关于表达式计算的设计一个好的设计和实现中常常包括某些缺省的实现在本案例中我提供了基本的四则运算符的实现和一个缺省的解析器实现（SimpleParser） 运算符实现了加减乘除四种基本运算符 需要说明一点的是对于每种基本运算符当前缺省实现只支持Number是IntegerLongFloatDouble的情况并且需要关注一下不同类型和精度的数值相运算时结果数值的类型和精度如何确定缺省实现对此有一定的处理 解析器这个缺省的解析器实现我认为它是简单的故取名为SimpleParser其基本思想是把表达式看作是由括号数值运算符和变量组成每种表达式元素都可以相对独立地进行解析为此提供一种表达式元素解析器（ElementParser）SimpleParser分别调用四种元素解析器完成所有的解析工作 ElementParser提供了表达式元素级的解析接口四种缺省的表达式元素解析器类BasicNumberParser BasicOperatorParser DefaultBracketParserDefaultVariableParser均实现这个接口 public interface ElementParser{ Object[] parse(char[] expr int off);} 解析方法parse()输入参数指明待解析的串以及起始偏移返回结果中存放本次解析所得到的具体元素（NumberOperatorBracket或者Object）以及解析的截止偏移本次的截至偏移很可能就是下次解析的起始偏移如果不考虑空白符的话 那么在整个解析过程中每种元素解析器何时被SimpleParser所调用？我的解决办法是它依次调用每种元素解析器可以说这是一个尝试的策略尝试的先后次序是有讲究的依次是变量解析器〉运算符解析器〉数值解析器〉括号解析器 为什么执行这么一种次序？从深层次上反映了我的一种忧虑这就是表达式的解析可能是相当复杂的可能有这样的表达式对于它不能完全执行分而治之的解析方式因为存在需要整体解析的地方例如考虑diff(@TotalBytesReceived)这样的一个子串用户可能用它可能表达这样的含义取采集量TotalBytesReceived的前后两次采集的差值diff在这里甚至不能理解成传统意义上的运算符最终合理的选择很可能是把diff(@TotalBytesReceived)整个视为一个变量来解析和处理在这样的情况下拆开成diff(@bytereceived)分别来解析是无意义的错误的 这就是为什么变量解析器被最先调用这样做允许用户能够截获重新定义超越常规的解析方式以满足实际需要实际上我安排让变化可能性最大的部分（如变量）其解析器被最先调用最小的部分（如括号）其解析器被最后调用在每一步上如果解析成功那么后续的解析器就不会被调用如果在表达式串的某个位置上经过所有的元素解析器都不能解析那么该表达式就是不可解析的将抛出IllegalExpressionException异常 扩展实现由于篇幅的关系不在此通过例子讨论扩展实现这并不意味着目前没有一个扩展实现在前面提到的数据采集项目中由于基本初衷就是支持特别语法的变量结果我实现了一个支持变量的扩展实现并且支持了一些其他运算符除四则运算符之外相信读者能够看出我所做的工作体现和满足了可扩展性而扩展性主要体现在运算符和变量上 总结对于表达式计算我提出的要求有一定挑战性但也并不是太高然而为了接近或达到这个目标在设计上我颇费了一番功夫数易其稿前面提到我丢弃了Numeral类Variable类实际上还不止这些我还曾经设计了Element类表达式在内部就表示成一个数组Element[]在Element类中通过一个枚举变量指明它包含的到底是什么类型的元素（数值括号运算符还是变量）但是我嗅出这个做法不够清晰自然（如果追根究底可以说不够面向对象化）而最后丢弃了这个类相应地Element[]被更直接的Object[]所代替 我的不断改进的动力就是力求让设计在追求其它目标的同时保持简洁注意这并不等于追求过于简单！我希望我的努力让我基本达到了这个目标我除去了主要的耦合性让相对不变的部分表达式转换和计算部分独立出来并把变化的部分运算符和变量开放出来虽然在表达式解析上我还留有遗憾表达式的一般解析接口过于宽泛了未能为用户的扩展带来实质性的帮助所幸缺省解析器的实现多少有所弥补 最后我希望这个关于表达式计算的设计和实现能够为他人所用和扩展我愿意看到它能经受住考验 作者简介刘源男软件工程师您可以通过和作者取得联系 |
