1

In our application users can enter custom expressions to calculate certain things. For instance they can specify an invoice and define a number of lines for cost calculation.

Example for a course with $400 price $10 transaction fee and a number of free people (say because of some credit)

  • (?numberOfParticipants? - ?creditedtTickets?) * 400 + 10

We currently have custom code that parses and executes this. But we recently found a bug in it and need to spend some time on this.

We could improve the current hacky code, we could build a proper parser but I feel this is a very generic problem that lots of people have and there should be an off the shelf solution but I can't seem to find one.

Does anybody recognize this problem and how did you handle it?

  • It's not that hard to write a simple, clean arithemetic expression parser, so I'd always write the module myself and have total control over everything. It's also easy to find one by searching for that term, but specific tool recommendations are off-topic here. – Kilian Foth Jan 15 '16 at 10:43
  • I've found that using an existing scripting language to deal with configuration like this is the cleanest solution. Easier than inventing your own config language, you don't need to worry about parsing and most importantly, there's lots of documentation and tutorials on the language that your users can turn to. – biziclop Jan 15 '16 at 11:06
  • How far off is "the current hacky code"? If it contains a few known bugs that don't require fundamental redesign to fix, and otherwise has implemented everything needed, sticking with that may be the best option. Otherwise, I would be looking for a parser library for your language. – user82096 Jan 15 '16 at 11:24
  • Which language/technology? Most have something available. For example, .NET has NCalc, Java has exp4j. You can also embed a full-service scripting language that offers on-demand compilation/evaluation like Lua or JavaScript. – Corbin March Jan 15 '16 at 13:08
1

Your expression uses what we call an infix notation, which is the notation commonly used in arithmetical statements.

One way of simplyfing parsing such expressions is converting them to Reverse Polish Notation (RPN) which turns them into a stack-based operation, for example your expression would turn into:

PUSH numberOfParticipants
PUSH creditedtTickets
SUBSTRACT
PUSH 400
MULTIPLY
PUSH 10
ADD

That list is not code, it's just a series of steps you should perform when you want to run the formula.

As you can imagine, every operation (substract, add, etc) pops the last two elements of the stack and applies the operation on them, pushing the result back into the stack.

That can be saved for executing later. You run it by iterating through the steps and doing the operations in your language of choice.

There is a known and proven algorithm called the Shunting-yard algorithm to parse back and forth between infix notation and RPN. That algorithm deals with parenthesis and operator precedence by using a railroad junction metaphor. You can parse the RPN steps back into infix notation to show them in the screen for users to see.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.