Matrix and Complex Numbers Parser

Question

I have been working on a simple calculator project in Java since November 2014 as hobby. Now I want to add complex number support and Matrices. I also wants to add support for symbolic computation in future. For this purpose I wrote a Literal class which is meant for to hold all types like Matrix class objects and Complex class objects in one class and Variables in future. Currently I am dealing with expressions like this

sin(2+3i*[[2+3,4][9,average(3,5,9)]]*9.8*PI)

So far I have written tokenizer that tokenize this type of expressions in to tokens of type functions, expression brackets, functions brackets, matrices, constants and numbers.

To verify syntax and parse Complex Numbers and Matrices from token I have written LiteralParser class which parse and return Literal Object in case of success and if fails throws NumberFormatException. I could use regular expression but I think that will be slow.

I have also tried Apache ComplexFormat and RealMatrixFormat. Apache ComplexFormat does a weird thing that it treats "2i" as "2+0i" and Apache RealMatrixFormat does not support expressions on indices and it is only for real numbers.

Now I want that my code should be less nested by utilizing some functions and some performance enhancements. if is there any already existing library that does this job then let me know.

LiteralParser.java

package com.kmstudios.evaluator;

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.ArrayList;

public class LiteralParser
{
   private final MatrixFormat format;
   private final Method evaluator;

  public LiteralParser(MatrixFormat format, Method m)
  {
      this.format = format;
      this.evaluator = m;
  }

  public void parse(String literal) throws NumberFormatException, InvocationTargetException, IllegalAccessException
  {
      if (literal == null || literal.isEmpty()) throw new NumberFormatException("cannot parse empty literal");

      //If format is null then its mean that there should be no matrix in Literal
      if (this.format != null && literal.charAt(0) == this.format.getPrefix()) /*return*/ parseMatrix(literal);
      else /*return*/ parseNumber(literal);
  }

  private void parseMatrix(String mat) throws NumberFormatException, InvocationTargetException, IllegalAccessException
  {
      /* Input: [[1,2][3,4][5,6]]
      *  Intended output:
      *  1 2
      *  3 4
      *  5 6
      *
      *  Criteria:
      *  1: Nested matrices are not allowed
      *  2: Checks for any syntax error
      *  3: Supports expression on indices e.g [[2+3*9-6+pi*average(1,2,3),25][23,96]]
      *  4: Solves expressions by invoking evaluator method which should be static and
      *         accepts String as argument and returns answer as String
      *  5: Check for any columns balance e.g [[1][1,2]] all row must have
      *         same numbers of columns
      *  6: Throws Syntax error when matrix is empty [[]] or []*/
      int length = mat.length() - 1; //not checking for last index it should be postfix

      final char prefix = this.format.getPrefix();
      final char postfix = this.format.getPostfix();

      final String ERROR = "invalid syntax of matrix " + mat;
      if (mat.charAt(0) != prefix || mat.charAt(length) != postfix)throw new NumberFormatException(ERROR);

      int i = 1;
      final char rowPrefix = this.format.getRowPrefix();
      final char rowPostfix = this.format.getRowPostfix();
      final char columnSeparator = this.format.getColumnSeparator();

      int rows = 0;
      int columns = 0;
      int preRowColumns = 0;
      int start = -1;
      int depth = 0;

      boolean isOpen = false;
      char curr, prev = prefix;
      ArrayList<String> indices = new ArrayList<>();//Container for individual element

      for (; i < length ;i++)
      {
          curr = mat.charAt(i);
          if (curr == rowPrefix)
          {
              if (isOpen)throw new NumberFormatException(ERROR);//Row already open [[2,[3]]
              /*
              * Distance between Matrix Prefix and row prefix should be 1
              * and Distance between row prefix and row postfix should be 1*/
              else if (rows != 0 && prev != rowPostfix)throw new NumberFormatException(ERROR);
              else if (rows == 0 && prev != prefix)throw new NumberFormatException(ERROR);

              start = i + 1; //do not include row prefix itself
              isOpen = true;
          }
          else if (curr == rowPostfix)
          {
              //[[,1,,32]]
              if (!isOpen || prev == columnSeparator || prev == rowPrefix)throw new NumberFormatException(ERROR);

              columns++;
              if (columns != preRowColumns && preRowColumns != 0)throw new NumberFormatException(ERROR);

              indices.add(mat.substring(start, i));
              start = -1;

              isOpen = false;
              preRowColumns = columns;
              columns = 0;
              rows++;
          }
          else if (curr == columnSeparator)
          {
              if (depth != 0)continue;
              if (prev == columnSeparator || prev == prefix || prev == postfix || prev == rowPrefix)throw new NumberFormatException(ERROR);
              columns++;
              indices.add(mat.substring(start, i));
              start = i + 1; //do not include column separator itself
          }
          else if (curr == prefix || curr == postfix)throw new NumberFormatException(ERROR);//Nested matrix detected
          else if (curr == '(')depth++; //any separator in expression brackets do not count [[mean(1,2,3,4),2][[3,5]]
          else if (curr == ')')depth--; //TODO use expression brackets

          prev = curr;
      }
      if(isOpen || rows == 0 || preRowColumns == 0)throw new NumberFormatException(ERROR);

      for (i = 0, length = indices.size(); i < length; i++)
      {
          //Evaluator method is static and taking String as argument and returning String
          indices.set(i, (String)evaluator.invoke(null, indices.get(i)));//invoke method to solve expression at any index e.g [[2+3,3*9][4,5]]
      }
      /*
      * Currently I do not have any Matrix class to represent result*/
  }

