Index: trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java
===================================================================
--- trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java	(revision 9929)
+++ trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java	(revision 9930)
@@ -453,5 +453,6 @@
         @Override
         public String toString() {
-            return lhs + " && " + rhs;
+            return (lhs instanceof BinaryMatch && !(lhs instanceof And) ? "(" + lhs + ")" : lhs) + " && "
+                    + (rhs instanceof BinaryMatch && !(rhs instanceof And) ? "(" + rhs + ")" : rhs);
         }
     }
@@ -477,5 +478,6 @@
         @Override
         public String toString() {
-            return lhs + " || " + rhs;
+            return (lhs instanceof BinaryMatch && !(lhs instanceof Or) ? "(" + lhs + ")" : lhs) + " || "
+                    + (rhs instanceof BinaryMatch && !(rhs instanceof Or) ? "(" + rhs + ")" : rhs);
         }
     }
@@ -501,5 +503,6 @@
         @Override
         public String toString() {
-            return lhs + " ^ " + rhs;
+            return (lhs instanceof BinaryMatch && !(lhs instanceof Xor) ? "(" + lhs + ")" : lhs) + " ^ "
+                    + (rhs instanceof BinaryMatch && !(rhs instanceof Xor) ? "(" + rhs + ")" : rhs);
         }
     }
Index: trunk/test/unit/org/openstreetmap/josm/actions/search/SearchCompilerTest.java
===================================================================
--- trunk/test/unit/org/openstreetmap/josm/actions/search/SearchCompilerTest.java	(revision 9929)
+++ trunk/test/unit/org/openstreetmap/josm/actions/search/SearchCompilerTest.java	(revision 9930)
@@ -4,8 +4,6 @@
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertThat;
 import static org.junit.Assert.assertTrue;
 
-import org.hamcrest.CoreMatchers;
 import org.junit.Before;
 import org.junit.Test;
@@ -97,4 +95,5 @@
         assertTrue(c.match(newPrimitive("name", "hello-foo-xy")));
         assertFalse(c.match(newPrimitive("name", "X")));
+        assertEquals("foo", c.toString());
     }
 
@@ -110,4 +109,5 @@
         assertFalse(c.match(newPrimitive("fooX", "bar")));
         assertFalse(c.match(newPrimitive("foo", "barX")));
+        assertEquals("foo=bar", c.toString());
     }
 
@@ -186,5 +186,5 @@
     @Test
     public void testNthParseNegative() throws ParseError {
-        assertThat(SearchCompiler.compile("nth:-1").toString(), CoreMatchers.is("Nth{nth=-1, modulo=false}"));
+        assertEquals("Nth{nth=-1, modulo=false}", SearchCompiler.compile("nth:-1").toString());
     }
 
@@ -408,3 +408,22 @@
         assertFalse(search.match(n1));
     }
+
+    /**
+     * Tests the implementation of the Boolean logic.
+     * @throws ParseError if an error has been encountered while compiling
+     */
+    @Test
+    public void testBooleanLogic() throws ParseError {
+        final SearchCompiler.Match c1 = SearchCompiler.compile("foo AND bar AND baz");
+        assertTrue(c1.match(newPrimitive("foobar", "baz")));
+        assertEquals("foo && bar && baz", c1.toString());
+        final SearchCompiler.Match c2 = SearchCompiler.compile("foo AND (bar OR baz)");
+        assertTrue(c2.match(newPrimitive("foobar", "yes")));
+        assertTrue(c2.match(newPrimitive("foobaz", "yes")));
+        assertEquals("foo && (bar || baz)", c2.toString());
+        final SearchCompiler.Match c3 = SearchCompiler.compile("foo OR (bar baz)");
+        assertEquals("foo || (bar && baz)", c3.toString());
+        final SearchCompiler.Match c4 = SearchCompiler.compile("foo1 OR (bar1 bar2 baz1 XOR baz2) OR foo2");
+        assertEquals("foo1 || (bar1 && bar2 && (baz1 ^ baz2)) || foo2", c4.toString());
+    }
 }