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.
Thanks for the code ,,, i needed something similar and it ws quite helpful in understanding how to implement the logic.
Hello,
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
Hi,
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
Math.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 )
That’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