IMAP protocol uses Polish notation (also known as prefix notation) for client queries. In general it means, that operator (in case of IMAP search it’s always a logical operator) is placed left of its operands.
Polish notation
Expression that would be written in conventional infix notation as:
(5 − 6) * 7
can be written in prefix/Polish notation as:
* (− 5 6) 7
As all mathematical operands are binary (or have defined number of operands) we don’t need parentheses to correctly evaluate this expression:
* − 5 6 7
Polish notation doesn’t require parentheses.
IMAP search needs parentheses
Although IMAP search syntax uses Polish notation it actually requires parentheses to be evaluated unambiguously.
This is because there is no explicitly defined AND operator, that takes exactly 2 operands.
RFC 3501:
When multiple keys are specified, the result is the intersection (AND function) of all the messages that match those keys.
So although it is true that Polish and reverse Polish notations don’t require parentheses, it is not true that IMAP search doesn’t require them.
‘OR/AND’ example
Expression 1a:
Regular notation:
(SUBJECT subject OR BODY body) AND FROM from
Polish notation:
AND OR SUBJECT subject BODY body FROM from
IMAP’s Polish notation (note there is no AND operator):
OR SUBJECT subject BODY body FROM from
Expression 1b:
Regular notation:
SUBJECT subject OR (BODY body AND FROM from)
Polish notation:
OR SUBJECT subject AND BODY body FROM from
IMAP’s Polish notation (note there is no AND operator):
OR SUBJECT subject BODY body FROM from
1a != 1b
Expression 1a is not equal to Expression 1b:
((a or b) and c) != (a or (b and c))
For:
a = true
b = true
c = false
We have:
((true or true) and false) != (true or (true and false))
false != true
Parentheses are needed
But when there is no AND operator, IMAP’s Polish notations look exactly the same, thus we need parentheses!
Expression 1a (IMAP’s Polish notation with parentheses):
(OR SUBJECT subject BODY body) FROM from
Expression 1b (IMAP’s Polish notation with parentheses):
OR SUBJECT subject (BODY body FROM from)
OR SUBJECT subject BODY body FROM from
is treated like
(OR SUBJECT subject BODY body) FROM from
‘NOT’ example
Expression 2a:
Regular notation:
NOT (SUBJECT subject AND BODY body)
Polish notation:
NOT AND SUBJECT subject BODY body
IMAP’s Polish notation (note there is no AND operator):
NOT SUBJECT subject BODY body
Expression 2b:
Regular notation:
(NOT SUBJECT subject) AND BODY body
Polish notation:
AND NOT SUBJECT subject BODY body
IMAP’s Polish notation (note there is no AND operator):
NOT SUBJECT subject BODY body
2a != 2b
Expression 2a is obviously not equal to Expression 2b.
Parentheses are needed
Again IMAP’s Polish notations look the same. We need parentheses!
Expression 2a (IMAP’s Polish notation with parentheses):
NOT (SUBJECT subject BODY body)
Expression 2b (IMAP’s Polish notation with parentheses):
(NOT SUBJECT subject) BODY body
NOT SUBJECT subject BODY body
is treated like
(NOT SUBJECT subject) BODY body