Verifying Mathematical Expressions

Question

This is a part of my calculator program. I have to check if the input entered by the user is a valid mathematical expression. The first check is performed by another program, where the program checks if the numbers and symbols are valid and it converts the string into tokens for further verification. The implementation of that program is trivial and thus not covered here.

The following program processes these tokens and outputs whether the expression is valid or not. The tokens are of two types:

1. Numbers: {"10", "5.27", "-91.22"}

2. Symbols: {"+", "-", "*", "/", "^", "!", "(", ")"}

The program handles parentheses differently and does not care about factorial as it's an unary operator. First, I'll describe the Expression class as it defines what an expression is and how its state is calculated.

A valid expression is a number or an unchanged state. So, if the whole expression contains a number then it's valid. If it contains a number, an operator and another number, it makes the entire expression a number. It also makes sure that parentheses are balanced (if present).

Valid expressions: {"1", "1+2", "1+2*3", "1*(2+3)", "(1+2)"}

Invalid expressions: {"1*(2", "1+", "+", "1)*2"}

The state of the expression is considered true if it's valid and false otherwise. The state of the expression is changed when a number is added or parenthesis count is changed. Exceptions are thrown whenever an invalid combination is found.

Note: The program doesn't calculate the expression it just verifies it.

Expression.java

/**
 * Tracks the state of the expression.
 */
class Expression {

    private boolean numberPresent;
    private boolean operatorPresent;
    private boolean state;
    private int openParCount;
    private boolean stateChanged;
    private boolean parStateChanged;

    void addNumber() throws ExpressionFormatException {
        if (!numberPresent) {
            numberPresent = true;
        } else if (operatorPresent) {
            // if operator is present, make the entire expression a number
            operatorPresent = false;
        } else {
            throw new ExpressionFormatException();
        }
        stateChanged = true;
    }

    void addOperator(String aOperator) throws ExpressionFormatException {
        if (numberPresent && !operatorPresent) {
            operatorPresent = true;
        } else {
            throw new ExpressionFormatException();
        }
    }

    /**
     * Modify open parenthesis count.
     */
    void modParCount(int n) {
        openParCount += n;
        parStateChanged = true;
        stateChanged = true;
    }

    boolean hasStateChanged() {
        return stateChanged;
    }

    /**
     * Get the current state of the expression.
     * @return a boolean value.
     */
    boolean getState() {
        if (!numberPresent && !operatorPresent) {
            // if parenthesis state is changed a number needs to be present
            state = !parStateChanged;
        } else if (numberPresent && operatorPresent) {
            state = false;
        } else if (numberPresent) {
            state = true;
        }

        // return true only if the state is true and parentheses are balanced
        return state && openParCount == 0;
    }
}

Now, I'll describe the Verifier class, mainly its isComputable method. The verify method starts the ball rolling, it passes isComputable the token array and the starting offset. The isComputable method makes a localExpression and adds a number or an operator whenever it encounters it. The method recurses when it encounters a "(" and if the localExpression's state is changed. It returns when the control flow drops or it encounters a ")". The method also changes the state of the parentheses in a localExpression. The method returns immediately if the subState, the expression nested inside it, is not valid or ExpressionFormatException is caught.

Verifier.java

import java.util.*;


class Verifier {

    private static Set<String> validOperators = Set.of("+", "-", "*", "/", "^");

    /**
     * Passes tokens and the starting offset to isComputable to verify the expression
     *
     * @param tokens contains valid numbers and symbols.
     * @return a boolean value returned by isComputable.
     */
    static boolean verify(ArrayList<String> tokens) {
        return isComputable(tokens, new int[] {0});
    }

    /**
     * Verifies the state of the expression and its nested expressions recursively.
     *
     * @param tokens a list containing valid numbers and symbols.
     * @param offset keeps track of the current position in the list.
     * @return a boolean value denoting whether the expression is valid.
     */
    private static boolean isComputable(ArrayList<String> tokens, int[] offset) {
        var localExpression = new Expression();
        var subState = true;

        while(offset[0] < tokens.size()) {
            String token = tokens.get(offset[0]);

            try {
                if (Evaluator.isNumber(token)) {
                    localExpression.addNumber();
                } else if (validOperators.contains(token)) {
                    localExpression.addOperator(token);
                } else if (token.equals("(")) {
                    if (localExpression.hasStateChanged()) {
                        // recurse if the state of the current expression has changed
                        subState = isComputable(tokens, offset);
                        if (!subState) {
                            return false;
                        } else {
                            localExpression.addNumber();
                        }
                    } else {
                        // if state is unchanged increase open parenthesis count
                        localExpression.modParCount(1);
                    }
                } else if (token.equals(")")) {
                    // decrease open parenthesis count
                    localExpression.modParCount(-1);
                    return localExpression.getState();
                }
            } catch (ExpressionFormatException e) {
                return false;
            }

            offset[0]++;
        }

        return localExpression.getState();
    }
}

Evaluator.isNumber and ExpressionFormatException are not a part of this program and are too trivial to include here.

Below are some tests:

Output   Input

true  -> "2+1"
true  -> "2+2*(5+6)"
true  -> "2+3+4+5+6"
true  -> "2!+3^5"
true  -> "-5*3+-1"
true  -> "4+2*(6+2)/(4-2)/(2*(65+(3*4)))"
true  -> "3"
false -> "(2+2"
false -> "2!(3)"
false -> "2**2"
false -> "5+()"
false -> "--1"
false -> "+3"
false -> ")"

Note: The input is shown in Strings to aid readability.

Issues:

1. Expression like "1/0" are considered valid as the Expression object does not care what kind of number it's receiving. Similarly, negative factorials are also allowed.

2. Unary minus is supported but unary plus is not (not yet).

3. The index is the first element in the int[] offset that is passed recursively to keep track of index.

Any help would be appreciated!

Answer 1

State nomenclature

stateChanged vaguely makes sense, but state doesn't. The word "state" is a fairly vague descriptor. What does state as a boolean actually mean? This should probably be renamed to isValid.

Boolean factorization

    if (!numberPresent && !operatorPresent) {
        // if parenthesis state is changed a number needs to be present
        state = !parStateChanged;
    } else if (numberPresent && operatorPresent) {
        state = false;
    } else if (numberPresent) {
        state = true;
    }

can be

if (numberPresent)
    isValid = !operatorPresent;
else
    isValid = !parStateChanged;

else after return

This:

                    if (!subState) {
                        return false;
                    } else {

doesn't need the else, due to the return stopping the function beforehand.

Surprise mutation

getState has a problem. One would assume, reading only the function signature and not the source, that it doesn't change the class - and only computes a value to return it. However, that's not the case - a member is changed. There are several different ways to deal with this depending on your intent:

• Rename the function to describe what it actually does (checkValidity?)
• Separate the check function from the isValid function
• Don't store a state as a member at all, and only have an isValid function