# Determine if simple arithmetic expression is valid

This looks very messy to me, and I'm fairly new to java, so I don't know what data structures could have helped me achieve the same result more efficiently. I just went ahead and brute-forced all possible failing scenarios:

Could this be further optimized to reduce the number of checks?

public static boolean isAnOperator(char c){
return (c == '*' || c == '/' || c == '+' || c == '-' || c == '%');
}

private static boolean isValidExpression(String expression){
//TEST 1: False if expression starts or ends with an operator
if (isAnOperator(expression.charAt(0)) || isAnOperator(expression.charAt(expression.length()-1)))
return false;

//TEST 2: False if test has mismatching number of opening and closing parantheses
int openParenthCount = 0;
int closedParenthCount = 0;
int consecutiveOpCount = 0;

for (int i = 0; i < expression.length(); i++){
if (expression.charAt(i) == '('){
openParenthCount++;
consecutiveOpCount = 0;
//SUBTEST: False if expression ends with '('
if (i == expression.length()-1) return false;
}
if (expression.charAt(i) == ')'){
closedParenthCount++;
consecutiveOpCount = 0;
//SUBTEST: False if expression starts with ')'
if (i == 1) return false;

}
if (isAnOperator(expression.charAt(i))){
consecutiveOpCount++;
//TEST 3: False if operator is preceded by opening paranthesis or followed by closing paranthesis
if (expression.charAt(i-1) == '(' || expression.charAt(i+1) == ')')
return false;
}
//TEST 4: False if 2 operators found next to each other
if (isAnOperator(expression.charAt(i)) || consecutiveOpCount > 0)
return false;
}
if (openParenthCount != closedParenthCount)
return false;

//LAST TEST 5: All preceding checks ensure that
// by this point, all exisiting parantheses open and close properly
return true;
}

• The code doesn't work. There are multiple bugs. Currently it returns false if any operator is present (Test 4), also if (i == 1) return false; should be if (i == 0) return false;. You also need to explain what exactly you mean with "valid expression", especially since you don't consider any other characters (e.g. white space) other than the operators and brackets. Commented Nov 30, 2017 at 8:52
• @RoToRa Added my own answer which fixes these issues, except the white space; In my code, I cleaned up the string before passing it to this method. I suppose it would be preferable to enforce another clean up within the method
– Will
Commented Nov 30, 2017 at 9:11
• It would probably be a good idea to post the updated code in a new question, if you want it reviewed. Don't forget to clarify what you consider a valid expression. Information like the clearing of whitespace is important to mention. Maybe close/delete this question, because broken code is off topic. Commented Nov 30, 2017 at 10:10

It is not always an easy task to solve this sort of problem. For data structures, we traditionally use a stack for open and close parenthesis but this is only needed if the type of parenthesis can differ and need nesting correctly. For only "(" and ")" I simmply use an int.

I re-wrote the isAnOperator to a switch statement - its personal choice that one.

I added a isANumber function to aid some checking.

I unit tested the function with 9 tests and worked till it past them all. (JUnitParams, read it as the string is the expression and the boolean is what I expect your function to return)

Your original code fails 3 of these tests - but it may because of not handling spaces in the expressions but you didn't provide any example data

To handle parenthesis I used a counter - but decrement it if I find a close. If I get into a negative number then something went wrong and if it isn't 0 at the end it was wrong. You can work out from the final value if there were too many close or opens. Simple boolean values keep track of wether the last character was an operation or a open parenthesis.

I welcome feedback on this answer - I'm trying to keep it as close to the original code as possible

$($("()", true),
$("3", true),$("3 + 2", true),
$("(3 + (2))", true),$(")", false),
$("+3", false),$("3+-2", false),
$("(3 + (3 + 2)", false),$("(x + 3)", false)
);


I've re-written the function to be cleaner with less variables:

public static boolean isAnOperator(char c) {
switch (c) {
case '*':
case '/':
case '+':
case '-':
case '%':
return true;
default:
return false;
}
}
public static boolean isANumber(char c){
return ((int)c) >= 48 && ((int)c) <= 57;
}

public static boolean isValidExpression2(String expression) {
// TEST 1
if (isAnOperator(expression.charAt(0)) || isAnOperator(expression.charAt(expression.length() - 1))) {
return false;
}

int openParenthCount = 0;
boolean lastWasOp = false;
boolean lastWasOpen = false;

for (char c : expression.toCharArray()) {
if(c == ' ') continue;
if (c == '(') {
openParenthCount++;
lastWasOpen = true;
continue;
} else if (c == ')') {
if (openParenthCount <= 0 || lastWasOp) {
return false;
}
openParenthCount--;
}else if (isAnOperator(c)){
if (lastWasOp || lastWasOpen) return false;
lastWasOp = true;
continue;
}else if(!isANumber(c)){
return false;
}
lastWasOp = false;
lastWasOpen = false;
}
if(openParenthCount != 0) return false;
if(lastWasOp || lastWasOpen) return false;
return true;
}

• Thank you for this answer; added my own answer as well, to consider the test cases failed here; Has passed all test I've throw at it so far
– Will
Commented Nov 30, 2017 at 9:07
• Thank you for this answer; added my own answer as well, to consider the test cases failed here; Has passed all tests I've thrown at it so far. I was split on whether to use cases or ifs for sake of visibility
– Will
Commented Nov 30, 2017 at 9:14

I finally rewrote the code the following, which passes previously failed test cases:

   /**
* Utility function to check if a given character is an arithmetic operator
* @param c
* @return true if operator, false if not
*/
public static boolean isAnOperator(char c){
return (c == '*' || c == '/' || c == '+' || c == '-' || c == '%');
}
/**
* Checks position and placement of (, ), and operators in a string
* to make sure it is a valid arithmetic expression
* @param expression
* @return true if the string is a valid arithmetic expression, false if not
*/
private static boolean isValidExpression(String expression){
//remove unnecessary whitespaces
expression = expression.replaceAll("\\s+", "");
//TEST 1: False if expression starts or ends with an operator
if (isAnOperator(expression.charAt(0)) || isAnOperator(expression.charAt(expression.length()-1)))
return false;
//System.out.println("Does not start or end with operator");

//TEST 2: False if test has mismatching number of opening and closing parantheses

int unclosedParenthesis = 0;
//System.out.println("Parentheses counter initialized to 0");

for (int i = 0; i < expression.length(); i++){
//System.out.println("For loop count: " + i);
if (expression.charAt(i) == '('){
//System.out.println("( found");
unclosedParenthesis++;

//SUBTEST: False if expression ends with '('
if (i == expression.length()-1) return false;
}
if (expression.charAt(i) == ')'){
unclosedParenthesis--;
//System.out.println(") found");
//SUBTEST: False if expression starts with ')'
if (i == 0) return false;

}
if (isAnOperator(expression.charAt(i))){

//System.out.println("Found an Operator");
//TEST 3: False if operator is preceded by an operator or opening paranthesis
//or followed by closing paranthesis
if (expression.charAt(i-1) == '(' || expression.charAt(i+1) == ')' || isAnOperator(expression.charAt(i+1))){
//System.out.println("Found wrongly preceding or following parenthesis to operator");
//System.out.println("or Found an operator following another operator");
return false;
}

}

}
return (unclosedParenthesis == 0);
}