Created
November 3, 2012 04:17
-
-
Save ruli/4005861 to your computer and use it in GitHub Desktop.
Stack Application
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python | |
# -*- coding: utf-8 -*- | |
class Stack(object): | |
def __init__(self): | |
self.items = [] | |
def isEmpty(self): | |
return not self.items | |
def push(self, item): | |
self.items.append(item) | |
def pop(self): | |
if self.isEmpty(): | |
raise IndexError('pop from empty stack') | |
return self.items.pop() | |
def peek(self): | |
if self.isEmpty(): | |
raise IndexError('peek from empty stack') | |
return self.items[self.size() - 1] | |
def size(self): | |
return len(self.items) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python | |
# -*- coding: utf-8 -*- | |
from stack import Stack | |
def eval_postfix(postfix_str): | |
operands = Stack() | |
for char in postfix_str: | |
if char.isspace(): | |
continue | |
elif char.isdigit(): | |
operands.push(int(char)) | |
elif char in "^*/+-": | |
second = operands.pop() | |
first = operands.pop() | |
result = None | |
if char == "^": | |
result = first ** second | |
elif char == "*": | |
result = first * second | |
elif char == "/": | |
result = first / second | |
elif char == "+": | |
result = first + second | |
else: | |
result = first - second | |
operands.push(result) | |
return operands.pop() | |
def infix2postfix(infix_str): | |
prec = {} | |
prec["^"] = 4 # highest precedence | |
prec["*"] = 3 | |
prec["/"] = 3 | |
prec["+"] = 2 | |
prec["-"] = 2 | |
prec["("] = 1 | |
ops = Stack() | |
postfix_list = [] | |
for char in infix_str: | |
if char.isspace(): | |
continue | |
elif char in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or char in "0123456789": | |
postfix_list.append(char) | |
elif char == '(': | |
ops.push(char) | |
elif char == ')': | |
top = ops.pop() | |
while top != '(': | |
postfix_list.append(top) | |
top = ops.pop() | |
else: | |
while (not ops.isEmpty()) and (prec[ops.peek()] >= prec[char]): | |
postfix_list.append(ops.pop()) | |
ops.push(char) | |
while not ops.isEmpty(): | |
postfix_list.append(ops.pop()) | |
return " ".join(postfix_list) | |
def dec2base(decimal, base): | |
digits = "0123456789ABCDEF" # up to hex | |
s = Stack() | |
while decimal > 0: | |
s.push(decimal % base) | |
decimal //= base | |
bin_str = "" | |
while not s.isEmpty(): | |
bin_str += digits[s.pop()] | |
return bin_str | |
def par_checker_stack(par_str): | |
s = Stack() | |
for par in par_str: | |
if par in "([{": | |
s.push(par) # Push in the opening bracket | |
continue | |
if par in ")]}": | |
if s.isEmpty(): | |
return False # Can't match, false | |
opening = s.pop() | |
if not par_match(opening, par): # uses a helper function to match indeces | |
return False | |
return s.isEmpty() | |
def par_match(opening, closing): | |
opens = "([{" | |
closes = ")]}" | |
return opens.index(opening) == closes.index(closing) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Some quite practical data structure/algo practices/examples found from the book "Problem Solving with Algorithms and Data Structures Using Python" By Brad Miller and David Ranum, Luther College. Did minor improvements and little problem fixes. Could be useful for future reference and review purposes.