Solves simple string-based expressions.
Currently only supports integers, but can easily be expanded to support float-types.
Simple Equation Solver
import java.util.*;
/**
* Utility class for solving equations
*/
public class EquationSolver{
public static void main(String... args){
System.out.println(EquationSolver.solve("5 + 3 * (8 - 4)"));
System.out.println();
System.out.println(EquationSolver.solve("12 / (3 * 4) + 5"));
}
private static String doOperation(String lhs, char operator, String rhs){
switch(operator){
case '^':
return "" + (int)Math.pow( (int)Integer.parseInt(lhs), (int)Integer.parseInt(rhs) );
case '*':
return "" + (Integer.parseInt(lhs) * Integer.parseInt(rhs));
case '/':
return "" + (Integer.parseInt(lhs) / Integer.parseInt(rhs));
case '+':
return "" + (Integer.parseInt(lhs) + Integer.parseInt(rhs));
case '-':
return "" + (Integer.parseInt(lhs) - Integer.parseInt(rhs));
}
return "";
}
/**
* Contains an expression that exists within parenthesis
* i.e., (5+3), (6 + 2), etc.
*
* If a set of paranethesis exists within the expression, it must be resolved
* by using another expression object to solve the inner expression.
* i.e., (5 + 3 - 2 + (8 * 7) ) would first result in an ExpressionNode consisting of
* a call to another expression to Solve the inner expression
*/
private class ExpressionNode{
String expression = "";
/**
* Accepts a String argument as an expression
*/
ExpressionNode(String arg){
/*
* LOGIC:
* -Set this object's globally scoped String to the newly corrected one.
*/
expression = correctedString(arg);
}
/**
* Returns a corrected version of the String, which is one that
* has its first and last paranthesis removed.
*/
private String correctedString(String arg){
// A Mutable String
StringBuilder sb = new StringBuilder();
/*
* LOGIC:
* -For every character in arg
* -If a left paranthesis character is found and it is the first one found
* -set foundFirst to true and do not add that character to the StringBuilder
* -Else
* -append to the StringBuilder the current character
*
* -make arg point to a reversed version of the StringBuilder's String
* -clear the StringBuilder for reuse
* -reset foundFirst (since we're planning on trying again)
*
* -For every character in arg
* -If a right paranthesis character is found and it is the first one found
* -set foundFirst to true and do not add that character to the StringBuilder
* -Else
* -append to the StringBuilder the current character
*
* -make arg point to a reversed version of the StringBuilder's String
* -return arg
*/
boolean foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == '(')
foundFirst = true;
else sb.append(arg.charAt(i));
arg = new StringBuilder(sb.reverse()).toString();
sb.delete(0, sb.length());
foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == ')')
foundFirst = true;
else sb.append(arg.charAt(i));
return arg = new StringBuilder(sb.reverse()).toString();
}
//private String
/**
* Returns the result of the calculated ExpressionNode.
* If another expression is found within this one,
* a new ExpressionNode will be created and will solve
* the inner expression.
*/
public String toString(){
/*
* LOGIC:
* -Create a finalExpression for a String and initialize it with an empty String
* -For every character in the expression
* -If a left paranthesis is encountered (denoting an inner expression)
* -Create a placeholder for a String and initialize it with a left paranthesis character
* -initialize valuesCounted as an int with the value of 1, denoting that we have at least 1 value
* -For every character, starting at that parenthesis (not including that paranthesis), until valuesCounted is zero
* -If the character is a left paranthesis
* -increment valuesCounted and add the left paranthesis to the placeholder
* -Else If the character is a right paranthesis
* -decrement valuesCounted and add the right paranthesis to the nested placeholder
* -Create an ExpressionNode for the placeHolder String
* -add the toString of the ExpressionNode to the finalExpression String
* -increment i by the length - 1 of the placeHolder
* -Else
* -add the character to the finalExpression String
*
* -Create a resizable array named totalNumbers to store the numbers in the expression
* -Create a resizable array named totalOperations to store the operators in the expression
*
* -For every character in finalExpression
* -If the character encountered is between characters '1' and '9'
* -store the current value of i into storedNumber [???]
* -Create a temp String to collect characters for the number
* -For every number character in the number set selected
* -Concatenate that number to the temp String
* -add the temp String to the ArrayList totalNumbers
* -advance i by (the length of the temp String - 1)
* -Else if the character encountered is '*', '-', '+', '/', '^'
* -store the character in the ArrayList totalOperations
*
* -Create a temp String to hold the final result
*
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to ^
* -perform the power operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -trim the totalOperations array to a new size, so the null value is removed
* -trim the totalNumbers array to a new size, so the null value is removed
* -decrement i
*
* -clear the temp String
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to * or /
* -perform the necessary operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -trim the totalOperations array to a new size, so the null value is removed
* -trim the totalNumbers array to a new size, so the null value is removed
* -decrement i
*
* -clear the temp String
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to + or -
* -Create a temp String to hold the final result
* -perform the necessary operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -decrement i
*
* -return the first element of totalNumbers
*/
String finalExpression = "";
for(int i = 0; i < expression.length(); i++){
if(expression.charAt(i) == '('){
String placeHolder = "(";
int valuesCounted = 1;
for(int j = i + 1; valuesCounted != 0; j++){
if(expression.charAt(j) == '(')
valuesCounted++;
else if(expression.charAt(j) == ')')
valuesCounted--;
placeHolder += "" + expression.charAt(j);
}
String evaluatedString = new ExpressionNode(placeHolder).toString();
finalExpression += evaluatedString;
i+= (placeHolder.length() - 1);
}else{
finalExpression += "" + expression.charAt(i);
}
}
ArrayList<String> totalNumbers = new ArrayList<String>(0);
ArrayList<Character> totalOperations = new ArrayList<Character>(0);
System.out.println(finalExpression);
for(int i = 0; i < finalExpression.length(); i++){
if((int)finalExpression.charAt(i) >= (int)'1' && (int)finalExpression.charAt(i) <= (int)'9'){
String temp = "";
for(int j = i; j < finalExpression.length(); j++){
if(finalExpression.charAt(j) >= '1' && finalExpression.charAt(j) <= '9'){
temp += "" + finalExpression.charAt(j);
}else break;
}
totalNumbers.add(temp);
i += temp.length() == 0 ? 0 : (temp.length() - 1);
}else if(finalExpression.charAt(i) == '*'
|| finalExpression.charAt(i) == '/'
|| finalExpression.charAt(i) == '^'
|| finalExpression.charAt(i) == '+'
|| finalExpression.charAt(i) == '-'
){
totalOperations.add(new Character(finalExpression.charAt(i)));
}
}
String result = "";
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(new Character('^'))){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalOperations.set(i, null);
totalNumbers.set(i, result);
totalNumbers.set(i + 1, null);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(new Character('*'))
|| totalOperations.get(i).equals(new Character('/'))){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalOperations.set(i, null);
totalNumbers.set(i, result);
totalNumbers.set(i + 1, null);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(new Character('+'))
|| totalOperations.get(i).equals(new Character('-'))){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalOperations.set(i, null);
totalNumbers.set(i, result);
totalNumbers.set(i + 1, null);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
return totalNumbers.get(0);
}
}
private static void sleep(int millis){
try{
Thread.sleep(millis);
}catch(Exception e){}
}
/**
* Checks to see if the expression is solvable or not.
*/
private static boolean isSolvable(String eq){
int paranthesisCount = 0;
/*
* LOGIC:
* -For all characters in the String eq
* -If a character encountered is equal to a left paranthesis
* -Increment the paranthesis count
* -Else If a character encountered is equal to a right paranthesis
* -Decrement the paranthesis count
* -return true if the count is zero, otherwise return false, and the reasoning
* for this is because if the paranthesis in the String do not match, the expression
* cannot be solved.
*/
for(char element : eq.toCharArray()){
if(element == '(')
paranthesisCount++;
else if(element == ')')
paranthesisCount--;
}
return paranthesisCount == 0;
}
public static String solve(String eq){
if(isSolvable(eq)){
EquationSolver es = new EquationSolver();
return es.new ExpressionNode(eq).toString();
}else return "";
}
}
Alex Edwards
321
Posting Shark
Darn I just noticed it doesn't handle negatives well... @_@
This can be easily modified by simply changing subtraction to plus-negative values and only doing sums of values.
Alex Edwards
321
Posting Shark
A version that works with negatives--
import java.util.*;
import java.io.*;
/**
* Utility class for solving equations
*/
public class EquationSolver{
public static void main(String... args){
System.out.println(EquationSolver.solve("5 + 3 * (8 - 4)"));
System.out.println();
System.out.println(EquationSolver.solve("12 / (3 * 4) + 5"));
System.out.println();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter an equation you would like to solve: ");
try{
System.out.println( EquationSolver.solve(br.readLine()) );
}catch(Exception e){
}
}
private static String doOperation(String lhs, char operator, String rhs){
switch(operator){
case '^':
return "" + (int)Math.pow( (int)Integer.parseInt(lhs), (int)Integer.parseInt(rhs) );
case '*':
return "" + (Integer.parseInt(lhs) * Integer.parseInt(rhs));
case '/':
return "" + (Integer.parseInt(lhs) / Integer.parseInt(rhs));
case '+':
return "" + (Integer.parseInt(lhs) + Integer.parseInt(rhs));
case '-':
return "" + (Integer.parseInt(lhs) - Integer.parseInt(rhs));
}
return "";
}
/**
* Contains an expression that exists within parenthesis
* i.e., (5+3), (6 + 2), etc.
*
* If a set of paranethesis exists within the expression, it must be resolved
* by using another expression object to solve the inner expression.
* i.e., (5 + 3 - 2 + (8 * 7) ) would first result in an ExpressionNode consisting of
* a call to another expression to Solve the inner expression
*/
private class ExpressionNode{
String expression = "";
/**
* Accepts a String argument as an expression
*/
ExpressionNode(String arg){
/*
* LOGIC:
* -Set this object's globally scoped String to the newly corrected one.
*/
expression = correctedString(arg);
}
/**
* Returns a corrected version of the String, which is one that
* has its first and last paranthesis removed.
*/
private String correctedString(String arg){
// A Mutable String
StringBuilder sb = new StringBuilder();
/*
* LOGIC:
* -For every character in arg
* -If a left paranthesis character is found and it is the first one found
* -set foundFirst to true and do not add that character to the StringBuilder
* -Else
* -append to the StringBuilder the current character
*
* -make arg point to a reversed version of the StringBuilder's String
* -clear the StringBuilder for reuse
* -reset foundFirst (since we're planning on trying again)
*
* -For every character in arg
* -If a right paranthesis character is found and it is the first one found
* -set foundFirst to true and do not add that character to the StringBuilder
* -Else
* -append to the StringBuilder the current character
*
* -make arg point to a reversed version of the StringBuilder's String
* -return arg
*/
boolean foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == '(')
foundFirst = true;
else sb.append(arg.charAt(i));
arg = new StringBuilder(sb.reverse()).toString();
sb.delete(0, sb.length());
foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == ')')
foundFirst = true;
else sb.append(arg.charAt(i));
return arg = new StringBuilder(sb.reverse()).toString();
}
//private String
/**
* Returns the result of the calculated ExpressionNode.
* If another expression is found within this one,
* a new ExpressionNode will be created and will solve
* the inner expression.
*/
public String toString(){
/*
* LOGIC:
* -Create a finalExpression for a String and initialize it with an empty String
* -For every character in the expression
* -If a left paranthesis is encountered (denoting an inner expression)
* -Create a placeholder for a String and initialize it with a left paranthesis character
* -initialize valuesCounted as an int with the value of 1, denoting that we have at least 1 value
* -For every character, starting at that parenthesis (not including that paranthesis), until valuesCounted is zero
* -If the character is a left paranthesis
* -increment valuesCounted and add the left paranthesis to the placeholder
* -Else If the character is a right paranthesis
* -decrement valuesCounted and add the right paranthesis to the nested placeholder
* -Create an ExpressionNode for the placeHolder String
* -add the toString of the ExpressionNode to the finalExpression String
* -increment i by the length - 1 of the placeHolder
* -Else if the character is a '-' character
* -append a + to the finalExpression String
* -append a - to the finalExpression String
* -Else
* -add the character to the finalExpression String
*
* -Create a resizable array named totalNumbers to store the numbers in the expression
* -Create a resizable array named totalOperations to store the operators in the expression
*
* -Create a temporary String for the compressed version of the finalExpression
* -For every character in the finalExpression
* -If the character is not equal to a space character
* -append the character to the temporary String
* -make finalExpression point to the temporary String
*
* -For every character in finalExpression
* -If the character encountered is between characters '1' and '9' or is a minus sign '-'
* -store the current value of i into storedNumber [???]
* -Create a temp String to collect characters for the number
* -For every number character in the number set selected
* -Concatenate that number to the temp String
* -add the temp String to the ArrayList totalNumbers
* -advance i by (the length of the temp String - 1)
* -Else if the character encountered is '*', '+', '/', '^'
* -store the character in the ArrayList totalOperations
*
* -Create a temp String to hold the final result
*
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to ^
* -perform the power operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -trim the totalOperations array to a new size, so the null value is removed
* -trim the totalNumbers array to a new size, so the null value is removed
* -decrement i
*
* -clear the temp String
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to * or /
* -perform the necessary operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -trim the totalOperations array to a new size, so the null value is removed
* -trim the totalNumbers array to a new size, so the null value is removed
* -decrement i
*
* -clear the temp String
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to +
* -Create a temp String to hold the final result
* -perform the necessary operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -decrement i
*
* -return the first element of totalNumbers
*/
String finalExpression = "";
boolean operatorEncountered = true;
for(int i = 0; i < expression.length(); i++){
if(expression.charAt(i) == '('){
String placeHolder = "(";
int valuesCounted = 1;
for(int j = i + 1; valuesCounted != 0; j++){
if(expression.charAt(j) == '(')
valuesCounted++;
else if(expression.charAt(j) == ')')
valuesCounted--;
placeHolder += "" + expression.charAt(j);
}
String evaluatedString = new ExpressionNode(placeHolder).toString();
finalExpression += evaluatedString;
i+= (placeHolder.length() - 1);
}else{
if(expression.charAt(i) == '-' && operatorEncountered == false)
finalExpression += '+';
finalExpression += "" + expression.charAt(i);
if((expression.charAt(i) == '+' || expression.charAt(i) == '/' || expression.charAt(i) == '^'
|| expression.charAt(i) == '*'))
operatorEncountered = true;
else if(expression.charAt(i) != ' ')
operatorEncountered = false;
}
}
String myTempString = "";
for(int i = 0; i < finalExpression.length(); i++){
if(finalExpression.charAt(i) != ' '){
myTempString += "" + finalExpression.charAt(i);
}
}
finalExpression = myTempString;
ArrayList<String> totalNumbers = new ArrayList<String>(0);
ArrayList<Character> totalOperations = new ArrayList<Character>(0);
System.out.println(finalExpression);
for(int i = 0; i < finalExpression.length(); i++){
if((int)finalExpression.charAt(i) >= (int)'1' && (int)finalExpression.charAt(i) <= (int)'9'
|| finalExpression.charAt(i) == '-'){
String temp = "";
for(int j = i; j < finalExpression.length(); j++){
if(finalExpression.charAt(j) >= '1' && finalExpression.charAt(j) <= '9'
|| finalExpression.charAt(j) == '-'){
temp += "" + finalExpression.charAt(j);
}else break;
}
totalNumbers.add(temp);
i += temp.length() == 0 ? 0 : (temp.length() - 1);
}else if(finalExpression.charAt(i) == '*'
|| finalExpression.charAt(i) == '/'
|| finalExpression.charAt(i) == '^'
|| finalExpression.charAt(i) == '+'
){
totalOperations.add(new Character(finalExpression.charAt(i)));
}
}
String result = "";
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(new Character('^'))){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalOperations.set(i, null);
totalNumbers.set(i, result);
totalNumbers.set(i + 1, null);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(new Character('*'))
|| totalOperations.get(i).equals(new Character('/'))){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalOperations.set(i, null);
totalNumbers.set(i, result);
totalNumbers.set(i + 1, null);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(new Character('+'))){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalOperations.set(i, null);
totalNumbers.set(i, result);
totalNumbers.set(i + 1, null);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
return totalNumbers.get(0);
}
}
private static void sleep(int millis){
try{
Thread.sleep(millis);
}catch(Exception e){}
}
/**
* Checks to see if the expression is solvable or not.
*/
private static boolean isSolvable(String eq){
int paranthesisCount = 0;
/*
* LOGIC:
* -For all characters in the String eq
* -If a character encountered is equal to a left paranthesis
* -Increment the paranthesis count
* -Else If a character encountered is equal to a right paranthesis
* -Decrement the paranthesis count
* -return true if the count is zero, otherwise return false, and the reasoning
* for this is because if the paranthesis in the String do not match, the expression
* cannot be solved.
*/
for(char element : eq.toCharArray()){
if(element == '(')
paranthesisCount++;
else if(element == ')')
paranthesisCount--;
}
return paranthesisCount == 0;
}
public static String solve(String eq){
if(isSolvable(eq)){
EquationSolver es = new EquationSolver();
return es.new ExpressionNode(eq).toString();
}else return "";
}
}
Alex Edwards
321
Posting Shark
5+3*8+-4
25
12/3*4+5
21
Enter an equation you would like to solve: ( 9 * (2 ^ (-3 + 5) * 8 - 3) )
-3+5
2^2*8+-3
9*29
261
Press any key to continue...
Alex Edwards
321
Posting Shark
This program treats zeros properly--
import java.util.*;
import java.io.*;
/**
* Utility class for solving equations
*/
public class EquationSolver{
public static void main(String... args){
System.out.println(EquationSolver.solve("5 + 3 * (8 - 4)"));
System.out.println();
System.out.println(EquationSolver.solve("12 / (3 * 4) + 5"));
System.out.println();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
System.out.print("Enter an equation you would like to solve: ");
try{
System.out.println( EquationSolver.solve(br.readLine()) );
}catch(Exception e){
}
}
}
private static String doOperation(String lhs, char operator, String rhs){
switch(operator){
case '^':
return "" + (int)Math.pow( (int)Integer.parseInt(lhs), (int)Integer.parseInt(rhs) );
case '*':
return "" + (Integer.parseInt(lhs) * Integer.parseInt(rhs));
case '/':
return "" + (Integer.parseInt(lhs) / Integer.parseInt(rhs));
case '+':
return "" + (Integer.parseInt(lhs) + Integer.parseInt(rhs));
case '-':
return "" + (Integer.parseInt(lhs) - Integer.parseInt(rhs));
}
return "";
}
/**
* Contains an expression that exists within parenthesis
* i.e., (5+3), (6 + 2), etc.
*
* If a set of paranethesis exists within the expression, it must be resolved
* by using another expression object to solve the inner expression.
* i.e., (5 + 3 - 2 + (8 * 7) ) would first result in an ExpressionNode consisting of
* a call to another expression to Solve the inner expression
*/
private class ExpressionNode{
String expression = "";
/**
* Accepts a String argument as an expression
*/
ExpressionNode(String arg){
/*
* LOGIC:
* -Set this object's globally scoped String to the newly corrected one.
*/
expression = correctedString(arg);
}
/**
* Returns a corrected version of the String, which is one that
* has its first and last paranthesis removed.
*/
private String correctedString(String arg){
// A Mutable String
StringBuilder sb = new StringBuilder();
/*
* LOGIC:
* -For every character in arg
* -If a left paranthesis character is found and it is the first one found
* -set foundFirst to true and do not add that character to the StringBuilder
* -Else
* -append to the StringBuilder the current character
*
* -make arg point to a reversed version of the StringBuilder's String
* -clear the StringBuilder for reuse
* -reset foundFirst (since we're planning on trying again)
*
* -For every character in arg
* -If a right paranthesis character is found and it is the first one found
* -set foundFirst to true and do not add that character to the StringBuilder
* -Else
* -append to the StringBuilder the current character
*
* -make arg point to a reversed version of the StringBuilder's String
* -return arg
*/
boolean foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == '(')
foundFirst = true;
else sb.append(arg.charAt(i));
arg = new StringBuilder(sb.reverse()).toString();
sb.delete(0, sb.length());
foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == ')')
foundFirst = true;
else sb.append(arg.charAt(i));
return arg = new StringBuilder(sb.reverse()).toString();
}
//private String
/**
* Returns the result of the calculated ExpressionNode.
* If another expression is found within this one,
* a new ExpressionNode will be created and will solve
* the inner expression.
*/
public String toString(){
/*
* LOGIC:
* -Create a finalExpression for a String and initialize it with an empty String
* -For every character in the expression
* -If a left paranthesis is encountered (denoting an inner expression)
* -Create a placeholder for a String and initialize it with a left paranthesis character
* -initialize valuesCounted as an int with the value of 1, denoting that we have at least 1 value
* -For every character, starting at that parenthesis (not including that paranthesis), until valuesCounted is zero
* -If the character is a left paranthesis
* -increment valuesCounted and add the left paranthesis to the placeholder
* -Else If the character is a right paranthesis
* -decrement valuesCounted and add the right paranthesis to the nested placeholder
* -Create an ExpressionNode for the placeHolder String
* -add the toString of the ExpressionNode to the finalExpression String
* -increment i by the length - 1 of the placeHolder
* -Else if the character is a '-' character
* -append a + to the finalExpression String
* -append a - to the finalExpression String
* -Else
* -add the character to the finalExpression String
*
* -Create a resizable array named totalNumbers to store the numbers in the expression
* -Create a resizable array named totalOperations to store the operators in the expression
*
* -Create a temporary String for the compressed version of the finalExpression
* -For every character in the finalExpression
* -If the character is not equal to a space character
* -append the character to the temporary String
* -make finalExpression point to the temporary String
*
* -For every character in finalExpression
* -If the character encountered is between characters '1' and '9' or is a minus sign '-'
* -store the current value of i into storedNumber [???]
* -Create a temp String to collect characters for the number
* -For every number character in the number set selected
* -Concatenate that number to the temp String
* -add the temp String to the ArrayList totalNumbers
* -advance i by (the length of the temp String - 1)
* -Else if the character encountered is '*', '+', '/', '^'
* -store the character in the ArrayList totalOperations
*
* -Create a temp String to hold the final result
*
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to ^
* -perform the power operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -trim the totalOperations array to a new size, so the null value is removed
* -trim the totalNumbers array to a new size, so the null value is removed
* -decrement i
*
* -clear the temp String
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to * or /
* -perform the necessary operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -trim the totalOperations array to a new size, so the null value is removed
* -trim the totalNumbers array to a new size, so the null value is removed
* -decrement i
*
* -clear the temp String
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to +
* -Create a temp String to hold the final result
* -perform the necessary operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -decrement i
*
* -return the first element of totalNumbers
*/
String finalExpression = "";
boolean operatorEncountered = true;
for(int i = 0; i < expression.length(); i++){
if(expression.charAt(i) == '('){
String placeHolder = "(";
int valuesCounted = 1;
for(int j = i + 1; valuesCounted != 0; j++){
if(expression.charAt(j) == '(')
valuesCounted++;
else if(expression.charAt(j) == ')')
valuesCounted--;
placeHolder += "" + expression.charAt(j);
}
String evaluatedString = new ExpressionNode(placeHolder).toString();
finalExpression += evaluatedString;
i+= (placeHolder.length() - 1);
}else{
if(expression.charAt(i) == '-' && operatorEncountered == false)
finalExpression += '+';
finalExpression += "" + expression.charAt(i);
if((expression.charAt(i) == '+' || expression.charAt(i) == '/' || expression.charAt(i) == '^'
|| expression.charAt(i) == '*'))
operatorEncountered = true;
else if(expression.charAt(i) != ' ')
operatorEncountered = false;
}
}
String myTempString = "";
for(int i = 0; i < finalExpression.length(); i++){
if(finalExpression.charAt(i) != ' '){
myTempString += "" + finalExpression.charAt(i);
}
}
finalExpression = myTempString;
ArrayList<String> totalNumbers = new ArrayList<String>(0);
ArrayList<Character> totalOperations = new ArrayList<Character>(0);
System.out.println(finalExpression);
for(int i = 0; i < finalExpression.length(); i++){
if((int)finalExpression.charAt(i) >= (int)'0' && (int)finalExpression.charAt(i) <= (int)'9'
|| finalExpression.charAt(i) == '-'){
String temp = "";
for(int j = i; j < finalExpression.length(); j++){
if(finalExpression.charAt(j) >= '0' && finalExpression.charAt(j) <= '9'
|| finalExpression.charAt(j) == '-'){
temp += "" + finalExpression.charAt(j);
}else break;
}
totalNumbers.add(temp);
i += temp.length() == 0 ? 0 : (temp.length() - 1);
}else if(finalExpression.charAt(i) == '*'
|| finalExpression.charAt(i) == '/'
|| finalExpression.charAt(i) == '^'
|| finalExpression.charAt(i) == '+'
){
totalOperations.add(new Character(finalExpression.charAt(i)));
}
}
String result = "";
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(new Character('^'))){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalOperations.set(i, null);
totalNumbers.set(i, result);
totalNumbers.set(i + 1, null);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(new Character('*'))
|| totalOperations.get(i).equals(new Character('/'))){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalOperations.set(i, null);
totalNumbers.set(i, result);
totalNumbers.set(i + 1, null);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(new Character('+'))){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalOperations.set(i, null);
totalNumbers.set(i, result);
totalNumbers.set(i + 1, null);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
return totalNumbers.get(0);
}
}
private static void sleep(int millis){
try{
Thread.sleep(millis);
}catch(Exception e){}
}
/**
* Checks to see if the expression is solvable or not.
*/
private static boolean isSolvable(String eq){
int paranthesisCount = 0;
/*
* LOGIC:
* -For all characters in the String eq
* -If a character encountered is equal to a left paranthesis
* -Increment the paranthesis count
* -Else If a character encountered is equal to a right paranthesis
* -Decrement the paranthesis count
* -return true if the count is zero, otherwise return false, and the reasoning
* for this is because if the paranthesis in the String do not match, the expression
* cannot be solved.
*/
for(char element : eq.toCharArray()){
if(element == '(')
paranthesisCount++;
else if(element == ')')
paranthesisCount--;
}
return paranthesisCount == 0;
}
public static String solve(String eq){
if(isSolvable(eq)){
EquationSolver es = new EquationSolver();
return es.new ExpressionNode(eq).toString();
}else return "";
}
}
Alex Edwards
321
Posting Shark
Ok, here's a fairly good version that evaluates floating-types well and also converts minus-negatives into positive values (90% accuracy).
import java.util.*;
import java.io.*;
import java.text.*;
import java.math.*;
/****************************************
* @Author: Mark Alexander Edwards Jr.
*
* Utility class for solving equations.
****************************************/
public final class EquationSolver{ // Utility classes don't need extensions!
private EquationSolver(){} // Utility classes don't need to be instantiated!
/*Constants*/
private static final Character POW = new Character('^'); // The power character
private static final Character MUL = new Character('*'); // The multiplication character
private static final Character DIV = new Character('/'); // The division character
private static final Character MOD = new Character('%'); // The modulus character
private static final Character ADD = new Character('+'); // The addition character
private static final DecimalFormat DF = new DecimalFormat(); // Our beloved formatter for floating-point values
private static final StringBuffer SB = new StringBuffer(); // A dummy StringBuffer
private static final MathContext MC = new MathContext(40); // Precision-value for BigDecimals
/**
* A Means of testing the program.
*/
public static void main(String... args){
System.out.println(EquationSolver.solve("5 + 3 * (8 - 4)"));
System.out.println();
System.out.println(EquationSolver.solve("12 / (3 * 4) + 5"));
System.out.println();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
System.out.print("Enter an equation you would like to solve: ");
try{
String temp = br.readLine();
long t1 = System.nanoTime();
System.out.println( "Answer: " + EquationSolver.solve(temp, 4) );
long t2 = System.nanoTime();
System.out.println( "\nTime taken to calculate value: " + (t2-t1) + " nanoseconds" );
}catch(Exception e){}
}
}
/**
* Performs an operation on the two numbers specified
*/
private static String doOperation(String lhs, char operator, String rhs){
BigDecimal bdLhs = new BigDecimal(lhs);
BigDecimal bdRhs = new BigDecimal(rhs);
switch(operator){
case '^':
return "" + Math.pow( bdLhs.doubleValue(), bdRhs.doubleValue() );
case '*':
return "" + bdLhs.multiply(bdRhs).toString();
case '/':
return "" + bdLhs.divide(bdRhs, MC).toString();
case '+':
return "" + bdLhs.add(bdRhs).toString();
case '%':
return "" + bdLhs.remainder(bdRhs).toString();
}
return "";
}
/**
* Returns a corrected version of the String, which is one that
* has its first and last paranthesis removed.
*/
private static String correctedString(String arg){
/*
* LOGIC:
* -For every character in arg
* -If a left paranthesis character is found and it is the first one found
* -set foundFirst to true and do not add that character to the StringBuilder
* -Else
* -append to the StringBuilder the current character
*
* -make arg point to a reversed version of the StringBuilder's String
* -clear the StringBuilder for reuse
* -reset foundFirst (since we're planning on trying again)
*
* -For every character in arg
* -If a right paranthesis character is found and it is the first one found
* -set foundFirst to true and do not add that character to the StringBuilder
* -Else
* -append to the StringBuilder the current character
*
* -make arg point to a reversed version of the StringBuilder's String
* -return arg
*/
StringBuilder sb = new StringBuilder(); // A Mutable String
boolean foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == '(')
foundFirst = true;
else sb.append(arg.charAt(i));
arg = new StringBuilder(sb.reverse()).toString();
sb.delete(0, sb.length());
foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == ')')
foundFirst = true;
else sb.append(arg.charAt(i));
return arg = new StringBuilder(sb.reverse()).toString();
}
/**
* Provides a means of halting a process for a specified amount of time
* without directly using the static Thread method sleep.
*
* Used for debugging purposes
*/
private static void sleep(int mill){
long t1 = System.currentTimeMillis(); // get the current time
long t2 = t1 + mill; // assign t2 the value of t1 + mill seconds in the future
while((t1 = System.currentTimeMillis()) < t2); // continue looping until t1 catches up with t2
}
/**
* Returns the a String that all of the characters the parameter argu
* has, minus the space characters in the String
*/
private static String removeSpaces(String argu){
String temp = "";
for(int i = 0; i < argu.length(); i++)
if(argu.charAt(i) != ' ')
temp += "" + argu.charAt(i); // only add non-space characters to temp
return temp; // return the desired String
}
/**
* Contains an expression that exists within parenthesis
* i.e., (5+3), (6 + 2), etc.
*
* If a set of paranethesis exists within the expression, it must be resolved
* by using another expression object to solve the inner expression.
* i.e., (5 + 3 - 2 + (8 * 7) ) would first result in an ExpressionNode consisting of
* a call to another expression to Solve the inner expression
*
* Returns the result of the calculated ExpressionNode.
* If another expression is found within this one,
* a new ExpressionNode will be created and will solve
* the inner expression.
*/
private static String parse(String arg){
/*
* LOGIC:
* -Create a finalExpression for a String and initialize it with an empty String
* -For every character in the expression
* -If a left paranthesis is encountered (denoting an inner expression)
* -Create a placeholder for a String and initialize it with a left paranthesis character
* -initialize valuesCounted as an int with the value of 1, denoting that we have at least 1 value
* -For every character, starting at that parenthesis (not including that paranthesis), until valuesCounted is zero
* -If the character is a left paranthesis
* -increment valuesCounted and add the left paranthesis to the placeholder
* -Else If the character is a right paranthesis
* -decrement valuesCounted and add the right paranthesis to the nested placeholder
* -Create an ExpressionNode for the placeHolder String
* -add the toString of the ExpressionNode to the finalExpression String
* -increment i by the length - 1 of the placeHolder
* -Else if the character is a '-' character
* -append a + to the finalExpression String
* -append a - to the finalExpression String
* -Else
* -add the character to the finalExpression String
*
* -Create a resizable array named totalNumbers to store the numbers in the expression
* -Create a resizable array named totalOperations to store the operators in the expression
*
* -Create a temporary String for the compressed version of the finalExpression
* -For every character in the finalExpression
* -If the character is not equal to a space character
* -append the character to the temporary String
* -make finalExpression point to the temporary String
*
* -For every character in finalExpression
* -If the character encountered is between characters '1' and '9' or is a minus sign '-'
* -store the current value of i into storedNumber [???]
* -Create a temp String to collect characters for the number
* -For every number character in the number set selected
* -Concatenate that number to the temp String
* -add the temp String to the ArrayList totalNumbers
* -advance i by (the length of the temp String - 1)
* -Else if the character encountered is '*', '+', '/', '^'
* -store the character in the ArrayList totalOperations
*
* -Create a temp String to hold the final result
*
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to ^
* -perform the power operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -trim the totalOperations array to a new size, so the null value is removed
* -trim the totalNumbers array to a new size, so the null value is removed
* -decrement i
*
* -clear the temp String
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to *, /, or %
* -perform the necessary operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -trim the totalOperations array to a new size, so the null value is removed
* -trim the totalNumbers array to a new size, so the null value is removed
* -decrement i
*
* -clear the temp String
* -For every Character object in totalOperations, using an int named i as a means to track values
* -If the Character object in totalOperations, located at i, is equal to +
* -Create a temp String to hold the final result
* -perform the necessary operation of the Integer form of the String at location i
* of the totalNumbers array with the Integer form of the String at location i + 1
* of the totalNumbers array and store the result in the temp String.
* -set the value of the Character object in totalOperations at i to null
* -set the value of the String object in totalNumbers at i + 1 to null
* -set the value of the String object in totalNumbers at i to be that of the temp String
* -decrement i
*
* -return the first element of totalNumbers
*/
String expression = removeSpaces(correctedString(arg)); // Removes paranthesis and spaces from the String expression
String finalExpression = ""; // Placeholder for the final String before values and operands are parsed
boolean operatorEncountered = true; // Used to determine if the previous value encountered is an operand
for(int i = 0; i < expression.length(); i++){ // for all of the characters in the String expression
if(expression.charAt(i) == '('){ // if we encounter a left paranthesis, the value must be a nested expression
String placeHolder = "("; // to prevent problems determining during boolean expression-checks
int valuesCounted = 1; // i.e., when should we stop? When valuesCounted is 0?
operatorEncountered = false; // because this will evaluate to be a number, we don't want to consider
// this char-expression to be an operand
for(int j = i + 1; valuesCounted != 0; j++){ // We know that i has to be "(" and we've accounted for it, so i+1 is what we'll use
if(expression.charAt(j) == '(') // if we encounted a left paranthesis, increment count
valuesCounted++;
else if(expression.charAt(j) == ')') // else if its a left paranthesis, decrement count
valuesCounted--;
placeHolder += "" + expression.charAt(j); // append the character to the expression
}
String evaluatedString = parse(placeHolder); // recursive call - evaluate the nested expression
finalExpression += evaluatedString; // append the evaluatedString to the finalExpression String
i+= (placeHolder.length() - 1); // the nested expression is already solved - force i to jump to non-redundant characters
}else{
if(expression.charAt(i) == '-' && operatorEncountered == false) // if we encountered a minus sign and we didn't encounter any operands
// before it, changes the subtraction to plus a negative
finalExpression += '+';
finalExpression += "" + expression.charAt(i); // append the character to the expression
if((expression.charAt(i) == '+'
|| expression.charAt(i) == '/'
|| expression.charAt(i) == '^'
|| expression.charAt(i) == '*'
|| expression.charAt(i) == '%'
|| expression.charAt(i) == '-')) // if we encounter a valid operand (including minus), flag operandEncountereed to be true
operatorEncountered = true;
else if(expression.charAt(i) != ' ') // else if we dont encounter whitespace nor an operand, flag operand to be false
operatorEncountered = false;
}
}
finalExpression = removeSpaces(finalExpression); // for safety measures, removing whitespace again
String perfectExpression = ""; // I'm planning on storing a better version of the finalExpression here
for(int i = 0; i < finalExpression.length(); i++){ // for every character in the String finalExpression
if((i + 1) < finalExpression.length()) // to prevent overshooting the array, this measure is taken
if(finalExpression.charAt(i) == '-' && finalExpression.charAt(i + 1) == '-') // if there are two - chars next to each other
i+=2; // ignore them.
perfectExpression += "" + finalExpression.charAt(i); // append to the perfectExpression
}
finalExpression = perfectExpression; // make finalExpression point to the same address as perfectExpression
ArrayList<String> totalNumbers = new ArrayList<String>(0); // I'm planning to use this to store Number values (as Strings)
ArrayList<Character> totalOperations = new ArrayList<Character>(0); // I'm planning to use this to store Operand values (as Characters)
System.out.println(finalExpression); // Technically a debug, but it adds a nice touch to the program.
//sleep(1000); // for debugging - this can be removed or commented out
for(int i = 0; i < finalExpression.length(); i++){ // for every character in the finalExpression
if(finalExpression.charAt(i) >= '0' && finalExpression.charAt(i) <= '9'
|| finalExpression.charAt(i) == '-' || finalExpression.charAt(i) == '.'){ // if our character is part of a number
String temp = ""; //
for(int j = i; j < finalExpression.length(); j++){ // We're technically breaking good programming practice here--
// I don't intend on traversing the entire String. We're breaking
// out of this loop the moment a non-numeric character is encountered
if(finalExpression.charAt(j) >= '0' && finalExpression.charAt(j) <= '9'
|| finalExpression.charAt(j) == '-' || finalExpression.charAt(j) == '.'){
temp += "" + finalExpression.charAt(j); // append to the temporary String
}else break;
}
totalNumbers.add(temp); // add our collected number to the ArrayList
i += temp.length() == 0 ? 0 : (temp.length() - 1); // we don't want to have redundancy, i.e.
// if number 242 is analyzed, 242, 42 and 2 shouldn't be stored, just 242
// so advance i past numbers already analyzed
}else if(finalExpression.charAt(i) == '*'
|| finalExpression.charAt(i) == '/'
|| finalExpression.charAt(i) == '^'
|| finalExpression.charAt(i) == '+'
|| finalExpression.charAt(i) == '%'
){ // If we run into an operand-character, store it in the operand list
totalOperations.add(new Character(finalExpression.charAt(i)));
}
}
String result = "";
/*
* DESCRIP:
* Nothing to special happening below, just PEMD%AS
*
* This means that Paranthesis are evaluated first (which is technically done per recursive call),
* then Exponents are evaluated on the 2nd-highest level, then Exponents, Division and Modulus are
* analyzed on the 3rd-highest level, and finally addition is performed on the lowest level.
* Subtraction is unnecessary since adding a negative if essentially the same.
*
* The algorithm used to solve the problems is similar to a INORDER version of the Forth Programming
* Language algorithm. Instead of making a stack-based solution, I simply decided to make a iterative
* ( or cursor ) based solution.
*
* Example:
* totalNumbers = [2, 3, 4, 2, 1]
* totalOperations = [+, *, ^, ^];
*
* -Paranthesis analayzed (this happens recursively)
* -Exponent analyzed
* - 4 ^ 2 = 16
* - 16 is stored in place of 4
* - 2 is removed from totalNumbers
* - ^ is removed from totalOperations
* - 1 takes the place of 2's last location
* - ^ takes the place of ^'s last location
* - 16 ^ 1 = 16
* - 16 is stored in place of 16
* - 1 is removed from totalNumbers
* - ^ is removed from totalOperations
*
* totalNumbers = [2, 3, 16]
* totalOperations = [+. *]
*
* -Multiplication, Division, and Modulus analyzed
* - 3 * 16 = 48
* - 48 is stored in place of 3
* - 16 is removed from totalNumbers
* - * is removed from totalOperations
*
* totalNumbers = [2, 48]
* totalOperations = [+]
*
* -Addition (and conceptualyy Subtraction) analyzed
* - 2 + 48 = 50
* - 50 is stored in place of 2
* - 48 is removed from totalNumbers
* - + is removed from totalOperations
*
* -return the value at indice 0 of totalNumbers, which should be 50
*/
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(POW)){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalNumbers.set(i, result);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(MUL)
|| totalOperations.get(i).equals(DIV)
|| totalOperations.get(i).equals(MOD)){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalNumbers.set(i, result);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
for(int i = 0; i < totalOperations.size(); i++){
if(totalOperations.get(i).equals(ADD)){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalNumbers.set(i, result);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
return totalNumbers.get(0); // return the value remaining in the first position of the ArrayList
}
/**
* Checks to see if the expression is solvable or not.
*
* This method is actually a misnomer, because more restrictions
* should be put in place on what a user can determine as solvable.
*/
private static boolean isSolvable(String eq){
/*
* LOGIC:
* -For all characters in the String eq
* -If a character encountered is equal to a left paranthesis
* -Increment the paranthesis count
* -Else If a character encountered is equal to a right paranthesis
* -Decrement the paranthesis count
* -return true if the count is zero, otherwise return false, and the reasoning
* for this is because if the paranthesis in the String do not match, the expression
* cannot be solved.
*/
int paranthesisCount = 0; // assuming 0 paranthesis to begin with
for(char element : eq.toCharArray()){ // for every char in the String eq
if(element == '(') // if the element is a left paranthesis
paranthesisCount++; // increment the paranthesisCount
else if(element == ')') // else if the element is a right paranthesis
paranthesisCount--; // decrement the paranthesisCount
if(paranthesisCount < 0) // if brackets aren't in correct order, return false
return false;
}
return paranthesisCount == 0; // return true if paranthesisCount is zero, otherwise return false
}
/**
* Attempts to solve an equation
*/
public static String solve(String eq){
if(isSolvable(eq)){
System.out.println(eq); // Prints out the equation before it is parsed
String value = "(" + eq + ")"; // Appending paranthesis to the equation for accuracy
return parse(value); // returning the final value of the expression
}else return "";
}
/**
* Attempts to solve an equation, with the precision factor taken into account.
*
* The maximum precision is 40, only because the max precision for a MathContext object is 40
* though this is not required and can be changed in future versions.
*/
public static String solve(String eq, int precision){
SB.delete(0, SB.length());
return DF.format( (double)Double.parseDouble(solve(eq)), SB, new FieldPosition(precision) ).toString(); // formatted answer
}
}
Alex Edwards
321
Posting Shark
Implemented Right-to-left evaluations for powers. Negatives were improved (slightly) by making negatives parse as multiplying -1 by the value.
import java.util.*;
import java.io.*;
import java.text.*;
import java.math.*;
/****************************************
* @Author: Mark Alexander Edwards Jr.
*
* Utility class for solving equations.
****************************************/
public final class EquationSolver{ // Utility classes don't need extensions!
private EquationSolver(){} // Utility classes don't need to be instantiated!
/*Constants*/
private static final Character POW = new Character('^');
private static final Character MUL = new Character('*');
private static final Character DIV = new Character('/');
private static final Character MOD = new Character('%');
private static final Character ADD = new Character('+');
private static final Character[] firstSet = {POW}, secondSet = {MUL, DIV, MOD}, thirdSet = {ADD};
private static final DecimalFormat DF = new DecimalFormat();
private static final StringBuffer SB = new StringBuffer();
private static final MathContext MC = new MathContext(40);
private enum Direction {
L_TO_R,
R_TO_L
};
/**
* A Means of testing the program.
*/
public static void main(String... args){
System.out.println();
System.out.println(EquationSolver.solve("5 + 3 * (8 - 4)"));
System.out.println();
System.out.println(EquationSolver.solve("12 / (3 * 4) + 5"));
System.out.println();
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
while(true){
System.out.print("Enter an equation you would like to solve \n(or enter EXIT to exit program): ");
try{
String temp = br.readLine();
if(temp.equalsIgnoreCase("exit")){
try{
isr.close();
br.close();
}catch(Exception f){
}finally{
System.exit(0);
}
}
long t1 = System.nanoTime();
System.out.println( "Answer: " + EquationSolver.solve(temp, 4) );
long t2 = System.nanoTime();
System.out.println( "\nTime taken to calculate value: " + (t2-t1) + " nanoseconds" );
}catch(Exception e){}
}
}
/**
* Performs an operation on the two numbers specified
*/
private static String doOperation(String lhs, char operator, String rhs){
BigDecimal bdLhs = new BigDecimal(lhs);
BigDecimal bdRhs = new BigDecimal(rhs);
switch(operator){
case '^':
return "" + Math.pow( bdLhs.doubleValue(), bdRhs.doubleValue() );
case '*':
return "" + bdLhs.multiply(bdRhs).toString();
case '/':
return "" + bdLhs.divide(bdRhs, MC).toString();
case '+':
return "" + bdLhs.add(bdRhs).toString();
case '%':
return "" + bdLhs.remainder(bdRhs).toString();
}
return "";
}
/**
* Returns a corrected version of the String, which is one that
* has its first and last paranthesis removed.
*/
private static String correctedString(String arg){
StringBuilder sb = new StringBuilder(); // A Mutable String
boolean foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == '(')
foundFirst = true;
else sb.append(arg.charAt(i));
arg = new StringBuilder(sb.reverse()).toString();
sb.delete(0, sb.length());
foundFirst = false;
for(int i = 0; i < arg.length(); i++)
if(foundFirst == false && arg.charAt(i) == ')')
foundFirst = true;
else sb.append(arg.charAt(i));
return arg = new StringBuilder(sb.reverse()).toString();
}
/**
* Provides a means of halting a process for a specified amount of time
* without directly using the static Thread method sleep.
*
* Used for debugging purposes
*/
private static void sleep(int mill){
long t1 = System.currentTimeMillis();
long t2 = t1 + mill;
while((t1 = System.currentTimeMillis()) < t2);
}
/**
* Returns the a String that all of the characters the parameter argu
* has, minus the space characters in the String
*/
private static String removeSpaces(String argu){
String temp = "";
for(int i = 0; i < argu.length(); i++)
if(argu.charAt(i) != ' ')
temp += "" + argu.charAt(i);
return temp;
}
/**
* Contains an expression that exists within parenthesis
* i.e., (5+3), (6 + 2), etc.
*
* If a set of paranethesis exists within the expression, it must be resolved
* by using another expression object to solve the inner expression.
* i.e., (5 + 3 - 2 + (8 * 7) ) would first result in an ExpressionNode consisting of
* a call to another expression to Solve the inner expression
*
* Returns the result of the calculated ExpressionNode.
* If another expression is found within this one,
* a new ExpressionNode will be created and will solve
* the inner expression.
*/
private static String parse(String arg){
String expression = removeSpaces(correctedString(arg));
String finalExpression = "";
boolean operatorEncountered = true;
boolean initialValue = true;
for(int i = 0; i < expression.length(); i++){
if(expression.charAt(i) == '('){
String multiply = "";
if(operatorEncountered == false && initialValue == false){
multiply += "*";
}
String placeHolder = "(";
int valuesCounted = 1;
operatorEncountered = false;
for(int j = i + 1; valuesCounted != 0; j++){
if(expression.charAt(j) == '(')
valuesCounted++;
else if(expression.charAt(j) == ')')
valuesCounted--;
placeHolder += "" + expression.charAt(j);
}
String evaluatedString = parse(placeHolder);
finalExpression += multiply + evaluatedString;
i+= (placeHolder.length() - 1);
}else{
if(expression.charAt(i) == '-' && operatorEncountered == false){
finalExpression += ((!initialValue) ? "+": "") + expression.charAt(i);
}else if(expression.charAt(i) == '-' && operatorEncountered == true){
finalExpression += "-1*";
}else finalExpression += expression.charAt(i);
if((expression.charAt(i) == '+'
|| expression.charAt(i) == '/'
|| expression.charAt(i) == '^'
|| expression.charAt(i) == '*'
|| expression.charAt(i) == '%'
|| expression.charAt(i) == '-'))
operatorEncountered = true;
else if(expression.charAt(i) != ' ')
operatorEncountered = false;
}
initialValue = false;
}
finalExpression = removeSpaces(finalExpression);
String perfectExpression = "";
for(int i = 0; i < finalExpression.length(); i++){
if((i + 1) < finalExpression.length())
if(finalExpression.charAt(i) == '-' && finalExpression.charAt(i + 1) == '-')
i+=2;
perfectExpression += "" + finalExpression.charAt(i);
}
finalExpression = perfectExpression;
ArrayList<String> totalNumbers = new ArrayList<String>(0);
ArrayList<Character> totalOperations = new ArrayList<Character>(0);
System.out.println(finalExpression);
for(int i = 0; i < finalExpression.length(); i++){
if(finalExpression.charAt(i) >= '0' && finalExpression.charAt(i) <= '9'
|| finalExpression.charAt(i) == '-' || finalExpression.charAt(i) == '.'
|| finalExpression.charAt(i) == ','){
String temp = "";
for(int j = i; j < finalExpression.length(); j++){
if(finalExpression.charAt(j) >= '0' && finalExpression.charAt(j) <= '9'
|| finalExpression.charAt(j) == '-' || finalExpression.charAt(j) == '.'
|| finalExpression.charAt(j) == ','){
temp += "" + finalExpression.charAt(j);
}else break;
}
totalNumbers.add(temp);
i += temp.length() == 0 ? 0 : (temp.length() - 1);
}else if(finalExpression.charAt(i) == '*'
|| finalExpression.charAt(i) == '/'
|| finalExpression.charAt(i) == '^'
|| finalExpression.charAt(i) == '+'
|| finalExpression.charAt(i) == '%'
){
totalOperations.add(new Character(finalExpression.charAt(i)));
}
}
calculate(totalNumbers, totalOperations, firstSet, Direction.R_TO_L);
calculate(totalNumbers, totalOperations, secondSet, Direction.L_TO_R);
calculate(totalNumbers, totalOperations, thirdSet, Direction.L_TO_R);
return totalNumbers.get(0);
}
/**
* Returns true if the target character exists in the set of Character operands, returns false otherwise.
*/
private static boolean containsCharacter(Character anOperation, Character operands[]){
for(Character item : operands){
if(anOperation.equals(item)){
return true;
}
}
return false;
}
/**
* Attempts to solve an equation that is seperated into a set of numbers and operands.
* (More to add)
*/
private static void calculate(ArrayList<String> totalNumbers, ArrayList<Character> totalOperations, Character operands[], Direction dir){
String result = "";
if(dir == Direction.L_TO_R){
for(int i = 0; i < totalOperations.size(); i++){
if(containsCharacter(totalOperations.get(i), operands)){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalNumbers.set(i, result);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
i--;
}
}
}else if(dir == Direction.R_TO_L){
for(int i = totalOperations.size() - 1; i >= 0; i--){
if(containsCharacter(totalOperations.get(i), operands)){
result = doOperation(totalNumbers.get(i), (char)totalOperations.get(i), totalNumbers.get(i + 1));
totalNumbers.set(i, result);
totalOperations.remove(i);
totalNumbers.remove(i + 1);
}
}
}
}
/**
* Checks to see if the expression is solvable or not.
*
* This method is actually a misnomer, because more restrictions
* should be put in place on what a user can determine as solvable.
*/
private static boolean isSolvable(String eq){
int paranthesisCount = 0; // assuming 0 paranthesis to begin with
for(char element : eq.toCharArray()){ // for every char in the String eq
if(element == '(') // if the element is a left paranthesis
paranthesisCount++; // increment the paranthesisCount
else if(element == ')') // else if the element is a right paranthesis
paranthesisCount--; // decrement the paranthesisCount
if(paranthesisCount < 0) // if brackets aren't in correct order, return false
return false;
}
return paranthesisCount == 0; // return true if paranthesisCount is zero, otherwise return false
}
/**
* Attempts to solve an equation
*/
public static String solve(String eq){
if(isSolvable(eq)){
System.out.println(eq); // Prints out the equation before it is parsed
String value = "(" + eq + ")"; // Appending paranthesis to the equation for accuracy
return parse(value); // returning the final value of the expression
}else return "";
}
/**
* Attempts to solve an equation, with the precision factor taken into account.
*
* The maximum precision is 40, only because the max precision for the MathContext object is 40
* though this is not required and can be changed in future versions.
*/
public static String solve(String eq, int precision){
SB.delete(0, SB.length());
return DF.format( (double)Double.parseDouble(solve(eq)), SB, new FieldPosition(precision) ).toString(); // formatted answer
}
}
my2milan
0
Newbie Poster
sir, how about just checking if the syntax is correct or not??..the syntax of the given equation will be checked based on the order of the variables(maximum of 2 variables), numbers(maximum of 2 numbers), operators(*, -, /, + and ^(power)) and separators(parenthesis only)..terms can be separated with parenthesis and consists of a variable(s)/number(s) and an operator with this format..variable(s)/number(s) followed by an operator then followed by another variable(s)/number(s)..i want to know how to do this..hear you soon..(^_^)
einjelle
0
Newbie Poster
Gee.. Thanks for posting this. (~__~)
Can I have the permission to modify this for binary operations?
einjelle
0
Newbie Poster
Is this supposed to be the output?
5 + 3 * 8 - 4
25
12 / 3 * 4 + 5
21
Ain't the answers supposed to be 17 for the first equation and 5 for the second one?
VernonDozier
2,218
Posting Expert
Featured Poster
5 + 3 * 8 - 4 = 25
This is correct.
5 + 3 * 8 - 4 = 5 + (3 * 8) - 4 = 5 + 24 - 4 = (5 + 24) - 4 = 29 - 4 = 25.
12 / 3 * 4 + 5 = 21.
This is also correct.
12 / 3 * 4 + 5 = (12 / 3) * 4 + 5 = 4 * 4 + 5 = (4 * 4) + 5 = 16 + 5 = 21.
etayhn
0
Newbie Poster
can you build one that handles roots and trigo?
a simple one that will be able to solve
(3+5*(arctan(√(3)) +√81 * 2 + sin15)+ cos80)*sin30
i would very very very very extremely appreciate it...
kvass
70
Junior Poster
@einjelle: you have your math wrong. The program is right.
Multiplication is evaluated prior to addition and subtraction, so 5 + 3 * 8 - 4 becomes 5 + 24 - 4 which is equal to 25, not 17.
For the next one, division and multiplication again come before addition, so 12 / 3 * 4 + 5 becomes 4 * 4 + 5 which becomes 16 + 5 which is equal to 21, not 5.
Elementary, my dear Watson ;)
Taywin
312
Posting Virtuoso
@kvass
einjelle has his math right on the first one but not the second. But his computation is NOT the same as computer computation because of mathematical operation preference. In math, if you do not give parenthesis to your expression, every operation has the same preference. Therefore, it is ambiguous and you can compute whatever order you want. In computer, there are rules for the preference, so einjelle is wrong in this case.
I said he is correct for the first one because he computed the expression 5 + 3 * 8 - 4 as 5 + (3 * (8 - 4)) or right to left with equal preference. However, I do not see how he could get 5 from the expression 12 / 3 * 4 + 5. The only think I am thinking is that he might have done (12 / (3 * 4)) + 5 which is still equal to 6.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.