Реализовывали такую штуку при помощи
ANTLR. Именно ANTLR был использован для описания грамматики. Он же генерирует парсеры/лексеры для этой грамматики (на целевом ЯП, мы использовали Java в качестве такового).
Затем необходимо будет реализовать свой visitor для AST-дерева (которое построится на основании, описанной Вами, грамматики), который собственно и будет давать вам true или false всего выражения.
Грамматику описать не сложно (примеры различных грамматик есть на просторах интернета), реализовать visitor тоже просто.