The Shunting Yard Algorithm

This following class can be used to convert from partially parenthesized infix expressions to their equivalent postfix expressions.


import java.util.Stack;

public class ShuntingYard {
    
    public String[][] opsByPrecedence = {{"+","-"},{"*","/"},{"^"}};
    public String[] rightAssociativeOps = {"^"};
    
    private boolean isOp(String s) {
        for (int i = 0; i < opsByPrecedence.length; i++) {
            for (int j = 0; j < opsByPrecedence[i].length; j++) {
                if (s.equals(opsByPrecedence[i][j])) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean isRightAssociative(String op) {
        for (int i = 0; i < rightAssociativeOps.length; i++) {
            if (op.equals(rightAssociativeOps[i])) {
                return true;
            }
        }
        return false;
    }
    
    private int getPrecedence(String op) {
        for (int i = 0; i < opsByPrecedence.length; i++) {
            for (int j = 0; j < opsByPrecedence[i].length; j++) {
                if (op.equals(opsByPrecedence[i][j])) {
                    return i;
                }
            }
        }
        throw new RuntimeException("Invalid op specified (" + op + ")");
    }
    
    public String toPostFix(String expression) {
        
        String[] tokens = expression.split(" ");
        Stack ops = new Stack();
        String postFixStr = "";
        
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("(")) {
                ops.push(tokens[i]);
            }
            else if (tokens[i].equals(")")) {
                while (! ops.peek().equals("(")) {
                    postFixStr += ops.pop() + " ";
                }
                ops.pop(); //pop the remaining "(" and throw it away
            }
            else if (! isOp(tokens[i])) {
                postFixStr += tokens[i] + " ";
            }
            else { // tokens[i] is an operator...
                
                boolean tokenProcessed = false; // we might have some work to do first before
                                                // we can push this token...
                
                while ( ! tokenProcessed ) {
                    if (ops.isEmpty() || ops.peek().equals("(")) {  
                        ops.push(tokens[i]);
                        tokenProcessed = true;
                    }
                    else {
                        String topOp = ops.peek();
                        
                        if ((getPrecedence(tokens[i]) > getPrecedence(topOp)) ||
                            ((getPrecedence(tokens[i]) == getPrecedence(topOp)) && 
                                     isRightAssociative(tokens[i]))) {
                            ops.push(tokens[i]);
                            tokenProcessed = true;
                        }
                        else {
                            postFixStr += ops.pop() + " ";
                        } 
                    } 
                } 
            } 
        } //end for loop (all tokens now are in postFixStr or the ops stack now)
        
        // we finish by moving elements from the stack to postFixStr...
        while (! ops.isEmpty()) {
            postFixStr += ops.pop() + " ";
        }
        
        return postFixStr;
    } 

    public static void main(String[] args) {
        ShuntingYard sy = new ShuntingYard();
        System.out.println(sy.toPostFix("A + ( B - C )"));
    }
}