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:
Numbers:
{"10", "5.27", "-91.22"}
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:
Expression like
"1/0"
are considered valid as theExpression
object does not care what kind of number it's receiving. Similarly, negative factorials are also allowed.Unary minus is supported but unary plus is not (not yet).
The index is the first element in the
int[] offset
that is passed recursively to keep track of index.
Any help would be appreciated!
int[] offset
that is passed recursively to keep track of index.- — I don't understand what you are trying to say. What index? \$\endgroup\$while(offset[0] < tokens.size())
as we don't have mutable integers in Java, I am passing an int array recursively to keep tack of the current index. It's more of a hack that's why it's one of the issues. There were many alternatives but this is easy to implement and doesn't lead to bloated code. You can read more about it here: stackoverflow.com/a/4520163. \$\endgroup\$