HOME WEB NEWS IMAGES CLASSIFIEDS YELLOW PAGESPOLLS - SURVEYS WIKI COUNTRIES PHOTOS US UK INDIA
Cities Stocks Weather Movies Coupons Travel Blogs Health Horoscope Maps ASIA EUROPE Classifieds Yellow Pages
 1
|
|
| Prefix notation |
| Infix notation |
| Postfix notation |
Reverse Polish scheme was proposed by F. L. Bauer and E. W. Dijkstra in early 1960s to reduce memory accesses and utilize special registers called stack to evaluate expressions. A notation for this scheme and algorithms was enriched by Australian philosopher and computer scientist Charles Hamblin in the mid-1960s.
Most of what follows is about binary operators. A unary operator for which the Reverse Polish notation is the general convention is the factorial.
Contents |
In Reverse Polish notation the operators follow their operands; for instance, to add three and four one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" in conventional infix notation would be written "3 4 − 5 +" in RPN: first subtract 4 from 3, then add 5 to that. An advantage of RPN is that it obviates the need for parentheses that are required by infix. While "3 − 4 * 5" can also be written "3 − (4 * 5)", that means something quite different from "(3 − 4) * 5", and only the parentheses disambiguate the two meanings. In postfix, the former would be written "3 4 5 * −", which unambiguously means "3 (4 5 *) −".
Interpreters of Reverse Polish notation are often stack-based; that is, operands are pushed onto a stack, and when an operation is performed, its operands are popped from a stack and its result pushed back on. Stacks, and therefore RPN, have the advantage of being easy to implement and very fast.
The algorithm for evaluating any postfix expression is fairly straightforward:
The infix expression "5 + ((1 + 2) * 4) − 3" can be written down like this in RPN:
The expression is evaluated left-to-right, with the inputs interpreted as shown in the following table (the Stack is the list of values the algorithm is "keeping track of" after the Operation given in the middle column has taken place):
| Input | Operation | Stack | Comment |
|---|---|---|---|
| 5 | Push operand | 5 | |
| 1 | Push operand | 5, 1 | |
| 2 | Push operand | 5, 1, 2 | |
| + | Add | 5, 3 | Pop two values (1, 2) and push result (3) |
| 4 | Push operand | 5, 3, 4 | |
| * | Multiply | 5, 12 | Pop two values (3, 4) and push result (12) |
| + | Add | 17 | Pop two values (5, 12) and push result (17) |
| 3 | Push operand | 17, 3 | |
| − | Subtract | 14 | Pop two values (17, 3) and push result (14) |
When a computation is finished, its result remains as the top (and only) value in the stack; in this case, 14.
Edsger Dijkstra invented the "shunting yard" algorithm to convert infix expressions to postfix (RPN), so named because its operation resembles that of a railroad shunting yard.
There are other ways of producing postfix expressions from infix notation. Most Operator-precedence parsers can be modified to produce postfix expressions; in particular, once an abstract syntax tree has been constructed, the corresponding postfix expression is given by a simple post-order traversal of that tree.
The first computers to implement architectures enabling RPN were the English Electric Company\'s KDF9 machine, which was announced in 1960 and delivered (i.e. made available commercially) in 1963, and the American Burroughs B5000, announced in 1961 and also delivered in 1963. One of the designers of the B5000, Robert S. Barton, later wrote that he developed RPN independently of Hamblin, sometime in 1958 while reading a textbook on symbolic logic, and before he was aware of Hamblin\'s work.
Friden introduced RPN to the desktop calculator market with the EC-130 in June of 1963. Hewlett-Packard (HP) engineers designed the 9100A Desktop Calculator in 1968 with RPN. This calculator popularized RPN among the scientific and engineering communities, even though early advertisements for the 9100A failed to mention RPN. The HP-35, the worlds first handheld scientific calculator, used RPN in 1972 as did the HP-10C series of calculators, including the famous financial calculator the HP-12C. When Hewlett-Packard introduced a later business calculator, the HP-19B, without RPN, feedback from financiers and others used to using the 12-C compelled them to release the HP-19BII, which gave users the option of using algebraic notation or RPN.
Existing implementations using Reverse Polish notation include:
File: postfix.bas
Dim Stack As New ByteStack
Public Sub Main()
Dim Answer As Double
Answer = EvaluatePostfix("3 2 + 5 *")
MsgBox "Answer is " & CStr(Answer), vbInformation, "Reverse Polish Notation (Postfix) Evaluator"
End
End Sub
Public Function EvaluatePostfix(Expression As String) As Double
Dim i As Integer
Dim A As Double
Dim C As Double
Dim Expn() As String
Stack.Initialize 128
Expression = Replace(Expression, " ", " ")
Expn() = Split(Expression, " ")
For i = 0 To UBound(Expn())
Select Case Expn(i)
Case "+"
Stack.POP VarPtr(C), 8
A = C + A
Case "-"
Stack.POP VarPtr(C), 8
A = C - A
Case "*"
Stack.POP VarPtr(C), 8
A = C * A
Case "/", "\"
Stack.POP VarPtr(C), 8
A = C / A
Case "^"
Stack.POP VarPtr(C), 8
A = C ^ A
Case Else
A = Val(Expn(i))
Stack.PUSH VarPtr(A), 8
End Select
Next i
EvaluatePostfix = A
End Function
File: ByteStack.cls
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (ByVal Destination As Long, Source As Any, ByVal Length As Long) Private Declare Sub RtlMoveMemory Lib "kernel32" (Destination As Any, ByVal Source As Long, ByVal Length As Long) Dim Stack() As Byte Dim TOS As Long
Public Sub Initialize(Bytes As Long) ReDim Stack(Bytes - 1) TOS = 0 End Sub
Public Sub PUSH(ptrDATA As Long, Length As Long)
If (Length + TOS - 1) > UBound(Stack()) Then
ReDim Preserve Stack(UBound(Stack()) + Length)
End If
RtlMoveMemory Stack(TOS), ptrDATA, Length
TOS = TOS + Length
End Sub
Public Function POP(ptrDATA As Long, Length As Long) As Boolean
If TOS - Length > -1 Then
TOS = TOS - Length
CopyMemory ptrDATA, Stack(TOS), Length
POP = True
End If
End Function
This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia