毕业论文论文范文课程设计实践报告法律论文英语论文教学论文医学论文农学论文艺术论文行政论文管理论文计算机安全
您现在的位置: 毕业论文 >> 课程设计 >> 正文

表达式计算器设计 第2页

更新时间:2009-5-2:  来源:毕业论文
 表达式计算器设计 第2页       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[]所代替。

我的不断改进的动力,就是力求让设计在追求其它目标的同时保持简洁。注意,这并不等于追求过于简单!我希望我的努力让我基本达到了这个目标。我除去了主要的耦合性,让相对不变的部分-表达式转换和计算部分独立出来,并把变化的部分-运算符和变量,开放出来。虽然在表达式解析上我还留有遗憾,表达式的一般解析接口过于宽泛了,未能为用户的扩展带来实质性的帮助。所幸缺省解析器的实现多少有所弥补。

最后,我希望这个关于表达式计算的设计和实现能够为他人所用和扩展。我愿意看到它能经受住考验。

上一页  [1] [2] 

表达式计算器设计 第2页下载如图片无法显示或论文不完整,请联系qq752018766
设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©751com.cn 辣文论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。