Shunting-Yard Algorithm with truth tables in Java

Question

I'm working on a truth table generator for one of my assignments in Discrete math.. I have to implement the shunting-yard algorithm, and I'm completely lost doing so. My problem, is implementing the shunting-yard algorithm. First I'll show what resources I've looked at, then my problem, then my code that I've started.

What I really need.. I know it's asking for a lot. But is a dumbed down version of the shunting-yard algorithm. I get lost in parts in the wikipedia example when notation is used such as o1 o2. What I really need is someone to explain step by step how to apply this. I'm not understanding how the RPN notation works either.. But that I can read up on now.

• An implementation of the shutting-yard:
  http://www.technical-recipes.com/2011/a-mathematical-expression-parser-in-java/#more-1658
• Wikipedia shutting yard algorithm:
  http://en.wikipedia.org/wiki/Shunting-yard_algorithm
• Someones problem on stackoverflow
  Problems with a shunting yard algorithm
• Basic implementation
  Generating truth tables in Java

Here's an example input:
A -> B
(C)
:. F

I'm supposed to generate an input that shows:
A-B-C-A->B-F
T-T-T--T---T
T-F-T--F---F
F-T-T--T---T
F-F-T--T---F
T-T-F--T---F
T-F-F--F---F
F-T-F--T---F
F-F-F--T---F

import java.util.Stack;
import java.util.ArrayList;

public class ShuttingYard{

private static final char THEREFORE = '>';
private static final char AND       = '&';
private static final char OR        = '|';


public static String inputToReversePolishNotation(String input)
{

    char[] tokens = input.toCharArray();
    ArrayList<String> output = new ArrayList<String>();
    Stack<String> oppStack = new Stack<String>();

    for(int i = 0; i < tokens.length; i++)
    {

    }

    return null;

}

public static boolean isLogicOperator(char input)
{

    switch(input)
    {
        case THEREFORE:
            return true;
        case AND:
            return true;
        case OR:
            return true;
        default:
            return false;
    }

}

}

Answer 1

The specific bit you mention giving you trouble, I believe, is this:

• If the token is an operator, o1, then:
  • while there is an operator token, o2, at the top of the stack, and
    • either o1 is left-associative and its precedence is less than or equal to that of o2, or
    • o1 has precedence less than that of o2,
  • pop o2 off the stack, onto the output queue;
• push o1 onto the stack.

I think it's understandable to be confused on this piece. Precedence rules are the reason RPN is much preferred for ease in parsing. In reading it, just remember, 'o1' is the operator you are reading in, and 'o2' is the operator at the top of the stack.

To handle it, you need to assign your operators precedence values. If we were discussing arithmetic, I might assign + = 1, * = 2 and ^ = 3 for precedence values, for instance. If the operator you are reading has been assigned a lower or equal precedence to the one at the top of the stack, you pop the operator from the stack and pass it to the output. Do that until you find an operator of lower precedence on the stack than the read operator, or no longer find an operator at the (new) top of the stack. Regardless, you will then push the read operator to the stack.

As far as a step-by-step of the whole thing, Wikipedia's write-up is pretty good. Keep in mind, that each rule defined may not apply to your case. Judging by the tokens you have defined, it looks like you don't need to worry about functions and parentheses, so the algorithm there can be simplified to:

• While there are tokens to be read:
  • Read a token.
  • If the token is a number, then add it to the output queue.
  • If the token is an operator, o1, then:
    • while there is an operator token, o2, at the top of the stack, and either o1 is left-associative and its precedence is less than or equal to that of o2, or o1 has precedence less than that of o2,
      • pop o2 off the stack, onto the output queue;
    • push o1 onto the stack.
• When there are no more tokens to read:
  • While there are still operator tokens in the stack:
    • Pop the operator onto the output queue.
• Exit.

Even if you do need parentheses and functions, it might help to start with the simpler problem, and enhance it once that is working.