This tutorial will show you how to write a Java program that takes a string input such as “3 + 4^2*7.5E-1*sin(22)” and convert it into a numerical answer, 2.893784 in this case, which you can use for whatever purpose you like.

This Java Applet utilizes the *Expression* class that you will be creating.

We will accomplish this by parsing the input string for tokens that we recognize, and then removing them from the input string by using the `substring()`

function. Here is the initial code for the file *Expression.java*:

`import java.util.*; public class Expression{ /* * Strings used for storing expression. */ String s, x; /* * Term evaluator for number literals. */ double term(){ // insert code here } /* * Public access method to evaluate this expression. */ public double evaluate(){ s = x.intern(); return term(); } /* * Creates new Expression. */ public Expression( String s ){ // remove white space, assume only spaces or tabs StringBuffer b = new StringBuffer(); StringTokenizer t = new StringTokenizer( s, " " ); while( t.hasMoreElements() ) b.append( t.nextToken() ); t = new StringTokenizer( b.toString(), "\t" ); b = new StringBuffer(); while( t.hasMoreElements() ) b.append( t.nextToken() ); x = b.toString(); } /* * The String value of this Expression. */ public String toString(){ return x.intern(); } /* * Test our Expression class by evaluating the command-line * argument and then returning. */ public static void main( String[] args ){ Expression e = new Expression( args[0] ); System.out.println( e + " = " + e.evaluate() ); } }`

We import the *java.util.** classes because we will be using a *StringTokenizer* in some places. The `Expression()`

constructor takes a string as an argument, removes any white space, and stores the result in the variable *x*. The `toString()`

function very simply returns a copy of *x*. The `evaluate()`

function makes a copy of the string, because it gets modified in our processing code, and calls `term()`

to search for a numerical valule. Finally, the `main()`

function takes an input string from the user, creates an *Expression* with it, evaluates it, and returns the result.

Let’s start by filling in the `term()`

function.

`double term(){ double ans = 0; boolean neg = false; if( s.charAt( 0 ) == '-' ){ neg = true; s = s.substring( 1 ); } StringBuffer temp = new StringBuffer(); while( s.length() > 0 && Character.isDigit( s.charAt( 0 ) ) ){ temp.append(Integer.parseInt( "" + s.charAt( 0 ) )); s = s.substring( 1 ); } if( s.length() > 0 && s.charAt( 0 ) == '.' ){ temp.append( '.' ); s = s.substring( 1 ); while( s.length() > 0 && Character.isDigit( s.charAt( 0 ) ) ){ temp.append(Integer.parseInt( "" + s.charAt( 0 ) )); s = s.substring( 1 ); } } if( s.length() > 0 && (s.charAt(0) == 'e' || s.charAt(0) == 'E') ){ temp.append( 'e' ); s = s.substring( 1 ); temp.append( s.charAt( 0 ) ); s = s.substring( 1 ); while( s.length() > 0 && Character.isDigit( s.charAt( 0 ) ) ){ temp.append(Integer.parseInt( "" + s.charAt( 0 ) )); s = s.substring( 1 ); } } ans = Double.valueOf( temp.toString() ).doubleValue(); if( neg ) ans *= -1; return ans; }`

This function is capable of reading integers or floating point numbers, including a leading minus sign, decimal point, and exponential notation. It starts by declaring a double in which we will store our result. The first block of code checks to see if the first character is a minus sign. If so, it eats that character with the `s = s.substring( 1 )`

call, and sets the variable *neg* to true. It is because of this method of using `substring()`

that we needed the extra string variable *s* in the class.

Next `term()`

creates a *StringBuffer* and begins to read one character at a time from the string *s* and append it if it is a digit, also removing it from *s* if it is a digit. Once we have read all the digits, we check to see if the next character is a period. If so, we remove it and append it, and then continue reading digits. When we run out of digits again, or the first time if there was no decimal point, we check to see if the next character is an ‘e’ or ‘E’ for exponential notation. If so, we remove and append it. We also remove and append the next character. We do this under the assumption that the input is valid, and will therefore consist of an integer following the exponential sign. This method takes care of it whether it is a digit or a minus sign. Then we read any more digits that are contained in the exponential part.

Once we have done this, our *StringBuffer, temp* has the full string value of the number, so we convert it to a *double*, multiply it by -1 if we found a minus sign as the very first character above, and return it.

If you now compile and run *Expression*, it will correctly interpret strings such as “3”, “3.4”, “-267”, “.314159E1”, or “-.01E-12”.

OK, now let’s include the capability to solve addition problems. Change the line `last = term();`

in the `evaulate()`

function to `last = add();`

and then insert the following function into your file:

`/* * Addition, subtraction expression solver. */ double add(){ double ans = term(); while( s.length() > 0 ){ if( s.charAt( 0 ) == '+' ){ s = s.substring( 1 ); ans += term(); } else if( s.charAt( 0 ) == '-' ){ s = s.substring( 1 ); ans -= term(); } else{ break; } } return ans; }`

The `add()`

function first reads a number by calling the `term()`

function. If that number is all the input, that is fine, `add()`

will return that function. But if that is not all the input, it checks for a + or a – sign, removes that character from the string, reads the next number, performs the appropriate action, and continues in this way until it has read the entire string (or encountered an error). It then returns the answer.

Now when you compile *Expression.java*, it can handle not only single numbers, but also addition and subtraction, such as “1+2”, or “-1.3e-1 + 9.7”. As you can see, the spaces in the last example don’t affect anything because we stripped them out in the constructor function. Also, the lowercase ‘e’ works just as well as the uppercase ‘E’.

