Prefix and infix notation By default, Verity uses infix notation, in which precedence is implicit in the expression; for example, the AND operator takes precedence over the OR operator. You can use prefix notation with any operator except an evidence operator (typically, STEM, WILDCARD, or WORD; for a description of evidence operators, see Evidence operators). In prefix notation, the expression explicitly specifies precedence. Rather than repeating an operator, you can use prefix notation to list the operator once and list the search targets in parentheses. For example, the following expressions are equivalent: Moses Larry Jerome Daniel Jacob (Moses,Larry,Jerome,Daniel,Jacob) The following prefix notation example searches first for documents that contain Larry and Jerome, then for documents that contain Moses: OR (Moses, AND (Larry,Jerome)) The infix notation equivalent of this is as follows: Moses OR (Larry AND Jerome) Infix notation From Wikipedia, the free encyclopedia. Infix notation is the arithmetic formula notation known to most people, in which operators are written infix-style between the operands they act on. It is not as simple to parse by computer as postfix notation, but many programming languages use it to take advantage of its familiarity. In infix notation, unlike in postfix or prefix notations, parentheses surrounding groups of operands and operators are necessary to indicate the intended order in which operations are to be performed. In the absence of parentheses, certain precedence rules determine the order of operations. These are explained in the order of operations article. Reverse Polish notation From Wikipedia, the free encyclopedia. (Redirected from Postfix notation) Reverse Polish notation (RPN) , also known as postfix notation, is an arithmetic formula notation, derived from the polish notation introduced in 1920 by the Polish mathematician Jan Lukasiewicz. RPN was invented by Australian philosopher and computer scientist Charles Hamblin in the mid-1950s, to enable zero-address memory stores. As a user interface for calculation the notation was first used in Hewlett-Packard's desktop calculators from the late 1960s and then in the HP-35 handheld scientific calculator launched in 1972. In RPN the operands precede the operator, thus dispensing with the need for parentheses. For example, the expression 3 * ( 4 + 7) would be written as 3 4 7 + *, and done on an RPN calculator as "3", "Enter", "4", "Enter", "7", "+", "*". 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 due to it being a regular grammar. Contents [showhide] 1 Practical implications 2 Example 3 Converting from infix notation 3.1 A simple conversion 3.2 The algorithm in detail 3.3 Complex example 4 Real-world RPN use 5 See also 6 External links [edit] Practical implications Calculations proceed from left to right There are no brackets or parentheses, as they are unnecessary. Operands precede operator. They are removed as the operation is evaluated. When an operation is made, the result becomes an operand itself (for later operators) There is no hidden state. No need to wonder if you hit an operator or not. [edit] Example The calculation: ((1 + 2) * 4) + 3 can be written down like this in RPN: 1 2 + 4 * 3 + The expression is evaluated in the following way (the Stack is displayed after Operation has taken place): Input Stack Operation 1 1 Push operand 2 1, 2 Push operand + 3 Addition 4 3, 4 Push operand * 12 Multiplication 3 12, 3 Push operand + 15 Addition The final result, 15, lies on the top of the stack at the end of the calculation. An alternate way of viewing the stack during the above operation is shown below (as seen on HP48S calculator). +---------------+ + + + + + 1 + 1 enter +---------------+ +---------------+ + + + 1 + + 2 + 2 [enter] +---------------+ +---------------+ + + + + + 3 + + +---------------+ +---------------+ + + + 3 + + 4 + 4 [enter] +---------------+ +---------------+ + + + + + 12 + * +---------------+ +---------------+ + + + 12 + + 3 + 3 [enter] +---------------+ +---------------+ + + + + + 15 + + +---------------+ The enters are in brackets because they are optional when proceded by an operator press. An enter is only needed to clear the insertion mark from the line. Thus, RPN allows the expression to be entered and evaluated in eight rather than eleven or twelve steps. [edit] Converting from infix notation Like the evaluation of RPN, conversion from infix notation to RPN is stack-based. Infix expressions are the form of math most people are used to, for instance 3+4 or 3+4*(2-1). For the conversion there are 2 text variables (strings), the input and the output. There is also a stack holding operators not yet added to the output stack. To convert, the program reads each letter in order and does something based on that letter. [edit] A simple conversion Input: 3+4 #Add 3 to the output stack (whenever a number is read it is added to the output) #Add 4 to the output stack #Push + (or its ID) onto the operator stack #After reading expression pop the operators off the stack and add them to the output. # In this case there is only one, "+". #Output 3 4 + This already shows a couple of rules: All numbers are added to the output when they are read. At the end of reading the expression, pop all operators off the stack and onto the output. [edit] The algorithm in detail While there are tokens to be read: Read a token. If the token is a number, then add it to the output. If the token is an operator, o1, then: 1) while there is an operator, o2, at the top of the stack, and either o1 is left-associative and its precedence is less than or equal to that of o2, or o1 is right-associative and its precedence is less than that of o2, pop o2 off the stack, onto the output; 2) push o1 onto the stack. If the token is a left parenthesis, then push it onto the stack. If the token is a right parenthesis, then pop operators off the stack, onto the output, until the token at the top of the stack is a left parenthesis, at which point it is popped off the stack but not added to the output. If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. When there are no more tokens to read, pop all the tokens, if any, off the stack, add each to the output as it is popped out and exit. (These must only be operators; if a left parenthesis is popped, then there are mismatched parentheses.) [edit] Complex example Input 3+4*2/(1-5)^2 Read "3" Add "3" to the output Output: 3 Read "+" Push "+" onto the stack Output: 3 Stack: + Read "4" Add "4" to the output Output: 3 4 Stack: + Read "*" Push "*" onto the stack Output: 3 4 Stack: + * Read "2" Add "2" to the output Output: 3 4 2 Stack: + * Read "/" Pop "*" off stack and add it to output, push "/" onto the stack Output: 3 4 2 * Stack: + / Read "(" Push "(" onto the stack Output: 3 4 2 * Stack: + / ( Read "1" Add "1" to output Output: 3 4 2 * 1 Stack: + / ( Read "-" Push "-" onto the stack Output: 3 4 2 * 1 Stack: + / ( - Read "5" Add "5" to output Output: 3 4 2 * 1 5 Stack: + / ( - Read ")" Pop "-" off stack and add it to the output, pop ( Output: 3 4 2 * 1 5 - Stack: + / Read "^" Push "^" onto stack Output: 3 4 2 * 1 5 - Stack: + / ^ Read "2" Add "2" to output Output: 3 4 2 * 1 5 - 2 Stack: + / ^ End of Expression Pop stack to output Output: 3 4 2 * 1 5 - 2 ^ / + If you were writing an interpreter, this output would be tokenized and written to a compiled file to be later interpreted. Conversion from Infix to RPN can also allow for easier computer simplification of expressions. To do this, act like you are solving the RPN expression, however, whenever you come to a variable its value is null, and whenever an operator has a null value, it and its parameters are written to the output (this is a simplification, problems arise when the parameters are operators). When an operator has no null parameters its value can simply be written to the output. This method obviously doesn't include all the simplifications possible. [edit] Real-world RPN use Forth programming language Hewlett-Packard science/engineering calculators PostScript page description language TI-68k (TI-89) implementation (http://www.paxm.org/symbulator/download/rpn.html) Unix system calculator program dc Writing an Interpreter Interactive JavaScript calculator with RPN (http://main.linuxfocus.org/~guido/javascript/rpnjcalc.html) [edit] See also Stack machine Subject Object Verb Subject Verb Object Infix notation [edit] External links RPN or DAL? by James Redin -------------------------------------------------------------------------------- To add "eighth plus six" in your normal calculator you just press the following sequence of keys: [8] [+] [6] [=] Very simple, right? Now, how would you do the same operation in an RPN calculator? The procedure involves to enter the two operands first and then its operator. This yields the following sequence: [8] [ENTER] [6] [+] Notice that the sequence still requires four keystrokes, although it may look a little confusing if you never had an HP calculator. Hewlett-Packard have used the "Reverse Polish Notation, RPN" since they launched the first scientific pocket calculator, the HP-35, back in 1972. Two of the reasons why Hewlett-Packard decided to use the RPN notation as opposed to the Direct Algebraic Logic (ADL) used on standard calculators were probabily the following: first, Reverse Polish Notation is a very efficient way for a chip logic to perform calculations, and second, a technical user, which was the main target for scientific calculators, can perform more complicated calculations with less number of keystrokes, by using this procedure. To illustrate this, lets take two simple examples which do not use scientific functions: -------------------------------------------------------------------------------- CASE A: Solve the following expression: (8 + 6)(7 - 5) With a normal calculator, assuming you have memory functions, you have to enter: [8][+][6][=] [M+] [7][-][5] [x] [MR] [=] while, with an RPN calculator you just enter: [8][ENTER][6][+] [7][ENTER][5][-] [x] RPN required only 9 keystrokes instead of the 11 required by a standard calculator. -------------------------------------------------------------------------------- CASE B: Solve the following expression: [(8 + 6)(7 - 5)] / (9 - 7) A user with a standard calculator still can solve this expression (without memorizing or noting subtotals in a piece of paper), but the solution is tricky as shown in the following sequence: [8][+][6][=][M+] [7][-][5][x][MR][=] [MC][M+] [9][-][7][/][MR][=][MC][M+][1][/][MR][=] Instead of the 25 keystrokes and a lot of ingenuity, an RPN calculator would require only 14 strokes and the application of the same basic technique: evaluate one operation at a time by entering the two operands first and then the operator that acts upon them: [8][ENTER][6][+] [7][ENTER][5][-] [x] [9][ENTER][7][-] [/] -------------------------------------------------------------------------------- Obviously, once you get the feeling of the technique it is not only efficient but also elegant, and this was one of the reasons why HP RPN calculators were so widely accepted among technical users. In a normal arithmetic expression, operations are grouped within parentheses to control the precedence of the operations. Segments of the expression which are enclosed within parentheses must be solved prior to continuing with the remaining parts of the expression. Parentheses can also be nested, in which case inner parentheses have precedence and must be solved first. A polish mathematician, Jan Lukasiewicz, demonstrated in 1929 (though even this may be late; it could be as early as 1922 [3]) that parentheses are not required to specify the sequence of operations within an expression. He showed that the reason why parentheses are used is because the operator is inserted in between the operands and operands cannot be used as delimiters in the expression, however, if the operator is specified before (Polish Notation) or after (Reverse Polish Notation) the operands, then the operator acts also as a delimiter or separator of the different expression components, and the order may then be controlled by setting a left-to-right precedence of the expression components. This left-to-right precedence is very compatible with the sequential nature of operations in a computing device. LIFO (Last-In-First-Out) algorithms and sequential stacks are common place in compilers and computer languages. So it was natural for early scientific calculators to use the RPN notation. The usage of standard algebraic approach introduced additional complexity and overhead which was not desirable at the point where the technology was in 1972 when the first scientific calculator was introduced in the market by Hewlett-Packard. The RPN method, however, proved to be successful not only from the point of view of chip design efficiency but also from the point of view of human operation. Once the user gets the basic understanding on the technique, its elegance converts users into RPN fans, which is one of the factors responsible by the popularity of HP among technical users. Of course, the advantage tends to disappear when the operations are simple, like the ones normally handled in standard four function calculators, and this is the reason why standard non-scientific calculators do not use RPN notation. More over, non-HP scientific calculators, such as the ones manufactured by Texas Instruments, relied on the algebraic model for their data-entry by providing parentheses as part of the keyboard, at the beginning that imposed limitations on the number of nested levels that could be handled, but these limitations started to disappear as new models arrived. Another limitation of the algebraic model was the fact that even with the usage of parenthesis, the operators had to be entered by the user explicitly, even though the usual expression involved the implicit multiplication operator. For example, to solve the expression 5(8-2), the user had the enter the sequence: [5] [x] [(][8][-][2][)] [=] This can become very inconvenient in certain expressions. To overcome this problem, Sharp developed a technology called "Advanced Direct Algebraic Logic (Advanced DAL)," which allows for the user to enter an expression in the same way as it appears in a text on a written document. For example, the expression: 2 sin(45+2^3) would be entered as: [2] [sin] [(] [4][5] [+] [2] [^] [3] [)] [=] This simplifies significantly the number-entry procedure and constitutes an interesting progress in the usage of algebraic notation within scientific calculators. Under RPN, the previous expression may be entered as: [2][ENTER][3][^] [4][5] [+] [sin] [2] [x] One less stroke was required by the RPN procedure. In addition, RPN fans will state that the RPN procedure gives a better understanding on what the expression is actually doing. And most probabily they will be right. On the other hand, ADL advocates will say that entering the expression actually implies that there is already a previous understanding on what the expression is doing, so they would rather leave the chip circuits to determine the sequence on which the elemental operations need to be performed. And most probably, they will also be right… Sources: [1] Hewlett-Packard, "What's Reverse Polish Notation (RPN)?" http://hpcc923.external.hp.com/abouthp/features/hp35calculator/rpn/ [2] Thomas M. Whitney, France Rode, and Chung C. Tung , "The 'Powerful Pocketful': an Electronic Calculator Challenges the Slide Rule." Hewlett-Packard Journal, June 1972, Article 1 - Sidebar: "Reverse Polish Notation" http://hpcc923.external.hp.com/hpj/72jun/ju72a1.htm [3] David Hemmendinger - Notes from the 4th. Edition of the "Encyclopedia of Computer Science" to be published in 1998. --------------------------------------------------------------------------------