Source code for pygorithm.data_structures.stack

"""
Author: OMKAR PATHAK
Created On: 3rd August 2017
"""
from string import ascii_letters
import inspect


[docs]class Stack(object): """ Stack object """ def __init__(self, limit=10): """ :param limit: the stack size """ self.stack = [] self.limit = limit def __str__(self): return ' '.join([str(i) for i in self.stack])
[docs] def push(self, data): """ pushes an item into the stack returns -1 if the stack is empty """ if len(self.stack) >= self.limit: # indicates stack overflow return -1 else: self.stack.append(data)
[docs] def pop(self): """ pops the topmost item from the stack returns -1 if the stack is empty """ if len(self.stack) <= 0: # indicates stack underflow return -1 else: return self.stack.pop()
[docs] def peek(self): """ returns the topmost element of the stack returns -1 if the stack is empty """ if len(self.stack) <= 0: # stack underflow return -1 else: return self.stack[len(self.stack) - 1]
[docs] def is_empty(self): """ checks if the stack is empty returns boolean value, True or False """ return self.size() == 0
[docs] def size(self): """ returns the current size of the stack """ return len(self.stack)
[docs] @staticmethod def get_code(): """ returns the code for current class """ return inspect.getsource(Stack)
[docs]class InfixToPostfix(object): """InfixToPostfix get the postfix of the given infix expression """ def __init__(self, expression=None, stack=None): """ :param expression: the infix expression to be converted to postfix :param stack: stack to perform infix to postfix operation """ self.expression = list(expression) self.my_stack = stack @staticmethod def _is_operand(char): """ utility function to find whether the given character is an operator """ # OLD VERSION # return ord(char) >= ord('a') and ord(char) <= ord('z') \ # or ord(char) >= ord('A') and ord(char) <= ord('Z') return True if ord(char) in [ord(c) for c in ascii_letters] else False @staticmethod def _precedence(char): """ utility function to find precedence of the specified character """ if char == '+' or char == '-': return 1 elif char == '*' or char == '/': return 2 elif char == '^': return 3 else: return -1
[docs] def infix_to_postfix(self): """ function to generate postfix expression from infix expression """ postfix = [] for i in range(len(self.expression)): if self._is_operand(self.expression[i]): postfix.append(self.expression[i]) elif self.expression[i] == '(': self.my_stack.push(self.expression[i]) elif self.expression[i] == ')': top_operator = self.my_stack.pop() while not self.my_stack.is_empty() and top_operator != '(': postfix.append(top_operator) top_operator = self.my_stack.pop() else: while not self.my_stack.is_empty() and self._precedence(self.expression[i]) <= self._precedence( self.my_stack.peek()): postfix.append(self.my_stack.pop()) self.my_stack.push(self.expression[i]) while not self.my_stack.is_empty(): postfix.append(self.my_stack.pop()) return ' '.join(postfix)
[docs] @staticmethod def get_code(): """ returns the code of the current class """ return inspect.getsource(InfixToPostfix)