Reverse Polish Notation: An Elegant Alternative for Evaluating Mathematical Expressions

There are numerous ways to write mathematical expressions. The most common is infix notation, where operators are placed between operands, such as in A + B or (C * D) - E. While this notation might seem intuitive to us humans, it's not necessarily the most optimal solution for computers and calculators. In this article, we will examine a less known, but arguably more elegant alternative: Reverse Polish Notation (RPN), also known as postfix notation.

What is Reverse Polish Notation?

RPN is a mathematical notation where operators follow their operands. Instead of writing A + B, in RPN we denote it as A B +. It might seem unusual at first glance, but its advantages quickly become apparent.

The concept of RPN originates from the Polish mathematician Jan Łukasiewicz, who developed prefix notation (Polish notation) in the 1920s, where operators precede their operands. Postfix notation is a variation of this, further developed by the Australian computer scientist Charles Hamblin in the 1950s to simplify computer processing.

Why is RPN Useful?

The main advantages of RPN are the elimination of ambiguity and computational efficiency. Infix notation requires parentheses to clarify the order of operations, and computers need complex parsing algorithms to correctly handle operator precedence. In RPN, however, parentheses are unnecessary, and the order of operations is automatically determined by the structure of the expression.

This was particularly crucial for early computers and pocket calculators where hardware resources were limited. Calculators using RPN could perform computations more simply and quickly.

Historical Tidbit: RPN notation was first popularized by Hewlett-Packard (HP) in the 1960s and 70s. The HP-9100A desktop calculator (1968) was one of the first commercially available calculators to use RPN. Later, the legendary HP-35 (1972), the first scientific pocket calculator, also employed RPN, and this method became a hallmark of HP's professional calculators for a long time. RPN calculators were renowned for their fast and accurate calculations and gained great popularity among engineers, scientists, and financial professionals.

How RPN Works

Let's look at an example of how RPN works. Consider the infix expression: (3 + 4) * 2 - 5.

First, we convert this to RPN. For the conversion, we must consider the order of operations. In this case, we first perform the addition within the parentheses, then multiply by two, and finally subtract five. The RPN expression will be: 3 4 + 2 * 5 -.

Now, let's see how to evaluate this RPN expression using a stack. A stack is a data structure into which elements can be placed (push) and removed (pop), always taking out the last inserted element first (LIFO - Last-In, First-Out).

Step-by-step evaluation of the RPN expression:

1. 3: Read 3. It's an operand, push it onto the stack. Stack state: [3]
2. 4: Read 4. Also an operand, push it onto the stack. Stack state: [3, 4]
3. +: Read the + operator. Pop two operands from the stack (first 4, then 3). Perform the addition: 3 + 4 = 7. Push the result (7) back onto the stack. Stack state: [7]
4. 2: Read 2. Operand, push onto the stack. Stack state: [7, 2]
5. *: Read the * operator. Pop two operands from the stack (first 2, then 7). Perform the multiplication: 7 * 2 = 14. Push the result (14) back onto the stack. Stack state: [14]
6. 5: Read 5. Operand, push onto the stack. Stack state: [14, 5]
7. -: Read the - operator. Pop two operands from the stack (first 5, then 14). Perform the subtraction: 14 - 5 = 9. Push the result (9) back onto the stack. Stack state: [9]

Since we have reached the end of the RPN expression and only one element remains on the stack, this element is the final result. Thus, the value of the expression (3 + 4) * 2 - 5 evaluated in RPN is 9.

How to Convert Infix Expressions to RPN?

The most common algorithm for converting infix expressions to RPN is the Shunting-yard algorithm, developed by Edsger Dijkstra. This algorithm uses a stack (for operators and parentheses) and an output queue (which can simply be a list in practice) for the conversion.

Steps of the Shunting-yard Algorithm:

1. Tokenization: Break down the infix expression into tokens (numbers, operators, parentheses).
2. Initialization: Create an empty stack for storing operators and an empty output queue for building the RPN expression.
3. Process Tokens: Iterate through the tokens:
   • Number: If the token is a number, add it to the output queue.
   • Operator (op1): If the token is an operator:
     • While there is an operator (op2) at the top of the stack, AND either:
       • op2 has greater precedence than op1, OR
       • op2 has equal precedence to op1 AND op1 is left-associative (in our example, all operators are left-associative),
     • Pop op2 from the stack and add it to the output queue.
     • Push op1 onto the stack.
   • Left Parenthesis (: Push it onto the stack.
   • Right Parenthesis ):
     • While the operator at the top of the stack is not a left parenthesis:
       • Pop the operator from the stack and add it to the output queue. (If the stack becomes empty before finding a left parenthesis, there's a mismatch.)
     • If there is a left parenthesis at the top of the stack, pop it from the stack (but do not add it to the output queue - parentheses are not included in the RPN expression).
     • If the stack top is not a left parenthesis after processing the right parenthesis, then the parentheses are mismatched.
4. Empty the Stack: When there are no more tokens to read, pop any remaining operators from the stack and add them to the output queue.
5. Result: The output queue now contains the RPN expression.

Precedence and Associativity:

Understanding operator precedence and associativity is important. The usual order of precedence (from highest to lowest):

• Multiplication (*), Division (/)
• Addition (+), Subtraction (-)

All four basic arithmetic operations are left-associative, meaning operators with the same precedence are evaluated from left to right (e.g., a - b - c = (a - b) - c).

Example of converting infix (3 + 4) * 2 - 5 to RPN using the Shunting-yard algorithm:

Token	Output Queue	Operator Stack	Remark
(		(	Left parenthesis pushed onto stack.
3	3	(	Number added to output queue.
+	3	(, +	Operator pushed onto stack.
4	3, 4	(, +	Number added to output queue.
)	3, 4, +	(	Right parenthesis: pop operators (+) to queue until left parenthesis is found. Pop left parenthesis.
*	3, 4, +	*	Operator pushed onto stack (stack was empty).
2	3, 4, +, 2	*	Number added to output queue.
-	3, 4, +, 2, *	-	Operator: * on stack has higher precedence, pop * to queue. Push - onto stack.
5	3, 4, +, 2, *, 5	-	Number added to output queue.
End	3, 4, +, 2, *, 5, -		End of input: pop remaining operators (-) from stack to queue.

Thus, the RPN form of the infix expression (3 + 4) * 2 - 5 is: 3 4 + 2 * 5 -.

Summary

Reverse Polish Notation is an elegant and efficient method for writing and evaluating mathematical expressions. Although it may seem less intuitive than infix notation at first, RPN offers several advantages, particularly for computer processing. It eliminates ambiguity, requires no parentheses, and can be efficiently evaluated using a simple stack. The Shunting-yard algorithm provides a widely used and effective method for converting infix expressions to RPN.

Its historical significance is undeniable, having played an important role in early pocket calculators, and it remains a relevant concept in computer science today, used in compilers and virtual machines. While less common in everyday use, RPN is a valuable tool and way of thinking that provides deeper insight into the relationship between mathematical expressions and computer operations.