Postfix Expression Evaluator

yiwi

• /**
  
• * filename: PostfixEvaluator.java
  
• * package:  
  
• * author:   Li Ma
  
• * email:    nick.ma85@yahoo.com
  
• * date:     Oct 3, 2008 (created)
  
• *                       Nov 2, 2008 (modified)
  
• * description: this class evaluates postfix expression.
  
• */
  
• 
  
• import java.util.*;
  
• 
  
• public class PostfixEvaluator {
  
•         
  
•         /** the stack stores operands */
  
•         private Stack<Integer> operandStack;
  
•         
  
•         /** each operator(char) has a integer value of priority */
  
•         private static final Map<Character, Integer> OPERATORS;
  
•         
  
•         /** postfix expression */
  
•         private String postfix;
  
•         
  
•         static {
  
•                 // initialize the static field
  
•                 OPERATORS = new HashMap<Character, Integer>();
  
•                 OPERATORS.put('+', 1);
  
•                 OPERATORS.put('-', 1);
  
•                 OPERATORS.put('*', 2);
  
•                 OPERATORS.put('/', 2);
  
•         }
  
•         
  
•         /**
  
•          * description: the constructor with fields
  
•          */
  
•         public PostfixEvaluator(String postfix) {
  
•                 // TODO Auto-generated constructor stub
  
•                 operandStack = new Stack<Integer>();
  
•                 this.postfix = postfix;
  
•         }
  
• 
  
•         /**
  
•          * description: determine whether the character is an operator
  
•          * @param ch - the character to be tested
  
•          * @return      true if ch is an operator
  
•          */
  
•         private boolean isOperator(char ch) {
  
•                 return OPERATORS.containsKey(ch);
  
•         }
  
•         
  
•         /**
  
•          * description: evaluate the current operation, poping the two operands off
  
•          * the operand stack and applying the operator.
  
•          * @param op - a character representing the operator
  
•          * @return the result of applying the operator
  
•          */
  
•         private int evalOp(char op) {
  
•                 // pop the two operands off the stack
  
•                 int rhs = operandStack.pop();
  
•                 int lhs = operandStack.pop();
  
•                 int result = 0;
  
•                
  
•                 // evaluate the operator
  
•                 switch(op) {
  
•                 case '+':
  
•                         result = lhs + rhs;
  
•                         break;
  
•                 case '-':
  
•                         result = lhs - rhs;
  
•                         break;
  
•                 case '*':
  
•                         result = lhs * rhs;
  
•                         break;
  
•                 case '/':
  
•                         result = lhs / rhs;
  
•                         break;
  
•                 }
  
•                 return result;
  
•         }
  
•         
  
•         /**
  
•          * description: evaluate the whole infix expression
  
•          * @return      the value of the infix expression
  
•          * @throws SyntaxErrorException
  
•          */
  
•         public int eval() throws SyntaxErrorException {
  
•                
  
•                 // process each token
  
•                 StringTokenizer tokens = new StringTokenizer(this.postfix);
  
•                 try {
  
•                         while(tokens.hasMoreTokens()) {
  
•                                 String next = tokens.nextToken();
  
•                                 
  
•                                 if(Character.isDigit(next.charAt(0))) {
  
•                                         int value = Integer.parseInt(next);
  
•                                        
  
•                                         // push value onto operand stack
  
•                                         operandStack.push(value);
  
•                                 } else if(isOperator(next.charAt(0))) {
  
•                                         // it is an operator
  
•                                         // evaluate the operator
  
•                                         int result = evalOp(next.charAt(0));
  
•                                         operandStack.push(result);
  
•                                 } else {
  
•                                         throw new SyntaxErrorException(&quot;Invalid character encountered&quot;);
  
•                                 }
  
•                         }
  
•                         
  
•                         // no more tokens, pop result from operand stack
  
•                         int answer = operandStack.pop();
  
•                         if(operandStack.empty()) {
  
•                                 return answer;
  
•                         } else {
  
•                                 // indicate syntax error
  
•                                 throw new SyntaxErrorException(&quot;Stack should be empty&quot;);
  
•                         }
  
•                 } catch(EmptyStackException e) {
  
•                         throw new SyntaxErrorException(&quot;the stack is empty&quot;);
  
•                 }
  
•         }
  
• 
  
• }
  
• 
  
• /**
  
• * filename: SyntaxErrorException.java
  
• * package:  
  
• * author:   Li Ma
  
• * email:    nick.ma85@yahoo.com
  
• * date:     Oct 3, 2008
  
• * description: this exception shows a syntax error.
  
• */
  
• 
  
• public class SyntaxErrorException extends Exception {
  
• 
  
•         private static final long serialVersionUID = 1L;
  
• 
  
•         public SyntaxErrorException(final String message) {
  
•                 super(message);
  
•         }
  
• }
  
•