Skip to content

Instantly share code, notes, and snippets.

@Robert-Wett

Robert-Wett/FudgeYou.java Secret

Last active August 29, 2015 14:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Robert-Wett/21937475655e9d569364 to your computer and use it in GitHub Desktop.
Save Robert-Wett/21937475655e9d569364 to your computer and use it in GitHub Desktop.
Download ZIP
ExpressionParserFinal (JAY)
Raw
FudgeYou.java
package expression;
public final class Util {
private Util() {}; // All static members. No constructor needed
/**
* Evaluates a {@code expression} as a mathematical expression and returns the result as a {@code double}.
* The expression string may contain the
* following operators '*', '/', '+', '-' and '^' for exponentiation. It also supports nested expressions
* using parentheses. Expression associativity for operators is left-to-right and negation is supported.
* Operator precedence is ^ followed by * or /, followed by + or -. The modulus operator '%' is not supported.
* A unary '+' operator is not supported because it is ambiguous, unary '-' is supported (e.g., -10 * -10)
*
* @param expression The string holding the expression. Example: "((1024 * 1024) * 3)"
*
* @return The value of the expression represented as a {@code double}.
*
* @throws IllegalArgumentException if {@code expression} is {@code null} or an empty string.
* @throws IllegalExpressionException if {@code expression} is not a valid mathematical expression.
* @throws ArithmeticException if {@code expression} results in a division by zero, or a number too
* large or small to be held by a {@code double}.
*/
public final static double evaluateExpression(String expression) throws IllegalArgumentException,
IllegalExpressionException,
ArithmeticException
{
ExpressionParser parser = new ExpressionParser(expression);
return parser.evaluate();
}
/*
* Recursive descent parser to parse and evaluate the expression.
*
* Built to enforce the following Backus-Naur rule set which enforces operator precedence:
*
* <expression> ::= [ "-" ] <term> [ [ "+" | "-" ] <term> ]...
* <term> ::= <factor> [ [ "*" | "/" ] <factor> ]...
* <factor> ::= [ "-" ] <number> | "(" <expression> ")"
* <number> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | .
*
*/
private static class ExpressionParser {
private static char END_OF_STRING = (char) -1;
private int cursor = 0; // Current position in the expression string
private String expression;
/*
* Construct the parser and assign the expression. All the work is done by the evaluate() method.
*/
ExpressionParser(String expression) throws IllegalArgumentException {
if (expression == null || expression.isEmpty())
throw new IllegalArgumentException("'expression' parameter is null or an empty string");
this.expression = expression;
}
protected final double evaluate() throws ArithmeticException, IllegalExpressionException {
double returnValue = getExpressionValue();
skipWhiteSpace();
if (peek() != END_OF_STRING) {
String extraChars = expression.substring(cursor);
/*
* This is a design decision because the expression could have been evaluated correctly
* but there may be extraneous closed parenthesis for instance. For example,
* for the expression "(10*2))", getExpressionValue() will return 20.0 "correctly" but there
* is an extra ')' at the end of the expression. We are enforcing strict grammar
* as a rule.
*/
throw new IllegalExpressionException(String.format("Extraneous %s '%s' at the end of expression %s",
extraChars.length() == 1 ? "character" : "characters",
extraChars,
expression));
}
return returnValue;
}
/*
* Returns the value of a single expression. Called recursively for each expression found.
*/
protected final double getExpressionValue() throws ArithmeticException, IllegalExpressionException {
boolean negated = false; // To support unary minus (e.g., -57)
double lhsValue;
double rhsValue;
char nextChar;
char operator;
skipWhiteSpace();
if (peek() == '-') {
getNextChar(); // Skip the '-'
negated = true;
}
lhsValue = getTermValue();
if (negated)
lhsValue = -lhsValue;
skipWhiteSpace();
nextChar = peek();
while (nextChar == '+' || nextChar == '-') {
operator = getNextChar();
rhsValue = getTermValue();
if (operator == '+')
lhsValue += rhsValue;
else
lhsValue -= rhsValue;
/*
* Unlike integer arithmetic, which will thrown an ArithmeticException when a divide
* by zero or overflow occurs, floats and doubles return a specific bit pattern representing
* NaN or Infinity in those cases. We must explicitly test the result.
*/
if (Double.isNaN(lhsValue)|| lhsValue == Double.NEGATIVE_INFINITY || lhsValue == Double.POSITIVE_INFINITY) {
throw new ArithmeticException(String.format("Operation %f %c %f results in a number " +
"that cannot be represented by a double",
lhsValue,
operator,
rhsValue));
}
skipWhiteSpace();
nextChar = peek();
}
return lhsValue;
}
/*
* Get the next term and calculate the value.
*/
private final double getTermValue() throws ArithmeticException, IllegalExpressionException {
double lhsValue;
double rhsValue;
double tmpValue; // Used for error reporting to represent the lhs on divide by zero and overflow
char nextChar;
char operator;
skipWhiteSpace();
lhsValue = getFactorValue();
skipWhiteSpace();
nextChar = peek();
while (nextChar == '*' || nextChar == '/' || nextChar == '^') {
operator = getNextChar();
rhsValue = getFactorValue();
tmpValue = lhsValue;
switch (operator) {
case '*':
lhsValue *= rhsValue;
break;
case '/':
lhsValue /= rhsValue;
break;
case '^':
lhsValue= Math.pow(lhsValue, rhsValue);
break;
default:
break; // Not reachable
}
/*
* Unlike integer arithmetic, which will thrown an ArithmeticException when a divide
* by zero or overflow occurs, floats and doubles return a specific bit pattern representing
* NaN or Infinity in those cases. We must explicitly test the result.
*/
if (Double.isNaN(lhsValue) || lhsValue == Double.NEGATIVE_INFINITY || lhsValue == Double.POSITIVE_INFINITY) {
throw new ArithmeticException(String.format("Operation %f %c %f results in a number " +
"that cannot be represented by a double",
tmpValue,
operator,
rhsValue));
}
skipWhiteSpace();
nextChar = peek();
}
return lhsValue;
}
/*
* Get the next factor and calculate the value.
*/
private final double getFactorValue() throws ArithmeticException, IllegalExpressionException {
double value;
char nextChar;
boolean negated = false;
skipWhiteSpace();
nextChar = peek();
if (nextChar == '-') {
getNextChar(); // Skip the '-'
negated = true;
}
nextChar = peek();
if (Character.isDigit(nextChar) || nextChar == '.') {
value = getNumber();
if (negated)
value = -value;
skipWhiteSpace();
if (peek() == '^') {
getNextChar();
skipWhiteSpace();
double exponent = peek() == '(' ? getExpressionValue() : getFactorValue();
value = Math.pow(value, exponent);
if (Double.isNaN(value) || value == Double.NEGATIVE_INFINITY || value == Double.POSITIVE_INFINITY) {
throw new ArithmeticException(String.format("Operation %f ^ %f results in a number " +
"that cannot be represented by a double",
value,
exponent));
}
}
if (Double.isNaN(value) || value == Double.NEGATIVE_INFINITY || value == Double.POSITIVE_INFINITY) {
throw new ArithmeticException(String.format("Expression %s results in a value " +
"that cannot be represented by a double",
expression));
}
return value;
}
if (nextChar == END_OF_STRING) {
throw new IllegalExpressionException(String.format("Expression '%s' is not propertly formed",
expression));
}
switch (nextChar) {
case '(':
getNextChar(); // Skip over the '('
value = getExpressionValue(); // We are at a new full expression
skipWhiteSpace();
break;
case ')':
throw new IllegalExpressionException(String.format("Extraneous right parenthesis " +
"in expression '%s'",
expression));
case '+':
case '-':
case '*':
case '/':
case '^':
throw new IllegalExpressionException(String.format("'%c' operator incorrectly specified " +
"in expression '%s'",
nextChar,
expression));
default:
throw new IllegalExpressionException(String.format("Illegal character '%c' specified " +
"in expression '%s'",
nextChar,
expression));
}
if (peek() != ')') {
throw new IllegalExpressionException(String.format("Missing right parenthesis in expression '%s'", expression));
}
getNextChar(); // Skip over the ')'
return value;
}
/*
* Returns a number from the expression string.
*/
private final double getNumber() throws IllegalExpressionException {
StringBuilder builder = new StringBuilder();
boolean hasDecimal = false;
char curChar;
for ( ; cursor < expression.length() ; cursor++) {
curChar = expression.charAt(cursor);
if ((curChar >= '0' && curChar <= '9') || curChar == '.') {
if (curChar == '.') {
if (hasDecimal)
throw new IllegalExpressionException("Multiple decimal points in numeric term not allowed.");
else
hasDecimal = true;
}
builder.append(expression.charAt(cursor));
}
else {
break; // Breaks on ANY character that's not a numeric value
}
}
String stringValue = builder.toString();
if (stringValue == null || stringValue.isEmpty()) {
// Should not be reachable, but just in case...
throw new IllegalExpressionException(String.format("Internal error occurred parsing expression '%s' at position %d",
expression, cursor));
}
if (stringValue.equals("."))
throw new IllegalExpressionException("A single '.' character is not a valid token.");
double returnValue;
try {
returnValue = Double.parseDouble(stringValue);
}
catch (Exception e) {
throw new IllegalExpressionException(String.format("Illegal numeric value %s encountered.",
stringValue));
}
return returnValue;
}
/*
* Skips over whitespace and sets the cursor to the next non-whitespace character or the last character
* in the expression even if it is whitespace.
*
* Returns true if the character if expression.charAt(cursor) is a non-whitespace character, false if
* the end of the expression string has been reached skipping whitespace chars.
*/
private final boolean skipWhiteSpace() {
for ( ; cursor < expression.length() ; cursor++) {
if (!Character.isWhitespace(expression.charAt(cursor)))
break;
}
return cursor == expression.length() ? false : true;
}
/*
* Returns the next character after the cursor.
*/
private final char getNextChar() {
char returnValue = cursor == expression.length() ? END_OF_STRING : expression.charAt(cursor);
cursor++;
return returnValue;
}
/*
* Returns the next character without incrementing the cursor. Used for look ahead.
*/
private final char peek() {
return cursor == expression.length() ? END_OF_STRING : expression.charAt(cursor);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment