Infix to Postfix Convertor
[*]/**
[*] * filename: InfixToPostfixConvertor.java
[*] * package:
[*] * author: Nick Ma
[*] * email: nick.ma85@yahoo.com
[*] * date: Nov 1, 2008
[*] * description: this class implements a string convertor from infix to postfix.
[*] */
[*]
[*]import java.util.*;
[*]
[*]public class InfixToPostfixConvertor {
[*]
[*] // Data Field
[*]
[*] /** the operator stack */
[*] private Stack<Character> operatorStack;
[*]
[*] /** the operators */
[*] private static final String OPERATORS = "+-*/()";
[*]
[*] /** the precedence of the operators */
[*] private static final int[] PRECEDENCE = {1, 1, 2, 2, -1, -1};
[*]
[*] /** the postfix string */
[*] private StringBuilder postfix;
[*]
[*] /**
[*] * description: the default constructor
[*] */
[*] public InfixToPostfixConvertor() {
[*] // TODO Auto-generated constructor stub
[*]
[*] postfix = new StringBuilder();
[*] }
[*]
[*] /**
[*] * description: convert a string from infix to postfix
[*] * @param infix - the infix string to input
[*] * @return - the postfix string
[*] * @throws Exception
[*] */
[*] public String convert(String infix) throws Exception {
[*] operatorStack = new Stack<Character>();
[*]
[*] StringTokenizer infixTokens = new StringTokenizer(infix);
[*] try {
[*] // process each token in the infix string
[*] while(infixTokens.hasMoreTokens()) {
[*] String nextToken = infixTokens.nextToken();
[*] char firstChar = nextToken.charAt(0);
[*] // determine if it is an operator
[*] if(Character.isJavaIdentifierStart(firstChar)
[*] || Character.isDigit(firstChar)){
[*] postfix.append(nextToken);
[*] postfix.append(' ');
[*] } else if(isOperator(firstChar)) {
[*] processOperator(firstChar);
[*] } else {
[*] throw new SyntaxErrorException("syntax error!");
[*] }
[*] }
[*]
[*] // pop any remaining operators and append them to postfix
[*] while(!operatorStack.isEmpty()) {
[*] Character op = operatorStack.pop();
[*] // any '(' on the stack is not matched
[*] if(op.charValue() == '(') {
[*] throw new SyntaxErrorException("syntax error!");
[*] }
[*] postfix.append(op);
[*] postfix.append(' ');
[*] }
[*] return postfix.toString();
[*] } catch(EmptyStackException e) {
[*] throw new SyntaxErrorException("the stack is empty!");
[*] }
[*] }
[*]
[*] /**
[*] * description: process operators
[*] * @param op - the operator
[*] */
[*] private void processOperator(char op) {
[*] if(operatorStack.isEmpty() || op == '(') {
[*] operatorStack.push(op);
[*] } else {
[*] // peek the operator stack
[*] char topOp = operatorStack.peek().charValue();
[*] if(precedence(op) > precedence(topOp)) {
[*] operatorStack.push(op);
[*] } else {
[*] // pop all stacked operators with equal or higher precedence than op
[*] while(!operatorStack.isEmpty() && precedence(op) <= precedence(topOp)) {
[*] operatorStack.pop();
[*] if(topOp == '(') {
[*] break;
[*] }
[*] postfix.append(topOp);
[*] postfix.append(' ');
[*] if(!operatorStack.isEmpty()) {
[*] // reset topOp
[*] topOp = operatorStack.peek().charValue();
[*] }
[*] }
[*] if(op != ')') {
[*] operatorStack.push(op);
[*] }
[*] }
[*] }
[*] }
[*]
[*] /**
[*] * description: determine the precedence of an operator
[*] * @param op - the operator
[*] * @return - the precedence
[*] */
[*] private int precedence(char op) {
[*] return PRECEDENCE;
[*] }
[*]
[*] /**
[*] * description: determine whether a char is an operator
[*] * @param op - the given char
[*] * @return - true if the char is an operator
[*] */
[*] private boolean isOperator(char op) {
[*] return OPERATORS.indexOf(op) != -1;
[*] }
[*]
[*] // test function
[*] public static void main(String[] args) {
[*] InfixToPostfixConvertor pc = new InfixToPostfixConvertor();
[*] try {
[*] System.out.println(pc.convert("( x + y ) * ( ( a + b ) / c )"));
[*] } catch(Exception e) {
[*] e.printStackTrace();
[*] }
[*] }
[*]}
[*]
[*]
[*]/**
[*] * 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]