Python does not have native structures for stack or queue, which could otherwise be manually implemented if needed. However, list in Python is an easy alternative as stack or queue. Stack and queue share the same method
append(), while stack uses pop() and queue applies pop(0) distinctively.1. Valid Parentheses
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
This question executes the principle of
try-match-else-insert. Since the question only needs to return True/False, the logic is pretty straightforward.# -*- coding: utf-8 -*-
def isValid(s):
a = []
for x in s:
if len(a) == 0:
a.append(x)
# Locate the three corret cases
elif ( x == ']' and a[-1] == '[' ) or ( x == '}' and a[-1] == '{' ) or ( x == ')' and a[-1] == '(' ):
a.pop()
else:
a.append(x)
if len(a) != 0:
return False
return True
if __name__ == "__main__":
testcase1 = '['
testcase2 = '(('
testcase3 = '([)]'
testcase4 = '()[]{}'
testcase5 = '([])'
for i in range(1, 6):
print isValid(eval('testcase' + str(i)))
2. Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.For “(()”, the longest valid parentheses substring is “()”, which has length = 2.Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.
This question is the difficult version of the question above, since it asks the maximum length of valid parentheses. This time the objected to be inserted is the index of the character instead of the character itself.
# -*- coding: utf-8 -*-
def LVP2(a):
if len(a) == 0 or a == None:
return 0
last = -1
maxLen = 0
b = [] # use a buffer list as stack
for i in xrange(len(a)):
if a[i] == '(':
b.append(i)
else:
# If buffer is empty
if not b:
# Record the position before first left parenthesis
last = i
else:
b.pop()
# If buffer is empty again
if not b:
maxLen = max(i-last, maxLen)
else:
# Select the top element from the buffer
maxLen = max(i-b[-1], maxLen)
return maxLen
if __name__ == "__main__":
testcase1 = ")()())"
testcase2 = '()()()()()))))))(((((('
testcase3 = "()(()))"
testcase4 = "()(()"
testcase5 = "))))((()(("
for i in range(1, 6):
print LVP2(eval("testcase" + str(i)))
3. Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.Some examples:
[“2”, “1”, “+”, “3”, ““] -> ((2 + 1) 3) -> 9
[“4”, “13”, “5”, “/“, “+”] -> (4 + (13 / 5)) -> 6
This question implements the principle of
try-number-else-calcultate. The tricky part is that the stack will have to pop the elements twice.# -*- coding: utf-8 -*-
def polish(s):
stack = []
for x in s:
# Use the int() function to make decision instead of isdigit()
try:
stack.append(int(x))
except:
# Still want to floating operation
e2 = float(stack.pop()) # the first pop-out is the second number
e1 = float(stack.pop())
if x == '+':
result = e1 + e2
elif x == '-':
result = e1 - e2
elif x == '*':
result = e1 * e2
elif x == '/':
if e2 == 0:
raise ValueError("No zero for denominator")
result = e1 / e2
else:
raise ValueError("Incorrect operator")
stack.append(int(result))
return stack[0] # transform single element list to number
if __name__ == "__main__":
testcase1 = ["2", "1", "+", "3", "*"]
testcase2 = ["4", "13", "5", "/", "+"]
testcase3 = ["3", "-4", "+"]
testcase4 = ["18"]
testcase5 = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
for i in range(1, 6):
print polish(eval('testcase' + str(i)))