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