Writing a Mathematical Expression Evaluator in Java

Introduction

Before understanding the mathematical expression evaluator first let’s understand what Mathematical Expression is.

Mathematical Expressions use arithmetic operators such as +, -, /, *, and %. The % operator is the remainder of the modulo operator. mathematical expressions are used to assign arithmetic values to variables. An expression is a combination of literals, operators, variables, and parentheses used to calculate a value.

The following code describes the use of different mathematical expressions.
int x, y, z; // Three integer variables declared at the same time.
x = 10;
y = 12;
z = y / x; // z is assigned the value of y divided by x.
// Here z will have value 1.
z = x + y; // z is assigned the value of x+y // Here z will have value 22.
z = y % x // z is assigned the value of remainder when y

Writing an expression evaluator, as simple as it may be, has always been a long standing challenge , mostly because it seems to be so simple, but gets tricky very fast.

Writing a code with some operators and operands having the same precedence is easy but when there are various operators and they all have different precedence it is quite tough to solve this type of mathematical expression.

Writing Mathematical Expressions:

Generally , Mathematic Expressions can be written in one of three forms:
Infix Notation: Operators are written between the operands they operate on, e.g.è a + b.
Prefix Notation: Operators are written before the operands, e.g ->+ a b
Postfix Notation: Operators are written after operands,e.g-> a b +

Infix Expressions are harder for Compilers to solve because of the additional work needed to decide precedence. Infix notation can easily be written and recognized by humans and, generally, input to programs. Given that they are harder to evaluate, they are generally converted to one of the two remaining forms. A very well known algorithm for converting an infix notation to a postfix notation is Shunting Yard Algorithm by Edgar Dijkstra. This algorithm takes as input an Infix Expression and produces a queue that has this expression converted to postfix notation.that is easy for compiler to solve the mathematical expression.

The first thing we need to define when writing something like this, is a language that translates well into code, that allows us to think about the problem at a higher level of abstraction.

We will say that an expression is composed of tokens:

Java Program for evaluating mathematical expression as String:

import java.util.Stack;
public class Main
{
    public static int evaluate(String expression)
    {
        char[] tokens = expression.toCharArray();

        // Stack for numbers: 'values'
        Stack<Integer> values = new Stack<Integer>();

        // Stack for Operators: 'ops'
        Stack<Character> ops = new Stack<Character>();

        for (int i = 0; i < tokens.length; i++)
        {

            // Current token is a
            // whitespace, skip it
            if (tokens[i] == ' ')
                continue;

            // Current token is a number,
            // push it to stack for numbers
            if (tokens[i] >= '0' && tokens[i] <= '9')
            {
                StringBuffer sbuf = new StringBuffer();

                // There may be more than one
                // digits in number
                while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9'){
                    sbuf.append(tokens[i++]);
                }   
                values.push(Integer.parseInt(sbuf.toString()));

                // right now the i points to
                // the character next to the digit,
                // since the for loop also increases
                // the i, we would skip one
                // token position; we need to
                // decrease the value of i by 1 to
                // correct the offset.
                i--;
            }

            // Current token is an opening brace,
            // push it to 'ops'
            else if (tokens[i] == '(')
                ops.push(tokens[i]);

            // Closing brace encountered,
            // solve entire brace
            else if (tokens[i] == ')')
            {
                while (ops.peek() != '('){
                    values.push(applyOp(ops.pop(), values.pop(), values.pop()));
                }
                ops.pop();
            }

            // Current token is an operator.
            else if (tokens[i] == '+' ||
                    tokens[i] == '-' ||
                    tokens[i] == '*' ||
                        tokens[i] == '/')
            {
                // While top of 'ops' has same
                // or greater precedence to current
                // token, which is an operator.
                // Apply operator on top of 'ops'
                // to top two elements in values stack
                while (!ops.empty() && hasPrecedence(tokens[i],ops.peek())){
                    values.push(applyOp(ops.pop(), values.pop(), values.pop()));
                }
                // Push current token to 'ops'.
                ops.push(tokens[i]);
            }
        }

        // Entire expression has been
        // parsed at this point, apply remaining
        // ops to remaining values
        while (!ops.empty()){
            values.push(applyOp(ops.pop(), values.pop(), values.pop()));
        }
        // Top of 'values' contains
        // result, return it
        return values.pop();
    }

    // Returns true if 'op2' has higher
    // or same precedence as 'op1',
    // otherwise returns false.
    public static boolean hasPrecedence(char op1, char op2)
    {
        if (op2 == '(' || op2 == ')')
            return false;

        if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
            return false;

        else
            return true;
    }

    // A utility method to apply an
    // operator 'op' on operands 'a'
    // and 'b'. Return the result.
    public static int applyOp(char op, int b, int a)
    {
        switch (op)
        {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': if (b == 0) throw new UnsupportedOperationException("Cannot divide by zero");
                return a / b;
        }
        return 0;
    }

    // Driver method to test above methods
    public static void main(String[] args)
    {
        System.out.println(evaluate("10 + 2 * 6"));
        System.out.println(evaluate("100 * 2 + 12"));
        System.out.println(evaluate("100 * ( 2 + 12 )"));
        System.out.println(evaluate("100 * ( 2 + 12 ) / 14"));
    }
}

