IBU News (Germany) Edition 0.9.9

Introduction

In RPN the operands precede the operator, removing the need for parentheses. For example, the expression 3 * ( 4 + 7) would be written as 3 4 7 + *, Because of this there is no need for grouping and, similarly, no requirement for the precedence rules required by infix notation.

Implementations of RPN are stack-based; that is, operands are popped from a stack, and calculation results are pushed back onto it. Although this concept may seem obscure at first, RPN has the advantage of being extremely easy, and therefore fast, for a computer to analyze.

The algorithm for evaluating any postfix expression:

• While there are input tokens left
  1. Read the next token from input.
  2. If the token is a value ---> Push it onto the stack.
     Else the token is a function. (Operators, like +, are simply functions taking two arguments.)
     1. It is known that the function takes n arguments.
     2. If there are fewer than n values on the stack --> Error: The user has not input sufficient values in the expression.
     3. Else, Pop the top n values from the stack.
     4. Evaluate the function, with the values as arguments.
     5. Push the returned results, if any, back onto the stack.
  3. If there is only one value in the stack -> Done: That value is the result of the calculation.
  4. If there are more values in the stack ---> Error: The user input too many values.

Implementation

A RPN sentence is constructed as

<RPNTerm1> <RPNTerm2> <Op1> <RPNTerm3><Op2>...

RPN Terms are

• Terms with an optional postfix unary operator and/or an optional field specification prefix: [<Field Name>/]<Term>[<PostfixTermOp>][:<Weight>]
  
• Valid RPN sentences.

A Term is

• A word
• A literal phrase enclosed in " (quotation) marks, eg. "A literal phrase".

A weight is a non-zero integer value

• Positive := the larger, the more relevant.
• Negative := the larger, the less relevant.

"hedgehog " and FILE:shakespeare.*

Example RPN Sentences:

• term1 term2 AND
  return records that include both terms

  term1 and term2.
  
  As logical sets, term1 && term2.
  

• term1 term2 OR
  return records that include either
  term1, term2 or both terms.
  

  As logical sets, term1 || term2.
  

• term1 term2 ANDNOT
  return those records that include the
  term term1 but not the
  term term2
  
  As logical sets, term1 - (term1 && term2) .
  
• term1 term2 NEAR
  return records that include term1

  and term2 within at most a "few words" (distance or for structured data: in the same container) in-between.
  

• term1 term2 before
  return records where term1 is
  within a few
  words before term2.
  
• term1 term2 AFTER
  return records where term1 is
  within a few
  words after term2.

• term1 term2 ANDNOT term1 ANDNOT
  This is equivalent to term1 term2 and
  
• term1 NOT
  The complement of term1: all without term1.
  
• term1 term2 NOT AND
  This is the equivalent to term1 term2 ANDNOT.
  
• term1 term2 XOR
  return those records with term1 or term2 but not both
  
  As logical sets, (term1 || term2) - (term1 && term2).
  
• term1 term2 Op1 term3 term4 Op2 Op3
  
  As logical sets, (term1 Op1 term2) Op3 (term3 Op2 term4)
  

Complex Attribute Search

Example: <law domain="Bavaria">Bayerische Gesetz zum Schutz der Gesundheit<law>

To search for laws with domain "bavaria" we'd search law@domain/bavaria.
To search for laws about "Gesundheit" we'd search law/Gesundheit.

Now if we'd like to have all the laws in domain "Bavaria" that are about Gesundheit we'd search:

law@domain/Bavaria law/Gesundheit AND:.

Notice the above and:. to mean in the same place.

The query:

Schutz Gesundheit AND:LAW

means to search for "Schutz" and "Gesundheit" in the same LAW container. To combine with the above

Schutz Gesundheit AND:LAW law@domain/bavaria AND:.

to search for only those "Schutz" and "Gesundheit" terms in LAW containers where the domain is "Bavaria".

Since we can have objects other than text such as numbers in complex attributes allows us to define queries such as

LINE@NUMBER>100 LINE/spot AND:.

to find lines that contain the word "spot" in those LINE elements whose NUMBER complex attribute is greater than 100.

See also: Infix Notation Queries