Boolean Evaluation in Apex?

I got a fairly simple one working. It might not perform as well as a more sophisticated option, but it is easy to understand.

Logic

public class BooleanExpression
{
    static Boolean orJoin(String x, String y) { return evaluate(x) || evaluate(y); }
    static Boolean andJoin(String x, String y) { return evaluate(x) && evaluate(y); }
    static Boolean isSimpleExpression(String x) { return x == 'true' || x == 'false'; }
    static String simplify(String x)
    {
        x = x.trim();
        while (x.contains('('))
        {
            String sub = x.substringAfterLast('(').substringBefore(')');
            x = x.replace('(' + sub + ')', String.valueOf(evaluate(sub)));
        }
        return x;
    }
    static Boolean evaluate(String x)
    {
        x = simplify(x);
        if (!isSimpleExpression(x))
        {
            if (x.contains('&&')) return andJoin(x.split('&&', 2));
            if (x.contains('||')) return orJoin(x.split('||', 2));
            if (x.startsWith('!')) return !evaluate(x.substring(1));
        }
        return Boolean.valueOf(x);
    }
}

Tests

I know you can just use assert(evaluate(expression)), but that feels kind of dirty here.

@IsTest
class BooleanExpressionTests
{
    static testMethod void testExpressions()
    {
        system.assertEquals(true, evaluate('true'));
        system.assertEquals(false, evaluate('!true'));
        system.assertEquals(true, evaluate('!false'));
        system.assertEquals(false, evaluate('false'));
        system.assertEquals(false, evaluate('true && !true'));
        system.assertEquals(true, evaluate('false || !false'));
        system.assertEquals(true,
            evaluate('false || (false || (!true || (false || true)))'));
    }
}

One more way may be using Reverse Polish Notation for evaluation of expressions without recursion and for linear time. My solution is just simplified version of this one.

Example of implementation some comments:

public class RPN {
    //map with priorities    
    public static Map<String,Integer> OperatorsPriorities = new Map<String,Integer>{
         '*' =>  2, // AND binary
         '+' =>  1,// OR binary
         '(' => -1, //
         ')' => -2,
         '-' => 3  //NOT - unary
    };

    public static Boolean evaluateString(String param){
        String rpn_string  = buildRPN(param);
        return evalRPN(rpn_string);
    }

    public static string buildRPN(String param){
        param = param.replace('true','t').replace('false','f').replace(' ','')
            .replace('&&','*').replace('||','+').replace('!','-');
        //to make input string smaller, do some nice replacements
        List<String> stack = new List<String>();//represent stack
        String result = '';//Reverse Polish Notation string
        Integer counter = 0;//current character position
        while(counter < param.length()){//go through input string
            String p = param.substring(counter,counter+1);//get current character
            if (p == 't' || p == 'f'){//if that is a value
                result += p;//add to RPN
            }else{
                if (OperatorsPriorities.get(p) == -1){//if that is open bracket
                    stack.add(p);//add to stack
                }else if(OperatorsPriorities.get(p) == -2){//if that is closed bracked
                    while(stack.get(stack.size() -1) != '('){//pop stack until open bracket
                        result += stack.remove(stack.size() - 1);
                    }
                    stack.remove(stack.size() - 1);//remove bracket from stack
                }else {//if that is operator
                    while (   stack.size() > 0 
                           && OperatorsPriorities.get(p) <= OperatorsPriorities.get(stack.get(stack.size() - 1))){
                        result += stack.remove(stack.size() - 1);//pop from stack to RPN until operator with lower priority meet
                    }
                    stack.add(p);
                }
            }
            counter++;
        }
        while(stack.size()> 0){//pop stack to RPN result string
            result += stack.remove(stack.size() - 1);
        }
        return result;
    }


    public static string opposite(string param){
        return (param == 't')? 'f': 't';
    }

    public static boolean evalRPN(string prn){
        List<String> elements = prn.split('');
        Integer position = 0;
        while(elements.size() > 1){//evaluate rpn string unless 1 value left
            String element = elements.get(position);//get current position
            if (element == 't' || element == 'f'){//if that is value - go forward
                position++;
            }else{
                if (element == '-'){//unary operator - replace previous value and remove it
                    elements.set(position-1,opposite(elements.get(position-1)));
                    elements.remove(position);
                    position--;
                }else if (element == '*'){//binary operator - replace prev prev value and remove prev and current 
                    String par1 = elements.get(position - 2);
                    String par2 = elements.get(position - 1);
                    String res = (par1 == 'f' || par2 == 'f')? 'f' : 't';
                    elements.set(position-2,res);
                    elements.remove(position);
                    elements.remove(position-1);
                    position -= 2;
                }else if (element == '+'){//another binary operator
                    String par1 = elements.get(position - 2);
                    String par2 = elements.get(position - 1);
                    String res = (par1 == 't' || par2 == 't')? 't' : 'f';
                    elements.set(position-2,res);
                    elements.remove(position);
                    elements.remove(position-1);
                    position -= 2;
                }
            }
        }
        return  (elements.get(0) == 't')?true:false;
    }
}