Thread: Java Calculator

Hi, I've been trying to create a fairly simple calculator that can parse a string and build up a simple tree that's easily evaluated. It has to support a custom order of operations and parenthesis support.

Sorry for the messy programming...

code:

 private Expression parse (Expression handle, int state) throws SyntaxError { Expression hold = null; while (charPoint < text.length()) { if (readType() == type.RPARENTHESIS) { if (lastRead == type.LPARENTHESIS || lastRead == type.OPERATOR) { // error! empty parenthesis or BOP without second parameter throw new SyntaxError(); } else if (state == 4) { // finalize handle handle.setExpr(hold, 2); } charPoint++; parenCounter--; if (handle.getOper() == null) { return handle.getExpr(1); } return handle; } switch (state) { case 1: // parenthesis handling if (readType() == type.LPARENTHESIS) { lastRead = type.LPARENTHESIS; charPoint++; // set the first expression to what ever is inside the parenthesis parenCounter++; state = 1; handle.setExpr(parse(new Expression(), 1), 1); state = 2; break; } // look for a number if (readType() != type.NUMBER) { // not a number throw new SyntaxError(); } // read number in lastRead = type.NUMBER; handle.setExpr(new Number(Double.parseDouble(numMatcher.group())), 1); charPoint = numMatcher.end(); state = 2; break; case 2: // look for a binary operator if (readType() != type.OPERATOR) { throw new SyntaxError(); } lastRead = type.OPERATOR; handle.setOper(Operator.createBOP(operMatcher.group())); charPoint = operMatcher.end(); state = 3; case 3: // parenthesis handling if (readType() == type.LPARENTHESIS) { lastRead = type.LPARENTHESIS; parenCounter++; charPoint++; // set the second expression to what ever is inside the parenthesis handle.setExpr(parse(new Expression(), 1), 2); Expression temp = new Expression(); temp.setExpr(handle, 1); handle = temp; state = 2; break; } // look for a number if (readType() != type.NUMBER) { throw new SyntaxError(); } lastRead = type.NUMBER; // hold that number hold = new Number(Double.parseDouble(numMatcher.group())); charPoint = numMatcher.end(); state = 4; // break cause we want close parenthesis parsing break; case 4: // perform one look ahead if (readType() != type.OPERATOR) { // error, didn't find an operator throw new SyntaxError(); } lastRead = type.OPERATOR; Operator look = Operator.createBOP(operMatcher.group()); charPoint = operMatcher.end(); if (handle.getOper().hasHigherPrecedence(look)) { // previous operator has higher or equal precedence, finalize and move handle Expression temp = new Expression(); handle.setExpr(hold, 2); temp.setExpr(handle, 1); temp.setOper(look); handle = temp; break; } else { // previous operator has lower precedence Expression temp = new Expression(); temp.setExpr(hold, 1); temp.setOper(look); handle.setExpr(parse(temp, 3), 2); temp = new Expression(); temp.setExpr(handle, 1); state = 3; break; } } } if (state == 4) { handle.setExpr(hold, 2); } return handle; }

Currently, parse is building the expression tree wrong...
ex:
1+2*3+4
should be built:

 + / \ + 4 / \ 1 * / \ 2 3

However, I can't quite figure out how to get the "+4" bit of the tree into the correct position...

It's coming out:

 + + / \ / \ 1 * 4 / \ 2 3

which is a problem, cause it's no longer a tree... And because of my class refering only to the top node, java's garbage collector turns it into this:

 + / \ * 4 / \ 2 3

hmm.. well, that's what it was doing for a while. I've been fiddling with it, and now it doesn't work at all

If I happen to undo the changes I made, i'll update the code.

could someone tell me if there's a better way to accomplish this?

I think I'm going to start over again. I found another topic talking about the shunting algorithm, and that sounds much easier than what i'm trying to do. I'll post that code if I run into problems.

Ok, it works if anyone wants the code, pm me.

Ok, it's quite long, though. I've put each seperate class file in their own code block (SyntaxError class is excluded cause it just extends RuntimeException). The only function that evaluates is sin, but you can add your own by going to Function.evaluate and adding another else/if statement. Same goes with any operators. Note: Unary operators currently are only prefix, and although Operator handles ternary operators, the parser doesn't. I'm also working on adding methods to allow users to make custom parsers (change the order of operations, change allowed operators, etc.), adding support for postfix unary operators, variables, and allowing Objects to be passed to a function (say, an array of numbers, or a String).

There's also no main method. To use:

Parser test = new Parser("1+1/2"); System.out.println(test + " = " + test.evaluate());

main parser class:

import java.util.*; import java.util.regex.Matcher; import java.util.regex.Pattern;   /** * A parser for a mathematical expression. Handles numbers, operators, and functions. * * @author Andrew * */ public class Parser { // allowed number forms private static Pattern numRegex = Pattern.compile("([0-9]*[.]?[0-9]+[eE]{1}-?[0-9]+)" + "|([0-9]+[.]?[0-9]*[eE]{1}-?[0-9]+)" + "|([0-9]*[.]?[0-9]+)" + "|([0-9]+)"); // allowed operators private String operString = "([\\Q()+-*/^\\E]{1})"; private Pattern operRegex = Pattern.compile("([\\Q()+--*/^\\E]{1})"); // allowed function names private Pattern funcRegex = Pattern.compile("[a-zA-Z]+[_1-9a-zA-Z]*"); // order of operations (the higher the index, the higher the precedence. same index = same precedence private String[] orderOfOperations = { "bl+ bl-", "bl* bl/", "un-", "br^", "unFUNCTION" }; // type constants private static final int NONE = -1; private static final int NUMBER = 0; private static final int OPERATOR = 1; private static final int LPARENTHESIS = 2; private static final int RPARENTHESIS = 3; private static final int FUNCTION = 4; private static final int SEPARATOR = 5; // private variables private Stack<Object> output; private Stack<Object> operator; private Object holding; private Object previous; private Matcher numMatcher; private Matcher operMatcher; private Matcher funcMatcher; private String equation; private int counter; private boolean parsed;   /** * Creates an empty parser */ public Parser () {}   /** * Creates a new parser on an equation. * * @param equation */ public Parser (String equation) { // initialize everything this.equation = equation; numMatcher = numRegex.matcher(equation); operMatcher = operRegex.matcher(equation); funcMatcher = funcRegex.matcher(equation); // build the RPN stack parse(); parsed = true; }   /** * builds an RPN stack for this expression. */ private void parse () { // initialize counter = 0; holding = null; previous = null; output = new Stack<Object>(); operator = new Stack<Object>(); while (counter < equation.length()) { // get a token int held = getNext(); // If the token is a number, then add it to the output queue. if (held == NUMBER) { output.push(holding); } // If the token is a function token, then push it onto the stack. else if (held == FUNCTION) { operator.push(holding); }   // If the token is a function argument separator (e.g., a comma): else if (held == SEPARATOR) { while (true) { // Until the token at the top of the stack is a left parenthesis // pop operators off the stack onto the output queue. if (operator.isEmpty()) { // separator misplaces or parentheses mismatched throw new SyntaxError(); } Object temp = operator.pop(); held = getType(temp); if (held == LPARENTHESIS) { // found left parenthesis // get function handle Function func = (Function) operator.pop(); func.increaseNumArgs(); // put function handle back on stack operator.push(func); // put left parenthesis back on stack operator.push(temp); break; } output.push(temp); } } // If the token is an operator, then: else if (held == OPERATOR) { // while there is an operator at the top of the stack while (!operator.isEmpty() && getType(operator.peek()) == OPERATOR) { Operator top = (Operator) operator.peek(); // if holding is associative or left-associative and has a lower or equal precedence to the top or // holding is right-associative and has lower precedence if (checkPrecedence((Operator) holding, top)) { // pop top onto output output.push(operator.pop()); } else { break; } }   // push holding onto the stack. operator.push(holding);   } // If the token is a left parenthesis, then push it onto the stack. else if (held == LPARENTHESIS) { if (getType(previous) == FUNCTION) { // previous item was a function set args to 0 Function temp = (Function) operator.pop(); temp.setNumArgs(1); operator.push(temp); } operator.push(holding); } // If the token is a right parenthesis: else if (held == RPARENTHESIS) { try { while (getType(operator.peek()) != LPARENTHESIS) { // pop operators off the stack onto the output queue output.push(operator.pop()); } // Pop the left parenthesis from the stack operator.pop(); // If the token at the top of the stack is a function token, pop it onto the output queue. if (getType(operator.peek()) == FUNCTION) { output.push(operator.pop()); } } catch (EmptyStackException e) { // Parenthesis mismatch throw new SyntaxError(); } } }   // While there are still operator tokens in the stack: while (!operator.empty()) { holding = operator.pop(); if (getType(holding) == LPARENTHESIS) { // There are mismatched parenthesis throw new SyntaxError(); } // Pop the operator onto the output queue output.push(holding); } }   /** * Determines the order of operations relationship between op1 and op2 * * @param op1 * @param op2 * @return true if:<br> * - if op1 is left-associative and has a lower or equal precedence to op2<br> * - if op1 is right-associative and has lower precedence to op2<br> * - if op1 is not associative and has lower precedence to op2<br> * false otherwise */ private boolean checkPrecedence (Operator op1, Operator op2) { int op1Prec = -1; int op2Prec = -1; for (int i = 0; i < orderOfOperations.length; i++) { Scanner reader = new Scanner(orderOfOperations[i]); while (reader.hasNext()) { String comparing = reader.next(); if (comparing.equals(op1.getOperator(true))) { // found a match! op1Prec = i; } if (comparing.equals(op2.getOperator(true))) { // found a match! op2Prec = i; } } } if (op1Prec == -1 || op2Prec == -1) { // invalid operator throw new SyntaxError(); } if (op1.isLeftAssociative()) { if (op1Prec <= op2Prec) { return true; } else { return false; } } else if (op1.isRightAssociative()) { if (op1Prec < op2Prec) { return true; } else { return false; } } else { if (op1Prec < op2Prec) { return true; } else { return false; } } }   /** * puts the parsed item starting at counter into holding. * * @return the type of the object now being held */ private int getNext () { while (Character.isWhitespace(equation.charAt(counter))) { counter++; } // set previous previous = holding; if (equation.charAt(counter) == '(') { // left parenthesis holding = "("; counter++; return LPARENTHESIS; } else if (equation.charAt(counter) == ')') { // right parenthesis holding = ")"; counter++; return RPARENTHESIS; } else if (equation.charAt(counter) == ',') { // separator holding = ","; counter++; return SEPARATOR; } else if (funcMatcher.find(counter) && funcMatcher.start() == counter) { // function holding = new Function(funcMatcher.group()); ((Function) holding).setNumArgs(1); counter = funcMatcher.end(); return FUNCTION; } else if (numMatcher.find(counter) && numMatcher.start() == counter) { // a number holding = Double.parseDouble(numMatcher.group()); counter = numMatcher.end(); return NUMBER; } else if (operMatcher.find(counter) && operMatcher.start() == counter) { // an operator String operFlags; if (getType(previous) != NUMBER && getType(previous) != RPARENTHESIS) { // unary operator operFlags = "u"; // determine associative status for unary operator for (int i = 0; i < orderOfOperations.length; i++) { Scanner reader = new Scanner(orderOfOperations[i]); while (reader.hasNext()) { String temp = reader.next(); if (temp.charAt(0) == 'u' && temp.substring(2, temp.length()).equals(operMatcher.group())) { // found matching operator operFlags += temp.charAt(1); } } } } else { operFlags = "b"; // determine associative status for binary operator for (int i = 0; i < orderOfOperations.length; i++) { Scanner reader = new Scanner(orderOfOperations[i]); while (reader.hasNext()) { String temp = reader.next(); if (temp.charAt(0) == 'b' && temp.substring(2, temp.length()).equals(operMatcher.group())) { // found matching operator operFlags += temp.charAt(1); } } } } holding = new Operator(operFlags + operMatcher.group()); counter = operMatcher.end(); return OPERATOR; } else { // invalid token throw new SyntaxError(); } }   /** * Returns the token type of an object * * @param object * @return */ private int getType (Object object) { if (object instanceof Double) { return NUMBER; } else if (object instanceof Function) { return FUNCTION; } else if (object instanceof Operator) { return OPERATOR; } else if (object instanceof String && object.equals("(")) { return LPARENTHESIS; } else if (object instanceof String && object.equals(")")) { return RPARENTHESIS; } else { return NONE; } }   /** * Evaluates the expression. Only evaluates if parsed. * * @return */ public double evaluate () { if (!parsed) { throw new SyntaxError(); } // create a temp place for output stack Stack<Object> temp = (Stack<Object>) output.clone(); double answer = eval(); output = temp; return answer; }   /** * helper function for evaluate * * @return */ private double eval () { Object held; while (!output.isEmpty()) { held = output.pop(); if (getType(held) == OPERATOR) { if (((Operator) held).isUnary()) { double[] args = { this.eval() }; return ((Operator) held).evaluate(args); } else if (((Operator) held).isBinary()) { double temp = this.eval(); double[] args = { this.eval(), temp }; return ((Operator) held).evaluate(args); } else { throw new SyntaxError(); } } else if (getType(held) == FUNCTION) { double[] args = new double[((Function) held).getNumArgs()]; for (int i = args.length - 1; i >= 0; i--) { args[i] = this.eval(); } return ((Function) held).evaluate(args); } else if (getType(held) == NUMBER) { return ((Double) held).doubleValue(); } else { throw new SyntaxError(); } } throw new SyntaxError(); }   /** * Returns a string representation of the expression. Empty if un-parsed */ public String toString () { if (!parsed) { return ""; } // create a temporary version of stack Stack<Object> temp = (Stack<Object>) output.clone(); String answer = toStringHelper(); output = temp; return answer; }   /** * toString helper method * * @return */ private String toStringHelper () { String answer = ""; Object held; while (!output.isEmpty()) { held = output.pop(); if (getType(held) == OPERATOR) { if (((Operator) held).isUnary()) { return "(" + held.toString() + this.toStringHelper() + ")"; } else if (((Operator) held).isBinary()) { String temp = this.toStringHelper(); return "(" + this.toStringHelper() + held.toString() + temp + ")"; } else { throw new SyntaxError(); } } else if (getType(held) == FUNCTION) { return ((Function) held) + "(" + this.toStringHelper() + ")"; } else if (getType(held) == NUMBER) { return ((Double) held).toString(); } else { throw new SyntaxError(); } } return answer; }

Operator class:

/** * @author Andrew * */ public class Operator { private String operString; private boolean unary; private boolean binary; private boolean ternary; private boolean rightAssociative; private boolean leftAssociative;   // private static String[] orderOfOperations = { "br^", "bl* bl/", "bl+ bl-", "un-" };   /** * Constructs an operator * * @param operatorText * the first character must denote unary status ('u' for unary, 'b' for binary, 't' for ternary)<br> * the second character must denote associative status ('r' for right, 'l' for left, 'n' for none) * */ public Operator (String operatorText) { // check unary status if (operatorText.charAt(0) == 'u') { unary = true; binary = false; ternary = false; } else if (operatorText.charAt(0) == 'b') { unary = false; binary = true; ternary = false; } else if (operatorText.charAt(0) == 't') { unary = false; binary = false; ternary = true; } else { throw new SyntaxError(); }   // check associative status if (operatorText.charAt(1) == 'r') { rightAssociative = true; leftAssociative = false; } else if (operatorText.charAt(1) == 'l') { rightAssociative = false; leftAssociative = true; } else if (operatorText.charAt(1) == 'n') { rightAssociative = false; leftAssociative = false; } else { throw new SyntaxError(); } this.operString = operatorText; }   /** * @return the operator string (minus flags) */ public String getOperator () { return this.operString.substring(2, operString.length()); }   public String toString () { return this.getOperator(); }   /** * @param withFlags * whether flags will be returned with string or not * @return the operator string */ public String getOperator (boolean withFlags) { if (withFlags) { return this.operString; } else { return getOperator(); } }   /** * @return the unary */ public boolean isUnary () { return this.unary; }   /** * @return the binary */ public boolean isBinary () { return this.binary; }   /** * @return the ternary */ public boolean isTernary () { return this.ternary; }   /** * @return the rightAssociative */ public boolean isRightAssociative () { return this.rightAssociative; }   /** * @return the leftAssociative */ public boolean isLeftAssociative () { return this.leftAssociative; }   /** * @param evaluate */ public double evaluate (double[] args) { if (operString.equals("bl+")) { return args[0] + args[1]; } else if (operString.equals("bl-")) { return args[0] - args[1]; } else if (operString.equals("bl*")) { return args[0] * args[1]; } else if (operString.equals("bl/")) { return args[0] / args[1]; } else if (operString.equals("br^")) { return Math.pow(args[0], args[1]); } else if (operString.equals("un-")) { return -args[0]; } else { throw new SyntaxError(); } } }

Function class:

/** * @author Andrew * */ public class Function extends Operator { private String name; private int numArgs;   /** * creates a function with a name and a list of args * * @param name * @param args */ public Function (String name) { super("unFUNCTION"); this.name = name; numArgs = 0; }   /** * Returns an object with what this function evaluates to. Note: Functions must override this method * * @return */ public double evaluate (double[] args) { if (this.name.equals("sin")) { return Math.sin(args[0]); } else { throw new SyntaxError(); } }   public void increaseNumArgs () { numArgs++; }   public void setNumArgs (int numArgs) { this.numArgs = numArgs; }   public int getNumArgs () { return numArgs; }   public String toString () { return name; } }

My eclipse is giving me an error on that "new SyntaxError()" i imported "import java.lang.Object;" but still it is the same. could u tell me something plz...