forked from OmkarPathak/pygorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathstack.py
More file actions
145 lines (127 loc) · 3.96 KB
/
stack.py
File metadata and controls
145 lines (127 loc) · 3.96 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
"""
Author: OMKAR PATHAK
Created On: 3rd August 2017
"""
from string import ascii_letters
import inspect
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])
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)
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()
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]
def is_empty(self):
"""
checks if the stack is empty
returns boolean value, True or False
"""
return self.size() == 0
def size(self):
"""
returns the current size of the stack
"""
return len(self.stack)
@staticmethod
def get_code():
"""
returns the code for current class
"""
return inspect.getsource(Stack)
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
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)
@staticmethod
def get_code():
"""
returns the code of the current class
"""
return inspect.getsource(InfixToPostfix)