Postfix Expression Evaluator
[*]/**
[*] * 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("Invalid character encountered");
[*] }
[*] }
[*]
[*] // no more tokens, pop result from operand stack
[*] int answer = operandStack.pop();
[*] if(operandStack.empty()) {
[*] return answer;
[*] } else {
[*] // indicate syntax error
[*] throw new SyntaxErrorException("Stack should be empty");
[*] }
[*] } catch(EmptyStackException e) {
[*] throw new SyntaxErrorException("the stack is empty");
[*] }
[*] }
[*]
[*]}
[*]
[*]/**
[*] * 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);
[*] }
[*]}
[*]
页:
[1]