  private void parseNumber(String number) throws NumberFormatException
  {
      /* Input: 2.3e+2+2.3e-3i, 2.3e-3i+2.3e+2, i2.3e-3+2.3e+2, 2.3e+2+i2.3e-3
      *  Intended output:
      *  (2.3e+2, 2.3e-3)
      *
      *
      *  1: Syntax Checking
      *  2: Supports any valid number*/

      //TODO simplify code and improve performance

      int length = number.length();
      int start = -1, indexOfI = -1, indexOfPoint = -1, indexOfE = -1, i = 0;
      final char imSign = 'i';
      char curr, prev = 0;
      boolean startWithSign = false, useful = false;
      String real = null, imag = null;

      final String ERROR = "syntax error in " + number;

      for (; i < length; i++)
      {
          curr = number.charAt(i);
          if (curr >= '0' && curr <= '9')
          {
              if (start == -1) start = i;
              useful = true;
          }
          else if (curr == '.')
          {
              //Contains point for two times or more or contain point after E
              if (indexOfPoint != -1 || indexOfE != -1) throw new NumberFormatException(ERROR);
              else indexOfPoint = i;

              if (start == -1)
              {
                  start = i;
                  useful = false; //if literal only contains "." or "-." or "-.i" etc
              }
              else if (prev == imSign || prev == '+' || prev == '-') useful = false;
          }
          else if (curr == 'e' || curr == 'E')
          {
              if (start == -1 || indexOfE != -1) throw new NumberFormatException(ERROR);
              else indexOfE = i;
          }
          else if (curr == imSign)
          {
              if (indexOfI != -1 || prev == 'e' || prev == 'E') throw new NumberFormatException(ERROR);
              else indexOfI = i;

              if (start == -1) start = i;
              else if (prev != '.') useful = true;
          }
          else if (curr == '+' || curr == '-')
          {
              if (prev == '+' || prev == '-') throw new NumberFormatException(ERROR);
              else if (start == -1)
              {
                  startWithSign = true;
                  start = i;
              }
              else if (!useful) throw new NumberFormatException(ERROR);
              else if ((indexOfI != -1) && !((indexOfI == i - 1) || (startWithSign && indexOfI == start + 1) || (!startWithSign && indexOfI == start)))throw new NumberFormatException(ERROR);
              else if (!(prev == 'e' || prev == 'E'))
              {
                  if (imag == null && indexOfI != -1) imag = number.substring(start, i);
                  else if (real == null && indexOfI == -1) real = number.substring(start, i);
                  else throw new NumberFormatException(ERROR);

                  start = i;
                  indexOfI = -1;
                  indexOfE = -1;
                  indexOfPoint = -1;
                  startWithSign = true;
                  useful = false;
              }
          }
          else throw new NumberFormatException(ERROR);
          prev = curr;
      }

      if (start != -1)
      {
          if (prev == '+' || prev == '-' || prev == 'e' || prev == 'E') throw new NumberFormatException(ERROR);
          else if (!useful) throw new NumberFormatException(ERROR);
          else if ((indexOfI != -1) && !((indexOfI == i - 1) || (startWithSign && indexOfI == start + 1) || (!startWithSign && indexOfI == start)))throw new NumberFormatException(ERROR);
          else if (imag == null && indexOfI != -1) imag = number.substring(start);
          else if (real == null && indexOfI == -1) real = number.substring(start);
          else throw new NumberFormatException(ERROR);
      }
      else throw new NumberFormatException(ERROR);

      if (real == null) real = "0";

      curr = imag != null ? imag.charAt(0) : 0;
      if (imag == null) imag = "0";
      else if ((imag.length() == 1) || ((imag.length() == 2) && (curr == '+' || curr == '-')))imag = imag.replace(new String(new char[]{imSign}), "1");
      else imag = imag.replace(new String(new char[]{imSign}), "");

      //return new Literal(new Complex(Double.parseDouble(real), Double.parseDouble(imag)));
  }
}

