Monday, January 21, 2013

Shunting Yard Algorithm

The Shunting Yard Algorithm converts infix notation to postfix notation (also known as reverse polish notation).  It was invented by Edsger Dijkstra.

Resource: Wikipedia article "Shunting Yard Algorithm"

The following pseudocode was derived from the following resources:
While there are tokens to be read:
  Read a token

  If the token is a number:
    Add token to the result stack

  If the token is a left parenthesis:
    Push token onto operators stack

  If the token is a right parenthesis:
    While the token at the top of the stack is not a left parenthesis:
      Pop token from operator stack and push it onto the result stack
    Pop the left parenthesis, but do not put it onto the result stack

  If the token is an operator:
    While the operator at the top of the operators stack has higher or equal precedence:
      Pop operator off operators stack and push it onto the result stack
    Push read in token onto operators stack

While the operators stack is not empty:
  Pop operator and push it onto the result stack
Here's what the Java implementation looks like:
public class ShuntingYard {

  public boolean isOperator(String token) {
    return isAddition(token) || isSubtraction(token) || isDivision(token) || isMultiplication(token);
  }

  public boolean isAddition(String token) {
    return "+".equals(token);
  }

  public boolean isSubtraction(String token) {
    return "-".equals(token);
  }

  public boolean isMultiplication(String token) {
    return "*".equals(token);
  }
  
  public boolean isDivision(String token) {
    return "/".equals(token);
  }

  public boolean isRightParenthesis(String token) {
    return ")".equals(token);
  }

  public boolean isLeftParenthesis(String token) {
    return "(".equals(token);
  }
  
  // Please Excuse My Dear Aunt Sally (Parenthesis Exponents Multiplication Division Addition Subtraction)
  // Multiplication and Division have the same precedence.  So do Addition and Subtraction.
  public int getPrecedence(String operator) {
    if(isAddition(operator) || isSubtraction(operator)) {
      return 1;
    }

    if(isMultiplication(operator) || isDivision(operator)) {
      return 2;
    }
    
    return -1;    
  }
  
  public boolean isNumber(String token) {
    try {      
      Double.parseDouble(token);
      return true;
    }
    catch(NumberFormatException numberFormat) {        
    }
    
    try {
      Integer.parseInt(token);
      return true;
    }
    catch(NumberFormatException numberFormat) {        
    }

    return false;
  }
  
  public Stack<String> toPostfix(String infix) throws IOException {
    return toReversePolishNotation(infix);
  }
  
  // Algorithm is based on the following resources: 
  // http://www.usna.edu/Users/cs/taylor/courses/ic312/class/project1.shtml
  // http://people.cs.vt.edu/~shaffer/AVCourse/ShuntingYard.ppt   
  public Stack<String> toReversePolishNotation(String infix) throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(infix);
    Stack<String> result = new Stack<String>();
    Stack<String> operators = new Stack<String>();    
    String token;

    //  While there are tokens to be read:    
    while(tokenizer.hasMoreElements()) {
      
      // Read a token
      token = tokenizer.nextToken();

      // If the token is a number:
      if(isNumber(token)) {
        
        // Add token to the result stack
        result.push(token);        
      }
                
      // If the token is a left parenthesis:
      if(isLeftParenthesis(token)) {
        
        // Push token onto operators stack
        operators.push(token);
      }
        
      // If the token is a right parenthesis:
      if(isRightParenthesis(token)) {
             
        // While the token at the top of the operator stack is not a left parenthesis:          
        while(!isLeftParenthesis(operators.peek())) {
          
          // Pop token from operator stack and push it onto the result stack
          result.push(operators.pop());
        }
        
        // Pop the left parenthesis, but do not put it onto the result stack
        operators.pop();
      }
        
      // If the token is an operator:
      if(isOperator(token)) {
        
        // While the operator at the top of the operators stack has higher or equal precedence:                        
        while(!operators.isEmpty() && (getPrecedence(token) <= getPrecedence(operators.peek()))) {
          
          // Pop operator off operators stack and push it onto the result stack
          result.push(operators.pop());
        }
        
        // Push read in token onto operators stack
        operators.push(token);        
      }
    }

    // While the operators stack is not empty:    
    while(!operators.isEmpty()) {
      // Pop operator and push it onto the result stack
      result.push(operators.pop());
    }
        
    return result;
  }

}

No comments:

Post a Comment