# Boolean expressions from infix to postfix notation using Dijkstra's Shunting Yard algorithm

I began working on a Java library that receives a boolean expression such as not A and (B or not C), compiles it to a circuit of logical gates $\mathcal{C}$, minimizes $\mathcal{C}$, and converts back to a (possibly shorter) boolean expression. Now, first things first: I need to be able to tokenize each input expression and change them from infix notation to postfix notation so as to be able to construct straighforwardly the actual circuit. Edsger Dijkstra's Shunting-yard algorithm does just that in linear time and space. That's what I have at this point:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {

/**
* The name of AND operator.
*/
public static final String AND = "and";

/**
* The name of NOT operator.
*/
public static final String NOT = "not";

/**
* The name of OR operator.
*/
public static final String OR = "or";

/**
* Exit command.
*/
public static final String QUIT = "quit";

/**
* The default operator precedence: NOT, AND, OR.
*/
private static final Map<String, Integer> defaultPrecedenceMap;

static {
defaultPrecedenceMap = new HashMap<>();
defaultPrecedenceMap.put(NOT, 1);
defaultPrecedenceMap.put(AND, 2);
defaultPrecedenceMap.put(OR, 3);
}

/**
* Calls for Shunting Yard algorithm with default operator precedence.
*
* @param  tokens the tokens in infix notation.
* @return the list of tokens in postfix notation, or <code>null</code> if
* the input token list is invalid.
*/
public static List<String> shuntingYard(final Deque<String> tokens) {
return shuntingYard(tokens, defaultPrecedenceMap);
}

/**
* Returns a list of tokens in postfix notation. If the input list of tokens
* is invalid (by having, say, incorrect parenthesization),
* <code>null</code> is returned.
*
* @param tokens        the tokens in infix notation.
* @param precedenceMap the operator precedence map.
* @return the list of tokens in postfix notation, or <code>null</code> if
*         the input token list is invalid.
*/
public static List<String>
shuntingYard(final Deque<String> tokens,
final Map<String, Integer> precedenceMap) {
final Deque<String> operatorStack = new LinkedList<>();
final Deque<String> outputQueue = new LinkedList<>();
String previousToken = "";

while (!tokens.isEmpty()) {
final String currentToken = tokens.removeFirst();

if (isVariableOrConstantName(currentToken)) {
} else if (isOperator(currentToken)) {
while (!operatorStack.isEmpty()) {
if (isOperator(operatorStack.getLast())
&& precedenceCompare(operatorStack.getLast(),
currentToken,
precedenceMap)) {
} else {
break;
}
}

} else if (currentToken.equals("(")) {
if (isVariableOrConstantName(previousToken)) {
return null;
}

} else if (currentToken.equals(")")) {
if (!isVariableOrConstantName(previousToken)) {
return null;
}

while (!operatorStack.isEmpty() &&
!operatorStack.getLast().equals("(")) {
}

if (operatorStack.isEmpty()) {
// Parenthesis structure is invalid.
return null;
} else {
// remove left parenthesis '('
operatorStack.removeLast();
}
} else {
throw new IllegalStateException(
"Could not recognize a token: " + currentToken);
}

previousToken = currentToken;
}

while (!operatorStack.isEmpty()) {
final String operator = operatorStack.removeLast();

// Parenthesis structure is invalid.
if (operator.equals("(") || operator.equals(")")) {
return null;
}

}

return new ArrayList<>(outputQueue);
}

/**
* Compares <code>stackTopToken</code> and <code>token</code> by their
* precedences.
*
* @param  stackTopToken the token at the top of operator stack.
* @param  token         the token to compare against.
* @param  precedenceMap the operator precedence map.
* @return <code>true</code> if the token at the top of the stack precedes
*         <code>token</code>.
*/
private static boolean
precedenceCompare(final String stackTopToken,
final String token,
final Map<String, Integer> precedenceMap) {
return precedenceMap.get(stackTopToken) < precedenceMap.get(token);
}

/**
* Checks whether the input token is a variable or constant name.
*
* @param  token the token to check.
* @return <code>true</code> if and only if <code>token</code> is a constant
*         (such as "0" or "1") or any other token that cannot be recognized
*         as an operator, parenthesis, or a constant.
*/
private static boolean isVariableOrConstantName(final String token) {
if (isOperator(token)) {
return false;
}

if (token.equals("(")) {
return false;
}

if (token.equals(")")) {
return false;
}

return !token.isEmpty();
}

/**
* Checks whether the input token denotes an operator such as AND, NOT, OR.
*
* @param  token the token to check.
* @return <code>true</code> if and only if <code>token</code> is an
*         operator.
*/
private static boolean isOperator(final String token) {
switch (token) {
case AND:
case NOT:
case OR:
return true;

default:
return false;
}
}

/**
* Splits the input text into a list of tokens.
*
* @param  text the text to split.
* @return the list of tokens.
*/
private static Deque<String> toTokenList(final String text) {
final Deque<String> tokenList = new ArrayDeque<>();

int index = 0;

while (index < text.length()) {
if (text.substring(index).startsWith(AND)) {
index += AND.length();
} else if (text.substring(index).startsWith(OR)) {
index += OR.length();
} else if (text.substring(index).startsWith(NOT)) {
index += NOT.length();
} else if (text.charAt(index) == '(') {
++index;
} else if (text.charAt(index) == ')') {
++index;
} else if (text.charAt(index) == '0') {
++index;
} else if (text.charAt(index) == '1') {
++index;
} else {
int index2 = index;

while (index2 < text.length()
&& !Character.isWhitespace(text.charAt(index2))
&& text.charAt(index2) != '('
&& text.charAt(index2) != ')') {
++index2;
}

final String variableName = text.substring(index, index2);
index += variableName.length();
}

}

}

/**
* Advances the input index to a position with non-whitespace character.
*
* @param  text  the text.
* @param  index the index.
* @return the index no less than <code>index</code> at which text contains
*         a non-whitespace character.
*/
private static int advancePastWhitespace(final String text, int index) {
while (index < text.length()
&& Character.isWhitespace(text.charAt(index))) {
++index;
}

return index;
}

/**
* The demo program.
*
* @param args ignored.
*/
public static void main(final String... args) {
final Scanner scanner = new Scanner(System.in);

while (scanner.hasNextLine()) {
final String line = scanner.nextLine().trim().toLowerCase();

if (line.equals(QUIT)) {
break;
}

final List<String> postfixTokenList =
shuntingYard(toTokenList(line));

if (postfixTokenList == null) {
System.out.println("Invalid token sequence!");
} else {
postfixTokenList.stream().forEach((token) -> {
System.out.print(token + " ");
});

System.out.println();
}
}

System.out.println("Bye!");
}
}


To my understanding, the algorithm is not supposed to "fix" an invalid expression in infix notation (for example, a or b not); it just produces a notation that may be recognized later (at construction of $\mathcal{C}$) as broken.

So what do you think? Should I rewrite it in more OOP style? Any improvements of commenting/naming/anything else?

• In isVariableOrConstantName check isEmpty() first, as if it's empty there's no reason to do the other comparisons. May 6, 2015 at 18:06
• You could make the tokenizer simpler by using a regular expression. Also all the operators could be placed in a hash map that contains the precedence as values. Then you don't need the final variables AND, OR and NOT. May 6, 2015 at 23:41