[[Linked List Stacks and Queues a Primer]]

Problem

You are given a string representing an arithmetic expression in Reverse Polish Notation (RPN). RPN is a way of writing expressions where the operator comes after its operands.

• The expression 3 + 4 becomes 3,4,+.
• The expression (3 + 4) * 2 becomes 3,4,+,2,*.

Your task: Write a function evaluate_rpn(expression) that takes this string, evaluates it, and returns the final integer result. You can assume the expression is always valid.

Brainstorming

This is a classic and direct application of STACK data structure for it clearly depends on the LIFO ( last in first out ) operation

lets do it by hand and simulate it for  3,4,+. (3+4)

1. you pick 3 see its a number you add to you stack
2. you see 4 see its a number you add it to your stock
3. you see + its an operator , now we need to do the operation for the 2 values in the stack
   1. you pop 4 its your first operand y
   2. you pop again this time its 3 your second operand x
   3. Now you do the operation ( 4 + 3) = 7 you push the result to the stack
   4. You move ahead
4. The value at the top of the stack after all the operations is your final answer

Lets try to do the code for it

import operator 

expression = "3,4,+,2,*,1,+"

def evaluate_rfpn(expression:str):
	intermediate_result = [] # initalize your stack
	# We don't need the operator module, lambdas are great here 
	operators = { "+": lambda y, x: x + y, 
				"-": lambda y, x: x - y, 
				"*": lambda y, x: x * y, 
				"/": lambda y, x: int(x / y) 
				# Handle integer division }

	"""
	operators = {"+":operator.add, 
				"/":operator.truediv, 
				"*":operator.mul, 
				 "-":operator.sub} # using a hash set for (O(1)) lookup
	"""
	tokens = expression.split(',)
	for token in expression:
		if token not in operators:
			intermediate_result.append(int(token)) # add the number as int
		else:
			operation = operators[token]
			x = intermediate_result.pop()
			y = intermediate_result.pop()
			result = operation(int(x),int(y))
			intermediate_result.append(result)
	 
	return intermediate_result.pop()
			
	

Key learnings

How to store operations in a hash dict

The problem in the book (and most versions of this problem) specifies that division should truncate towards zero, which is what standard integer division does. Your use of operator.truediv will produce a float (e.g., 6 / -132 would give -0.045…). We should use integer division.

The Fix: Python’s integer division operator is //. We can implement this with a lambda function in our dictionary.

# A lambda function to handle integer division correctly
'/': lambda y, x: int(x / y)