现在的位置: 首页 > 综合 > 正文

Postfix Expression Evaluator

2014年10月03日 ⁄ 综合 ⁄ 共 4885字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

  1. /**
  2.  * filename: PostfixEvaluator.java
  3.  * package:  
  4.  * author:   Li Ma
  5.  * email:    nick.ma85@yahoo.com
  6.  * date:     Oct 3, 2008 (created)
  7.  *                       Nov 2, 2008 (modified)
  8.  * description: this class evaluates postfix expression.
  9.  */
  11. import
     java.util.*;
  13. public
     
    class
     PostfixEvaluator {
  14.         
  15.         
    /** the stack stores operands */
  16.         
    private
     Stack<Integer> operandStack;
  17.         
  18.         
    /** each operator(char) has a integer value of priority */
  19.         
    private
     
    static
     
    final
     Map<Character, Integer> OPERATORS;
  20.         
  21.         
    /** postfix expression */
  22.         
    private
     String postfix;
  23.         
  24.         
    static
     {
  25.                 
    // initialize the static field
  26.                 OPERATORS = 
    new
     HashMap<Character, Integer>();
  27.                 OPERATORS.put(
    '+'
    , 
    1
    );
  28.                 OPERATORS.put(
    '-'
    , 
    1
    );
  29.                 OPERATORS.put(
    '*'
    , 
    2
    );
  30.                 OPERATORS.put(
    '/'
    , 
    2
    );
  31.         }
  32.         
  33.         
    /**
  34.          * description: the constructor with fields
  35.          */
  36.         
    public
     PostfixEvaluator(String postfix) {
  37.                 
    // TODO Auto-generated constructor stub
  38.                 operandStack = 
    new
     Stack<Integer>();
  39.                 
    this
    .postfix = postfix;
  40.         }
  42.         
    /**
  43.          * description: determine whether the character is an operator
  44.          * @param ch - the character to be tested
  45.          * @return      true if ch is an operator
  46.          */
  47.         
    private
     
    boolean
     isOperator(
    char
     ch) {
  48.                 
    return
     OPERATORS.containsKey(ch);
  49.         }
  50.         
  51.         
    /**
  52.          * description: evaluate the current operation, poping the two operands off 
  53.          * the operand stack and applying the operator.
  54.          * @param op - a character representing the operator
  55.          * @return the result of applying the operator
  56.          */
  57.         
    private
     
    int
     evalOp(
    char
     op) {
  58.                 
    // pop the two operands off the stack
  59.                 
    int
     rhs = operandStack.pop();
  60.                 
    int
     lhs = operandStack.pop();
  61.                 
    int
     result = 
    0
    ;
  62.                 
  63.                 
    // evaluate the operator
  64.                 
    switch
    (op) {
  65.                 
    case
     
    '+'
    :
  66.                         result = lhs + rhs;
  67.                         
    break
    ;
  68.                 
    case
     
    '-'
    :
  69.                         result = lhs - rhs;
  70.                         
    break
    ;
  71.                 
    case
     
    '*'
    :
  72.                         result = lhs * rhs;
  73.                         
    break
    ;
  74.                 
    case
     
    '/'
    :
  75.                         result = lhs / rhs;
  76.                         
    break
    ;
  77.                 }
  78.                 
    return
     result;
  79.         }
  80.         
  81.         
    /**
  82.          * description: evaluate the whole infix expression
  83.          * @return      the value of the infix expression
  84.          * @throws SyntaxErrorException
  85.          */
  86.         
    public
     
    int
     eval() 
    throws
     SyntaxErrorException {
  87.                 
  88.                 
    // process each token
  89.                 StringTokenizer tokens = 
    new
     StringTokenizer(
    this
    .postfix);
  90.                 
    try
     {
  91.                         
    while
    (tokens.hasMoreTokens()) {
  92.                                 String next = tokens.nextToken();
  93.                                 
  94.                                 
    if
    (Character.isDigit(next.charAt(
    0
    ))) {
  95.                                         
    int
     value = Integer.parseInt(next);
  96.                                         
  97.                                         
    // push value onto operand stack
  98.                                         operandStack.push(value);
  99.                                 } 
    else
     
    if
    (isOperator(next.charAt(
    0
    ))) {
  100.                                         
    // it is an operator
  101.                                         
    // evaluate the operator
  102.                                         
    int
     result = evalOp(next.charAt(
    0
    ));
  103.                                         operandStack.push(result);
  104.                                 } 
    else
     {
  105.                                         
    throw
     
    new
     SyntaxErrorException(
    "Invalid character encountered"
    );
  106.                                 }
  107.                         }
  108.                         
  109.                         
    // no more tokens, pop result from operand stack
  110.                         
    int
     answer = operandStack.pop();
  111.                         
    if
    (operandStack.empty()) {
  112.                                 
    return
     answer;
  113.                         } 
    else
     {
  114.                                 
    // indicate syntax error
  115.                                 
    throw
     
    new
     SyntaxErrorException(
    "Stack should be empty"
    );
  116.                         }
  117.                 } 
    catch
    (EmptyStackException e) {
  118.                         
    throw
     
    new
     SyntaxErrorException(
    "the stack is empty"
    );
  119.                 }
  120.         }
  122. }
  124. /**
  125.  * filename: SyntaxErrorException.java
  126.  * package:  
  127.  * author:   Li Ma
  128.  * email:    nick.ma85@yahoo.com
  129.  * date:     Oct 3, 2008
  130.  * description: this exception shows a syntax error.
  131.  */
  133. public
     
    class
     SyntaxErrorException 
    extends
     Exception {
  135.         
    private
     
    static
     
    final
     
    long
     serialVersionUID = 1L;
  137.         
    public
     SyntaxErrorException(
    final
     String message) {
  138.                 
    super
    (message);
  139.         }
  140. }
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