MatrixFormat.java

package com.kmstudios.evaluator;

public class MatrixFormat
{
    private final char[] format;

    public MatrixFormat(char prefix, char postfix, char rowPrefix, char rowPostfix, char columnSeparator)
    {
        format = new char[5];
        if ((prefix == '[' && postfix == ']') || (prefix == '{' && postfix == '}') || (prefix == '<' && postfix == '>') || (prefix == '(' && postfix == ')'))
        {
            this.format[0] = prefix;
            this.format[1] = postfix;
        } else throw new IllegalArgumentException("cannot set matrix brackets of type " + prefix + postfix);

        if ((rowPrefix == '[' && rowPostfix == ']') || (rowPrefix == '{' && rowPostfix == '}') || (rowPrefix == '<' && rowPostfix == '>') || (rowPrefix == '(' && rowPostfix == ')'))
        {
            this.format[2] = rowPrefix;
            this.format[3] = rowPostfix;
        } else throw new IllegalArgumentException("cannot set matrix row brackets of type " + rowPrefix + rowPostfix);

        if (columnSeparator == ',' || columnSeparator == ';' || columnSeparator == ':') this.format[4] = columnSeparator;
        else throw new IllegalArgumentException("cannot set matrix column separator of type: " + columnSeparator);
    }

    public char getPrefix()
    {
        return this.format[0];
    }

    public char getPostfix()
    {
        return this.format[1];
    }

    public char getRowPrefix()
    {
        return this.format[2];
    }

    public char getRowPostfix()
    {
        return this.format[3];
    }

    public char getColumnSeparator()
    {
        return this.format[4];
    }
}

Answer 1

From the tenor of your question, I'm going to just give some high-level suggestions of approaches you might use to make your code simpler and more manageable, rather than an in-depth line-by-line review.

Performance

You expressed a few concerns about performance and mentioned design decisions you'd taken for performance reasons.

I wouldn't worry about parser performance too much: partly because premature optimization is sadness; partly because in this kind of application, parser input is generally small and parsing is relatively infrequent; and partly because optimizers are generally quite good at optimizing well-structured code.

Unless you are using your calculator in some surreally absurd way, parser performance is not something you should be worrying about. So I would suggest that you not make your life more complicated for the sake of performance.

Parsing balanced expressions

You have a lot of special-case code and state flags to handle being in particular parts of the expression (like isOpen, various checks that prev is a particular kind of character, etc).

All of this stuff would be easier to manage with a less ad-hoc approach to parsing. A recursive descent parser would probably be the easiest approach to get started with, but generally thinking about the grammar of your input language and looking at "standard" approaches to parsing should lead you in a helpful direction.

I'm sorry if the above seems a little vague---it's quite a large and broad point. But I would suggest you read up on parsing.

Parsing numbers

Numeric literals (in every context I can think of, and certainly as you have implemented them) form a regular language. You will probably find that the easiest way to parse them is either to use (simple!) regular expressions, or an explicit state machine.

There are a number of standard implementation techniques for implementing finite-state machines; the state pattern is one obvious choice, although for a language this simple I would consider a simple conditional/switch statement implementation.

Input representation

Your parser currently expects to be given a string which exactly contains a literal. This means that you effectively have to parse everything twice: once to determine the boundaries of the literal, and once to determine the meaning of the literal. This has a minor performance impact, but more critically, means that you have to smear multiple versions of your parsing code all over the place.

I would expect that you would find things more straightforward if you allowed parsing functions to greedily consume as many characters as they felt appropriate from a "stream" of input characters (either an actual stream, or some arrangement with string+offset, with each parsing function updating the offset). It should not be too difficult to arrange your language such that greedily consuming characters is always correct (although you might need a few characters of lookahead).

Evaluation

