class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class Stack:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
def push(self, data):
new_node = Node(data)
if self.length == 0:
self.head = self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
def peek(self):
return self.tail.data
def pop(self):
ret = self.tail.data
if self.length == 1:
self.head = self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
self.length -= 1
return ret
def __iter__(self):
self._iter_node = self.head
return self
def __next__(self):
if self._iter_node is None:
raise StopIteration
ret = self._iter_node.data
self._iter_node = self._iter_node.next
return ret
def __str__(self):
return str([value for value in self])
def __len__(self):
return self.length
In order to implement postfix notation:
For each item in the postfix list, a) Check if it is an operator, if so: i) Pop out the first top two elements from the list and make the operation. Always make sure that the second element popped is the one that is the first one on the operation b) If not, keep looping through the numbers and add them to the stack.
Make sure that the tokenize function is robust: a) It can accept items separated by: (i) Spaces (ii) Commas (iii) No separation
import re
def tokenize(expression):
return re.findall(r"\d+|\*+|[-+/()]", expression)
def process_sum(stack):
top_item = stack.pop()
second_item = stack.pop()
result = second_item + top_item
stack.push(result)
def process_minus(stack):
top_item = stack.pop()
second_item = stack.pop()
result = second_item - top_item
stack.push(result)
def process_multiplication(stack):
top_item = stack.pop()
second_item = stack.pop()
result = second_item * top_item
stack.push(result)
def process_division(stack):
top_item = stack.pop()
second_item = stack.pop()
result = second_item / top_item
stack.push(result)
def process_intdivision(stack):
top_item = stack.pop()
second_item = stack.pop()
result = second_item // top_item
stack.push(result)
def process_power(stack):
top_item = stack.pop()
second_item = stack.pop()
result = second_item ** top_item
stack.push(result)
processes = {"+": process_sum, "-": process_minus, "/": process_division, "//": process_intdivision,
"*": process_multiplication, "**": process_power}
def postfix_to_output(expression):
tokens = tokenize(expression)
stack = Stack()
for token in tokens:
if token in processes:
processes[token](stack)
else:
token = float(token)
stack.push(token)
return print(stack.pop())
expressions = [
"4 6 -",
"4 1 2 9 3 / * + 5 - *",
"1 2 + 3 -",
"1 2 - 3 +",
"10 3 5 * 16 4 - / +",
"5 3 4 2 - ** *",
"12 2 4 + / 21 *",
"1 1 + 2 **",
"1 1 2 ** +"
]
for expression in expressions:
postfix_to_output(expression)
-2.0 8.0 0.0 2.0 11.25 45.0 42.0 4.0 2.0
Read a token
If it's a number add it to queue
If it's an operator
While there's an operator on the top of the stack with greater precedence:
Pop operators from the stack onto the output queue
Push the current operator onto the stack
If it's a left bracket push it onto the stack
If it's a right bracket
While there's not a left bracket at the top of the stack:
Pop operators from the stack onto the output queue.
Pop the left bracket from the stack and discard it
hierarchy = {"+": 1, "-": 1, "/": 2, "*": 2, "//": 2, "**":3}
def infix_to_postfix(expression):
tokens = tokenize(expression)
stack = Stack()
postfix = []
for token in tokens:
if token == "(":
stack.push(token)
elif token == ")":
while stack.peek() != "(":
postfix.append(stack.pop())
stack.pop()
elif token in hierarchy:
while len(stack) > 0 and stack.peek() in hierarchy and hierarchy[stack.peek()] >= hierarchy[token]:
postfix.append(stack.pop())
stack.push(token)
else:
postfix.append(token)
while len(stack) > 0:
postfix.append(stack.pop())
return " ".join(postfix)
def evaluate(expression):
postfix = infix_to_postfix(expression)
output = postfix_to_output(postfix)
return output
expressions = [
"1 + 1",
"1 * ( 2 - ( 1 + 1 ) )",
"4 * ( 1 + 2 * ( 9 / 3 ) - 5 )",
"10 + 3 * 5 / ( 16 - 4 * 1 )",
"2 * 2 * 2 * 2 * 2 * 2 * 2 * 2",
"2 ** 2 ** 2 ** 2 ** 2",
"( 1 - 2 ) / ( 3 - 5 )",
"9 / 8 * 8",
"64 / ( 8 * 8 )",
]
for expression in expressions:
evaluate(expression)
2.0 0.0 8.0 11.25 256.0 65536.0 0.5 9.0 1.0
Expected results: 2.0 0.0 8.0 11.25 256.0 65536.0 0.5 9.0 1.0