BODMAS assignment

Question

Hello All,

Im working on a problem that goes like this -

Implement a function that evaluates an expression consisting of following operands : '(', ')', '+', '-', '*', '/'. Each numbers in the expression could be large (as large as being represented by string of 1000 digits). The '/' (i.e. divide) operand returns the integer quotient.

The test cases go like -

( ( ( 10000000000000000000000001231234448563465435434723854278423 / 1111111111234623874627 ) * 2342384523 + 123124 - 34534534 ) * ( 1231263123242346 + 223423234346 * 234236536 ) )

and could be even longer.

I do not want to use external libraries which are expression evaluators/parsers like JEP and the like.

I was thinking along the lines of BigInteger and then came to know that BigIntegers do not evaluate epressions like Integers do. I also know that parsing is an option where in i would have to simulate the BODMAS behaviour.I would like to know if there is any other way to go about this and if there isnt, would like some pointers on how i could get this implemented.

I am not looking for a readymade solution, just looking for directions to arrive at the solution by myself.

Answer 1

You can implement this as a finite state machine then implement it using the state pattern. I can't find any examples of a BODMAS state machine unfortunately but they must be out there somewhere.

Answer 2

You could create a recursive descent parser to evaluate the expression and use StringTokenizer as a spimple lexer to split up the line. You can use delim = "()/*-+" and returnDelims = true. This will return the numbers and the delimeters whoch in your case are the operators and parenthesis you need to evaluate.