Output:
22
212
1400
100

You can run this program on Interviewbit java compiler.

Time Complexity: O(n)
Space Complexity: O(n)

Different Evaluator In Java:

1:Jep Java- Jep Java parses and evaluates mathematical expressions with only a few lines of code. This package allows your users to enter a formula as a string, and instantly evaluate it. Jep supports user defined variables, constants, and functions. A number of common mathematical functions and constants are included.

Jep Extensions- Add symbolic operations, a type system and structured programming support to core Jep.

Component of Jep-

Field type system- It allows users new types, like unlimited precision integers, and rational numbers, decimal values to be used with Jep.

Vectors and Matrices- Calculations with vectors, matrices, and standard matrix functions.

Fast evaluation- Allows very fast evaluation for double precision expressions and matrices with double value entries, typically 3 times faster than other evaluators.

Symbolic operations- Simplification, expansion, symbolic comparison and conversion to polynomials.checks the correct symbols.

Symbolic differentiation- Allows the derivatives of expressions to be calculated

Structured programming- It allows a block style programming, such as loops like for and while, and if - else statements.

Lambda expressions- Syntactical support for lambda function and higher order functions. Means correct meaning of the expression.

Mathml- Conversion to/from presentation MathML

Statistical Functions- A range of statistical aggregate functions and distributions

2: EvalEx: Java Expression Evaluation is a handy expression evaluator for Java, that allows you to evaluate simple mathematical and Boolean expressions.

Key Features:
1.Uses BigDecimal for calculation and result
2.Single class implementation, very compact
3.No dependencies to external libraries
4.Precision and rounding mode can be set
5.Supports variables
6.Standard boolean and mathematical operators
7.Standard basic mathematical and boolean functions
8.Custom functions and operators can be added at runtime

There is also some special properties that EvalEx evaluator support:

Default Settings- The default settings for an expression can be set on creation through an ExpressionSettings object. It can be created using a builder pattern.

supported Operators- it also supports various types of operators like mathematical operation and boolean operation.
Example- +,-,/,* %,^ etc. Boolean operators as =,==,&&,||,<=,>=,<,> etc.
Boolean operators always result in a BigDecimal value of 1 or 0 (zero). Any non-zero value is treated as a true value.
Supported Functions- it supports various mathematical functions like: SIN(expression),COS(expression),TAN(expression)etc.

Precision- The default precision is set to 7 digits (MathContext.DECIMAL32). Depending on your use-case you can set a different precision to get accurate results.

3: exp4j- There's also exp4j, an expression evaluator based on Dijkstra's Shunting Yard. It's freely available and redistributable under the Apache License 2.0, only about 25KB in size, and quite easy to use. If you want to add a feature where the user can provide in a formula,
for example: sin (x + pi)/2 + 1

Introduction

• Version 0.4.0 API Changes
• Version 0.3.11
• Examples
• Apache Maven

Usage

• Evaluating an expression
• Evaluating an expression asynchronously
• Variable declaration
• Implicit multiplication
• Numerical constants
• Scientific notation
• Custom functions
• Custom operators
• Precedence of unary minus and power operators
• Division by zero in operations and functions
• Built-in functions
• Validation of expression
• Error handling

Evaluating Simple Expressions

We can evaluate a simple math expression provided in String format:
We first created an instance of ExpressionBuilder. Then we assign it to an Expression reference, which we use to evaluate our expression.

1. First create an instance of expressionBuilder and apply the .build() method.

2. Declare a variable named as result and use the .evaluate() method to evaluate the value of the expression that is assigned to the result variable.

Evaluating Expressions Containing Math Functions- Let's now see a short example of how we can evaluate some standard math functions:

Calculating the result of 3*((sin(pi)-2)/e)can be done in the following way:

• Assign a variable that take reference of an object that has parameter as expression
• Now use.variables("pi", "e")method for passing the parameter for constant values like pi and e.
• Use (.build() method .
• Use(.setVariable("pi", Math.PI))method and pass the values as pi and for the value of the pi use math.pi .
• Use (.setVariable("e", Math.PI))method and pass the values as pi and for the value of the e use math.E .
• Declare a variable result and assign the method .evaluate() to calculate the result of the expression.
• We can also solve the above expressions containing math functions using the Javaluator library.

Conclusion:

Expression evaluation in Java is used to determine the order of the operators to calculate the accurate output. Arithmetic, Relational, Logical, and Conditional are expression evaluations in Java. As I recommended for understanding mathematical expression evaluator the 2nd edition of the book "Engineering a Compiler”.this article will surely help you to understand mathematical expression evaluator in a very simple and easy manner.