You have a little throwaway comment about an evaluator that takes a String and produces a String. I suspect it would work better if the evaluator took either a string or a parsed representation, and returned some richer object as a result (e.g., a `Literal).

Character identification

You have a lot of code like "c == '{' || c == '[' || c == '('" etc. I expect that you would find it easier to work with sets of characters, either represented using Java Sets, or, for convenience (with small sets) strings; then you could just ask openBrackets.contains('c').

On a similar note, a function like closingBracketFor(char openingBracket) that returned ) for (, } for {, etc. would simplify various things.

Answer 2

The problems we had when writing a parser were solved by breaking down the parsing to a state machine. We parsed every single character and tried to represent every state as a separate class. We got rid of deep nested if-statements and got expressive little classes that either remain the state machine in the current state or go to the next state. We remember once read characters in a buffer and put them on a stack to support recursive structures. Finally we called our expression parser recursively when we determined a separate expression.

It's a lot of additional structure code (classes) to introduce. But the effort will be benifical to future requirements.

I really suggest to have a look at following resources:

1. State Pattern
2. Interpreter Pattern

Currently I cannot provide any specific suggestions on the existing code in good conscience. This is because it would be symptom fighting if I suggest something like this:

Break parseMatrix(String mat) and parseNumber(String number) into smaller pieces.

This you will get anyway if you think about the mentioned structure.

Here I provide you an example so you get an idea what I mean.

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class NumberParser {


    public static void main(String[] args) {

        List<BigInteger> parse = new NumberParser("   10   22  32  ").parse();

        for (BigInteger bigInteger : parse) {
            System.out.println(bigInteger);
        }

    }


    private List<BigInteger> numbers;


    private final StringBuffer stringToParse;
    private final StringBuffer buffer;


    private State state;


    public NumberParser(String string) {
        this.stringToParse = new StringBuffer(string);
        this.buffer = new StringBuffer();
        this.setState(new Unknown());
    }


    private boolean hasCurrentChar() {
        return this.stringToParse.length() > 0;
    }


    private char removeCurrentChar() {
        if (hasCurrentChar()) {
            char ch = this.stringToParse.charAt(0);
            this.stringToParse.deleteCharAt(0);
            return ch;
        } else {
            throw new NoSuchElementException();
        }
    }

    private char currentChar() {
        if (this.stringToParse.length() > 0) {
            return this.stringToParse.charAt(0);
        } else {
            throw new NoSuchElementException();
        }
    }


    private void clearBuffer() {
        buffer.setLength(0);
    }


    private void recognizeNumber() {
        numbers.add(new BigInteger(buffer.toString()));
        clearBuffer();
    }


    public List<BigInteger> parse() {

        if (numbers == null) {

            this.numbers = new ArrayList<>();

            while (!(getState() instanceof End)) {
                getState().parse();
            }

        }

        return this.numbers;

    }


    private State getState() {
        return state;
    }


    private void setState(State state) {
        System.out.println(state.getStateInfo());
        this.state = state;
    }


    private interface State {
        public String getStateInfo();
        public void parse();
    }


    private interface End extends State {
    }


    private class Error implements End {

        @Override
        public String getStateInfo() {
            return "Something went wrong ...";
        }

        @Override
        public void parse() {
        }

    }


    private class NoMoreChars implements End {

        @Override
        public String getStateInfo() {
            return "No chars left.";
        }

        @Override
        public void parse() {
        }

    }


    private class RemoveWhiteSpaces implements State {

        @Override
        public String getStateInfo() {
            return "Removing white spaces.";
        }

        @Override
        public void parse() {

            if (hasCurrentChar()) {

                if (Character.isWhitespace(currentChar())) {
                    removeCurrentChar();
                } else {
                    setState(new Unknown());
                }

            } else {
                setState(new NoMoreChars());
            }

        }

    }


    private class Number implements State {

        @Override
        public String getStateInfo() {
            return "Parse digits.";
        }

        @Override
        public void parse() {

            if (hasCurrentChar()) {

                if (Character.isDigit(currentChar())) {
                    buffer.append(currentChar());
                    removeCurrentChar();
                } else {
                    recognizeNumber();
                    setState(new Unknown());
                }

            } else {
                recognizeNumber();
                setState(new NoMoreChars());
            }

        }

    }


    private class Unknown implements State {

        @Override
        public String getStateInfo() {
            return "Search ...";
        }

        @Override
        public void parse() {

            if (hasCurrentChar()) {

                if (Character.isWhitespace(currentChar())) {
                    setState(new RemoveWhiteSpaces());
                } else if (Character.isDigit(currentChar())){
                    setState(new Number());
                } else {
                    setState(new Error());
                }

            } else {
                setState(new NoMoreChars());
            }

        }

    }

}

This parser searches for numbers and returns them. Whitespaces separate numbers as whitespaces are allowed to occur multiple times. If you input alphanumeric characters the machine goes into the Error-State.

As I kept it simple you will have to distinguish several other states when parsing expressions. For example if you have an + operator you may have a stack on which at least two numbers exists.

Some other things you have to consider is an appropriate abstraction. For expressions you may have "Expression" with an evaluate-method. Numbers is this case will evaluate to themselves.

There are a lot of other things to consider. As I said: You picked one of the most difficult task in computer science for a hobby project.