CC
BAN USER- 0of 0 votes
AnswersParsing CSV input into a list of tokens. Exception: a comma in double quote is considered inside of a token. Two double quotes inside is considered an escape to one double quote in the token.
- CC in United States
example:
a, b, c ===>
a
b
c
a, "b", c ==>
a
b
c
a, "b, x" , d ==>
a
b,x
d
a, "b, x,""", d ==> 'a' 'b,x"' 'd'
a
b,x,"
d| Report Duplicate | Flag | PURGE
Software Engineer Algorithm
I think you need the stack for mismatch checking. and such method is parsing's standard solution that can be used in other expression parsing problems, and be tested on compiler construction.
Python with stack
#find max paranthesis depth, throw if mismatch
def max_depth(s):
stack = []
depth = 0
max_depth = 0
for c in s:
if c == '(':
stack.append(c)
depth += 1
if depth > max_depth:
max_depth = depth
elif c == ')':
if (len(stack) == 0 or
stack[len(stack)-1] != '('):
raise ValueError("paran mismatch")
else:
stack = stack[:-1] #pop
depth -= 1
return max_depth
Same here. Code in python (parsing could have been done with regular expression instead of this mess)
#interpret string of + and * expression
from collections import deque
def interpret(s):
stack = []
tokens = tokenize(s)
for t in tokens:
stack.append(t)
if stack[len(stack)-2] == '*':
mul_result = stack[len(stack)-1] * stack[len(stack)-3]
stack = stack[:-3] #pop
stack.append(mul_result)
sum = 0
for n in stack:
if n != '+':
sum += n
return sum
def parse_leading_number(s):
number = ''
for i in range(len(s)):
number += (s[i])
if i < len(s)-1 and s[i+1] in '+*':
break
number = int(number)
return number, i #i is pos of the last char
def tokenize(s):
ret = []
if not s:
return []
if s[0] in '+*':
return [s[0]] + tokenize(s[1:])
number, i = parse_leading_number(s)
return [number] + tokenize(s[i+1:])
#test
print interpret('1+2*4')
Recursive solution, python. since n can be of any value, you wanna also check for non positive integer.
For each node, this function returns a 3-tuple. (outcome_value, node_count_from_the_end, whether_the_job_is_done.)
So if the call to next node returns done, then the value is done and we return the result.
Otherwise, check to see if this node is the node we want by checking the node count from the end. increment count if not done.
#nth from last node of linkedlist
class Node(object):
def __init__(self, data, next):
self.data = data
self.next = next
def nth_from_last(head, n):
(value, count, done ) = nth_from_last_aux(head, n)
if not done:
return None
else:
return value
def nth_from_last_aux(head, n):
if not head:
return None
if not head.next: #last node
if n == 1:
return (head.data, None, True)
else:
return (None, 1, False)
(value, count, done) = nth_from_last(head.next, n)
if done:
return (value, count, True)
elif count+1 == n:
return (head.data, count, True)
else:
return (value, count+1, False)
#test
h = Node(1, Node(2, Node(3, Node(4, None))))
print nth_from_last(h, 2)
So sorry, didn't read the question correctly. Without copying the string, here's my solution using iterative pointers in python.
#check palindrome skip non-alpha-numerical
def special_palindrome(s):
idx1 = 0
idx2 = len(s)-1
while idx1 < idx2:
if not (s[idx1].isalpha() or s[idx1].isdigit()):
idx1 += 1
continue
if not (s[idx2].isalpha() or s[idx2].isdigit()):
idx2 -= 1
continue
if not s[idx1]==s[idx2]:
return False
else:
idx1 += 1
idx2 -= 1
return True
Trivial is to clean up the string before checking whether the cleaned string is palindrome
python:
#check palindrome skip non-alpha-numerical
def special_palindrome(s):
ret = True
cleaned = ''
for i in range(len(s)):
if s[i].isalpha() or s[i].isdigit():
cleaned += s[i]
return palindrome(cleaned)
def palindrome(s):
for i in range(len(s)/2):
if s[i] != s[len(s)-i-1]:
return False
return True
Python recursive to find all possible combinations.
def split_words(s, words):
ret = []
phrases = split_words_aux(s, words)
for p in phrases:
ret.append(' '.join(p))
return ret
def split_words_aux(s, words):
ret = []
if not s:
return []
for w in words:
if w == s:
return [[w]]
if len(w) <= len(s) and s[:len(w)] == w:
sub_str_matches = split_words_aux(s[len(w):], words)
for match in sub_str_matches:
ret.append([w] + match)
return ret
The idea is, add this new range to the first element of the entire list of ranges, then use a while loop to update this set of ranges until stable - meaning the size of this list of ranges no longer changes.
Keeping the newly constructed range always in the first element, for each iteration, try to merge with the rest of the element and see if there's a successful merge, and update the list or ranges while keeping the merged range in the first element of this list.
in Python,
- CC February 26, 2015