GameDev.netUnderstanding Reverse Polish Notation

Understanding Reverse-Polish Notation For those of us using or considering a Hewlett-Packard scientific calculator or computer, the question often arises, "What the heck is Reverse-Polish Notation?" The conventional mathematical notation we learned in high school is known as "Algebraic Notation." In this notation, the operators are placed either between or in front of the arguments. Operators designate the operation to be performed ("+", "*", "sin", etc.) and arguments are the values or variables upon which they act ("1", "42.5", "pi", "x", etc.). A typical mathematical expression might be: sin[123 + 45 ln(27 - 6)] The operators in this expression, from left to right, are "sin", "+", "*" (implied between "45" and "ln"), "ln", and "-". By their natures, "sin" and "ln" require one argument each while "+", "*", and "-" require two each. The arguments are not so easily determined. At first glance they appear to be "123", "45", "27", and "6", but this is patently false! The argument of "sin" is everything within the brackets, or "123 + 45 ln(27 - 6)", those of "+" are "123" and "45 ln(27 - 6)", those of "*" are "45" and "ln(27 - 6)", that of "ln" is "27 - 6", and those of "-" are "27" and "6". The whole expression may be thought of as a series of separate operations: sin[123 + 45 ln(27 - 6)] = sin(a) :: a = 123 + 45 ln(27 - 6) 123 + 45 ln(27 - 6) = 123 + b :: b = 45 ln(27 - 6) 45 ln(27 - 6) = 45 * c :: c = ln(27 - 6) ln(27 - 6) = ln(d) :: d = 27 - 6 27 - 6 It is because of this that complex expressions are performed from the inside out: sin[123 + 45 ln(27 - 6)] = sin[123 + 45 ln(21) sin[123 + 45 ln(21)] = sin(123 + 45 * 3.04452243772) sin(123 + 45 * 3.04452243772) = sin(123 + 137.003509697) sin(123 + 137.003509697) = sin(260.003509697) sin(260.003539697) = 0.680672740775 In this manner, it can easily be seen that each operation is a function of its argument or arguments, and an argument may itself be a function of other arguments. Therefore, if we were to treat the operations exactly as functions of arguments in the traditional ¦(x) and ¦(y,x) formats, the expression "27 - 6" would become -(27,6), where "-" is the operator "¦", "27" is the argument "y", and "6" is the argument "x": 27 - 6 -> -(27,6) This is a two-argument function: in any two-argument function, the second argument will always act against the first argument. In this case, the second argument "6" will be subtracted from the first argument "27". The concept of treating all operators as functions is not as strange as it first appears when you consider that a considerable number of operators are already functions: ln(x) is ¦(x) where "¦" is "ln". In the case of our example expression, the next function out is ln(d), where "d" is itself the function -(27,6): 27 - 6 -> -(27,6) ln(27 - 6) -> ln(-(27,6)) 45 ln(27 - 6) -> *(45,ln(-(27,6))) 123 + 45 ln(27 - 6) -> +(123,*(45,ln(-(27,6)))) sin[123 + 45 ln(27 - 6)] -> sin(+(123,*(45,ln(-(27,6))))) The final function sin(+(123,*(45,ln(-(27,6))))) may at first seem confusing, especially with all the parentheses, until one remembers that it is the one-argument function sin(x). Once this is realized, then everything within the parenthesis following "sin" must be the one and only argument of sin(): the argument of sin() must be +(123,*(45,ln(-(27,6)))). In a similar manner, +(123,*(45,ln(-(27,6)))) is the two-argument function +(y,x), where "y" is "123" and "x" is *(45,ln(-(27,6))). A further clarification can be made if "+(y,x)" is thought of as "the sum of y and x" (just as "ln(x)" is "the natural logarithm of x"). This approach allows "sin(+(123,*(45,ln(-(27,6)))))" to be read as "the sine of the sum of 123 and the product of 45 and the natural logarithm of the difference of 27 and 6." This phrase readily illustrates its clarity when emphasized function by function: sin(+(123,*(45,ln(-(27,6))))) The sine of sin(...) the sum of sin(+(...)) 123 and the product of sin(+(123,*(...))) 45 and the natural logarithm of sin(+(123,*(45,ln(...)))) the difference of sin(+(123,*(45,ln(-(...))))) 27 and 6. sin(+(123,*(45,ln(-(27,6))))) Awkward as that may seem, it is much cleaner and more straightforward than "sin[123+45ln(27-6)]," which is "the sine of the quantity 123 plus 45 times the natural logarithm of the quantity 27 minus 6." What is even more important, it is unambiguous! If you heard someone say "the quantity 123 plus 45 times the natural logarithm of ...," does the speaker mean "(123+45)ln()" or "(123+(45ln()))". By defining all operations as functions there is no ambiguity, ever! In algebra, a complex set of rules has been established as regards order and priority of operations, and if these rules are strictly followed there will be no ambiguity. Unfortunately, few of the "algebraic" calculators or software packages on the market follow these rules properly, and there is a total lack of consistency in which rules are overlooked or changed. What is needed with a calculator or computer is a mechanistic and totally unambiguous method of operation. Treating all arguments as functions provides just such a method and is known as Polish Notation after its creator, the Polish logician Jan Lukasiewicz. The complex function sin(+(123,*(45,ln(-(27,6))))) has one and only one possible meaning, whether written in mathematical symbology or spoken aloud. Further research by the logicians at Hewlett-Packard provided a slight variation on the theme. If instead of placing the function ahead of its argument(s), it is placed behind, we get: sin(+(123,*(45,ln(-(27,6))))) ————————————————————————————— sin( ) ——> ( )sin +(123, ) ——> (123, )+ *(45, ) ——> (45, )* ln( ) ——> ( )ln -(27,6) ——> (27,6)- ————————————————————————————— ((123,(45,((27,6)-)ln)*)+)sin This method is known as Reverse Polish Notation, or RPN, in honor of the original method. RPN, like Polish Notation, is unambiguous: the order and only the order of arguments and operators will determine the result. Since this is the case, the parentheses and commas are irrelevant, and we may express our function as: ((123,(45,((27,6)-)ln)*)+)sin -> 123 45 27 6 - ln * + sin This allows a simple and straightforward solution to calculator or software mathematics: treat both the functions and their arguments alike as "objects," and process them in a last-in, first-out (LIFO) storage structure, a "stack." When a function-object is entered onto the stack, it operates upon the argument-object(s) already there to produce a result, which replaces the argument-object(s). The stack adjusts accordingly. This can be seen as:
The secret behind RPN's sophisticated yet simple power is in the stack. In computer terms, a stack is an area in which pieces of information may be stored on a last-in, first-out (LIFO) basis. Think of the stack as a stack of plates: the last plate placed on the stack will be the first plate used. Most simple RPN calculators use a four-level stack, with the levels labeled "x", "y", "z", and "t". Some newer, more sophisticated calculators (such as the HP-28S and the HP-48SX) and most software programs use an "infinite" stack: the number of stack levels is limited only by available memory. The levels in an infinite stack are usually numerical. Entering a value will cause a stack lift: existing values will be pushed up a level. Entering a function will consume the arguments of the function. If this consumption causes a "hole," the values above the hole will be dropped to fill the hole. Following through our example on an HP-48SX calculator:
© 1999-2011 Gamedev.net. All rights reserved. |