4
\$\begingroup\$

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.LinkedList;
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)) {
                outputQueue.add(currentToken);
            } else if (isOperator(currentToken)) {
                while (!operatorStack.isEmpty()) {
                    if (isOperator(operatorStack.getLast())
                            && precedenceCompare(operatorStack.getLast(),
                                                 currentToken,
                                                 precedenceMap)) {
                        outputQueue.addLast(operatorStack.removeLast());
                    } else {
                        break;
                    }
                }

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

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

                while (!operatorStack.isEmpty() && 
                       !operatorStack.getLast().equals("(")) {
                    outputQueue.addLast(operatorStack.removeLast());
                }

                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;
            }

            outputQueue.addLast(operator);
        }

        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();
                tokenList.add(AND);
            } else if (text.substring(index).startsWith(OR)) {
                index += OR.length();
                tokenList.add(OR);
            } else if (text.substring(index).startsWith(NOT)) {
                index += NOT.length();
                tokenList.add(NOT);
            } else if (text.charAt(index) == '(') {
                ++index;
                tokenList.add("(");
            } else if (text.charAt(index) == ')') {
                ++index;
                tokenList.add(")");
            } else if (text.charAt(index) == '0') {
                ++index;
                tokenList.add("0");
            } else if (text.charAt(index) == '1') {
                ++index;
                tokenList.add("1");
            } 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();
                tokenList.add(variableName);
            }

            index = advancePastWhitespace(text, index);
        }

        return tokenList;
    }

    /**
     * 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?

\$\endgroup\$
  • 1
    \$\begingroup\$ In isVariableOrConstantName check isEmpty() first, as if it's empty there's no reason to do the other comparisons. \$\endgroup\$ – Snowbody May 6 '15 at 18:06
  • \$\begingroup\$ 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. \$\endgroup\$ – SpiderPig May 6 '15 at 23:41
1
\$\begingroup\$

I think the code is very well written.

But, as you suggest, it should be more object oriented. I see two objects which are calling to be extracted: a Tokenizer and the InfixToPostfixConverter(better name required).

The Tokenizer should read its input from the scanner and have a method to get the next token as a string. The Converter could be feed with tokens and fill the outputQueue.

This way you separate the two problems. Moreover you can put the tokenization process in parallel with the shuntingYard algorithm without the need of a buffer to keep the tokens.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.