from linked_list import LinkedList
class Stack(LinkedList):
def push(self, data):
self.append(data)
def peek(self):
return self.tail.data
def pop(self):
ret = self.tail.data
if self.length == 1:
self.tail = self.head = None
else:
self.tail = self.tail.prev
self.tail.next = None
self.length -= 1
return ret
def tokenize(expression):
return expression.split()
print(tokenize("12 2 4 + / 21 *"))
['12', '2', '4', '+', '/', '21', '*']
The functions are all the same, the only thing that changes is the operator used to calculate the result
variable.
It is very important to perform the operation between the elements that was second to to and the top elements. If we do it the other way around we'll get the wrong result.
For example, in the process_minus()
function we do:
result = second_to_top - top # Correct
and not
result = top - second_to_top # Wrong
def process_minus(stack):
top = stack.pop()
second_to_top = stack.pop()
result = second_to_top - top
stack.push(result)
def process_plus(stack):
top = stack.pop()
second_to_top = stack.pop()
# Same as process_minus but with + instead of -
result = second_to_top + top
stack.push(result)
def process_times(stack):
top = stack.pop()
second_to_top = stack.pop()
# Same as process_minus but with * instead of -
result = second_to_top * top
stack.push(result)
def process_divide(stack):
top = stack.pop()
second_to_top = stack.pop()
# Same as process_minus but with / instead of -
result = second_to_top / top
stack.push(result)
def process_pow(stack):
top = stack.pop()
second_to_top = stack.pop()
# Same as process_minus but with ** instead of -
result = second_to_top ** top
stack.push(result)
Here are the steps we need to follow to implement the evaluate_postfix()
function.
tokenize()
function.+
we call the process_plus()
function.float
first.def evaluate_postfix(expression):
tokens = tokenize(expression)
stack = Stack()
for token in tokens:
if token == "+":
process_plus(stack)
elif token == "-":
process_minus(stack)
elif token == "*":
process_times(stack)
elif token == "/":
process_divide(stack)
elif token == "**":
process_pow(stack)
else:
# The token is not an operator so it must be a number
stack.push(float(token))
return stack.pop()
When testing with other expressions we need to add spaces between at two tokens. For example 1 + 3
will work but 1+3
won't.
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:
print(evaluate_postfix(expression))
-2.0 8.0 0.0 2.0 11.25 45.0 42.0 4.0 2.0
The precedence dictionary is used to compare the precedence of two operators.
precedence = {
"+": 1,
"-": 1,
"*": 2,
"/": 2,
"**": 3
}
print(precedence["/"] < precedence["-"])
print(precedence["+"] < precedence["*"])
print(precedence["+"] < precedence["-"])
print(precedence["/"] < precedence["**"])
False True False True
(
:def process_opening_parenthesis(stack):
stack.push("(")
)
:def process_closing_parenthesis(stack, postfix):
# Add tokens until we find the open bracket
while stack.peek() != "(":
postfix.append(stack.pop())
# Remove the opening bracket
stack.pop()
+
, -
, *
, /
or **
:postfix
token list.The Stack.peek()
method will cause an error if the stack is empty. Thus, in the while loop we also need to check that the stack is not empty.
def process_operator(stack, postfix, operator):
while len(stack) > 0 and stack.peek() in precedence and precedence[stack.peek()] >= precedence[operator]:
postfix.append(stack.pop())
stack.push(operator)
def process_number(postfix, number):
postfix.append(number)
tokenize()
function."("
we call the process_opening_parenthesis()
function.")"
we call the process_closing_parenthesis()
function.process_operator()
function.process_number()
function.str.join()
method to convert the postfix token list into a string.def infix_to_postfix(expression):
tokens = tokenize(expression)
stack = Stack()
postfix = []
for token in tokens:
if token == "(":
process_opening_parenthesis(stack)
elif token == ")":
process_closing_parenthesis(stack, postfix)
elif token in precedence:
process_operator(stack, postfix, token)
else:
process_number(postfix, token)
while len(stack) > 0:
postfix.append(stack.pop())
return " ".join(postfix)
def evaluate(expression):
postfix_expression = infix_to_postfix(expression)
return evaluate_postfix(postfix_expression)
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:
print(evaluate(expression))
2.0 0.0 8.0 11.25 256.0 65536.0 0.5 9.0 1.0