Now replace the three occurrences of `term()`

in the `add()`

function with `mul()`

, which will handle our multiplication functionality. The `mul()`

function is as follows:

`/* * Multiplication, division expression solver. */ double mul(){ double ans = term(); while( s.length() > 0 ){ if( s.charAt( 0 ) == '*' ){ s = s.substring( 1 ); ans *= term(); } else if( s.charAt( 0 ) == '/' ){ s = s.substring( 1 ); ans /= term(); } else break; } return ans; }`

Like the `add()`

function, the `mul()`

function calls `term()`

and then checks for multiplication or division operators. When it has run out, it returns to the `add()`

function, which may then read in another portion of the string with additional numbers or multiplication.

You can now compile *Expression* and it will interpret and solve such strings as “1+2*3+4”, or “-1-2.e-4*-2E3+12”, giving the proper output for standard operator precedence.

We will now add trigonometric function capability. Replace the three occurrences of `term()`

in the above `mul()`

function with the call `trig()`

. The `trig()`

function is:

`/* * Trigonometric function solver. */ double trig(){ double ans = 0; boolean found = false; if( s.indexOf( "sin" ) == 0 ){ s = s.substring( 3 ); ans = Math.sin( trig() ); found = true; } else if( s.indexOf( "cos" ) == 0 ){ s = s.substring( 3 ); ans = Math.cos( trig() ); found = true; } else if( s.indexOf( "tan" ) == 0 ){ s = s.substring( 3 ); ans = Math.tan( trig() ); found = true; } if( !found ){ ans = term(); } return ans; }`

This function checks to see if the first part of the string is one of its recognized trig functions, and if so applies it and recurses, calling `trig()`

again. When it no longer reads a function name, it assumes it is just a number, and calls term.

After compiling, you can evaluate expressions such as “sin 12”, or “tan -3.4e-1”, or “sin cos 3” (the sine of the cosine of 3, hard to read since we haven’t added parentheses yet).

The next operator we will add is the exponentiation operator, ^. Replace the call to `term()`

in the above `trig()`

function with `exp()`

, and add that function to your file:

`/* * Exponentiation solver. */ double exp(){ boolean neg = false; if( s.charAt( 0 ) == '-' ){ neg = true; s = s.substring( 1 ); } double ans = term(); while( s.length() > 0 ){ if( s.charAt( 0 ) == '^' ){ s = s.substring( 1 ); boolean expNeg = false; if( s.charAt( 0 ) == '-' ){ expNeg = true; s = s.substring( 1 ); } double e = term(); if( ans < 0 ){ // if it's negative double x = 1; if( Math.ceil(e) == e ){ // only raise to an integer if( expNeg ) e *= -1; if( e == 0 ) ans = 1; else if( e > 0 ) for( int i = 0; i < e; i++ ) x *= ans; else for( int i = 0; i < -e; i++ ) x /= ans; ans = x; } else { ans = Math.log(-1); // otherwise make it NaN } } else if( expNeg ) ans = Math.exp( -e*Math.log( ans ) ); else ans = Math.exp( e*Math.log( ans ) ); } else break; } if( neg ) ans *= -1; return ans; }`

As you can see, we have moved the checking for a negative value into the `exp()`

function because exponentiation has higher precedence, so remove the indicated lines from the term() function. This function is somewhat complicated because we can only raise negative numbers to integral powers. Until you code the next function you won’t be able to raise negative numbers to anything, however, because exponentiation has precedence, so the negative will apply to the result.

Now the *Expression* class is fully capable of parsing and evaluating such strings as “sin 2^2” or even “2^3^-4”. Of course, it can also still handle those complicated decimal and exponential notation numbers with all this functionality.

We are almost done now. The final step is to allow for parentheses. Replace the two calls to `term()`

in `exp()`

with calls to `paren()`

, and put the following function into your file:

`/* * Parentheses solver. */ double paren(){ double ans; if( s.charAt( 0 ) == '(' ){ s = s.substring( 1 ); ans = add(); s = s.substring( 1 ); // we assume this is a ')' } else { ans = term(); } return ans; }`

A parentheses-enclosed block has the same precedence as a single number, which is why this function checks for a ( ), or just a number. If the parentheses are present, it recurses back to the `add()`

function because any expression is allowable inside parentheses.

The *Expression* class is now fully functional. It properly handles operator precedence and notation. You could also add additional functions to the `trig()`

function, such as the inverse trigonometric functions, or logarithm or natural log, or even your own arbitrary function. The example given at the beginning of this page, “3 + 4^2*7.5E-1*sin(22)”, which involves every function we added to *Expression*, may now be solved.

You can download the finished file here.

The applet code is available here.

payalThanks for the code ,,, i needed something similar and it ws quite helpful in understanding how to implement the logic.

ResiduenHello,

I still wirting an opensource-tool to solve and visualize functions:

http://residuen.github.com/JFunktion/

May I use your solver? I’m using the GPL 3.0 licence.

Regards

Residuen

paulPost authorHi,

Yes, feel free to include or borrow from my source! Just put a note somewhere in a readme or something that you’re using it.

Paul

bobMath.exp( e*Math.log( ans ) )

could be written as

Math.pow( ans, e )

similarly

Math.exp( -e*Math.log( ans ) )

could be written as

Math.pow( ans, -e )

paulPost authorThat’s a good point; I’m not sure why I didn’t do that in the first place. 🙂

Pingback: BASIC Interpreter, Part I | Visceral Logic Programming