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...