How to do a complex search with UI input?

I am planning to do a complex query of things. Imagine a CRM type list of contacts and I want to create a view of contacts based on complex AND or OR operand queries.

Queries like ((name starts with "a" or "b" and ends with "s") or (last name contains "x" and last name contains "o" and does not end with "x" ))

Before I roll up my sleeves I want to consult for tips.

I am thinking I should save the criteria into a “segment criteria” thing, and then do a search for contacts:filtered Advanced: etc.

Now I didn’t completely thought this through but I hope it’s the correct approach for this.

What are your suggestions?

Note: I completely edited this post, taking a new approach.