Google Interview Question Software Engineer Interns
Interview Type: Phone Interview
static ArrayList<String> getStrings(String input){
if(input == null){
return null;
}
String regExp = "[(][a-z]+,[a-z]+[)][a-z]*";
Pattern pattern = Pattern.compile(regExp);
Matcher matcher = pattern.matcher(input);
ArrayList<String> result = new ArrayList<String>();
result.add(input);
while(matcher.find()){
result = getCombination(matcher.group(), result);
}
return result;
}
static ArrayList<String> getCombination(String target, ArrayList<String> result){
int startPosition = target.indexOf('(');
int endPosition = target.indexOf(')');
String prefix = target.substring(startPosition+1, endPosition);
String[] preChs = prefix.split(",");
String postfix = target.substring(endPosition+1, target.length());
for(int i = 0; i<preChs.length; i++){
preChs[i] = preChs[i]+postfix;
}
ArrayList<String> temp = new ArrayList<String>();
for(String input : result){
for(int i = 0; i<preChs.length; i++){
String word = preChs[i];
word = input.replace(target, word);
temp.addAll(getStrings(word));
Set<String> items = new LinkedHashSet<String>(temp);
temp.clear();
temp.addAll(items);
}
}
result = temp;
return result;
}
import java.util.Stack;
public class BashBrace {
public static void main(String[] args) {
String expr = "a,((a,b)o(m,n)p),b(a,c)";
System.out.println(bashBrace(expr));
}
public static String bashBrace(String expr) {
Stack<String> stack = new Stack<String>();
String finalStr = "";
String str1 = "";
int index = 0;
for (int i = 0; i < expr.length();) {
char ch = expr.charAt(i++);
if (ch == ',') {
if (!"".equals(finalStr)) {
finalStr = finalStr + ",";
}
finalStr = finalStr + multiply(str1, expr.substring(index, i - 1));
str1 = "";
index = i;
}
if (ch == '(') {
StringBuffer buffer = new StringBuffer();
i = evaluate(buffer, multiply(str1, expr.substring(index, i - 1)), expr, i);
str1 = buffer.toString();
index = i;
}
}
if (!"".equals(finalStr)) {
finalStr = finalStr + ",";
}
finalStr = finalStr + multiply(str1, expr.substring(index, expr.length()));
return finalStr.replaceAll(",", "\n");
}
private static int evaluate(StringBuffer buffer, String str, String expr, int i) {
int index = i;
for (; i < expr.length();) {
char ch = expr.charAt(i++);
if (ch == ')') {
buffer.append(multiply(str, expr.substring(index, i - 1)));
break;
}
if (ch == '(') {
StringBuffer buffer1 = new StringBuffer();
i = evaluate(buffer1, multiply(str, expr.substring(index, i - 1)), expr, i);
str = buffer1.toString();
index = i;
}
}
return i;
}
private static String multiply(String str1, String str2) {
String str1Arr[] = str1.split(",");
String str2Arr[] = str2.split(",");
String str = "";
for (int i = 0; i < str1Arr.length; i++) {
for (int j = 0; j < str2Arr.length; j++) {
if (!"".equals(str)) {
str = str + ",";
}
str = str + str1Arr[i] + str2Arr[j];
}
}
return str;
}
}
Not pretty, but works. Recursive. I hope someone posts a more elegant solution.
#!/usr/bin/env python
class BashParser(object):
def parse(self, string):
bigParts = self.separateHighCommas(string)
retList = list()
for bigPart in bigParts:
retList.extend(self.parsePart(bigPart))
return retList
def separateHighCommas(self, string):
index = 0
iStart = 0
pCount = 0
tokenList = list()
while index < len(string):
if string[index] == '(': pCount += 1
if string[index] == ')': pCount -= 1
if string[index] == ',' and pCount == 0:
tokenList.append(string[iStart:index])
iStart = index + 1
index += 1
if len(string) - iStart > 0:
tokenList.append(string[iStart:])
return tokenList
def parsePart(self, string):
tokens = self.separateTokens(string)
if len(tokens) == 1 and tokens[0] == string:
return tokens[0]
else:
return self.comb(*map(self.parse, tokens))
def separateTokens(self, string):
index = 0
iStart = 0
pCount = 0
tokenList = list()
while index < len(string):
if string[index] == '(':
if pCount == 0 and index - iStart > 0:
tokenList.append(string[iStart:index])
iStart = index
pCount += 1
if string[index] == ')':
pCount -= 1
if pCount == 0:
tokenList.append(string[iStart+1:index])
iStart = index + 1
index += 1
if iStart < index:
tokenList.append(string[iStart:])
return tokenList
def comb(self, *lists):
index = 0
frontier = ['']
while index < len(lists):
next = list()
for string in frontier:
for elem in lists[index]:
next.append(string + elem)
index += 1
frontier = next
return frontier
def main():
print 'Woohoo! :)'
bp = BashParser()
print bp.parse('a(b(c,d),a(p,q))')
if __name__ == '__main__':
main()
Yes, recursive seems to be the way to go.
std::vector<std::string>
parse_bash(const std::string& s, int& p) {
std::vector<std::string> parsed;
std::vector<std::string> res;
res.push_back("");
while (p < s.length()) {
if (s[p] == '(') {
p++;
std::vector<std::string> substrings = parse_bash(s, p);
std::vector<std::string> newres;
for (std::string ss : substrings) {
for (std::string r : res) {
newres.push_back(r + ss);
}
}
res = newres;
} else if (s[p] == ',') {
parsed.insert(parsed.end(), res.begin(), res.end());
res.clear();
res.push_back("");
p++;
} else if (s[p] == ')') {
p++;
parsed.insert(parsed.end(), res.begin(), res.end());
return parsed;
} else {
for (int i = 0; i < res.size(); ++i) {
res[i] += s[p];
}
p++;
}
}
parsed.insert(parsed.end(), res.begin(), res.end());
return parsed;
}
int
main(int argc, char* argv[]) {
if (argc > 1) {
std::cout << argv[1] << std::endl;
int p = 0;
std::vector<std::string> res = parse_bash(argv[1], p);
for (std::string s : res) {
std::cout << s << std::endl;
}
}
return 0;
}
Here is my code:
//input="(a,b,cy)n,m"
public ArrayList<String> GetCombination(String input)
{
int startPosition = input.indexOf('(');
int endPosition = input.indexOf(')');
String prefix = input.substring(startPosition+1, endPosition);
String[] preChs = prefix.split(",");
String postfix = input.substring(endPosition+1, target.length());
String postChs=postfix.split(",");
ArrayList<String> result = new ArrayList<String>();
String temp="";
for (int i = 0; i<preChs.length; i++)
{
for (int j = 0; j<postChs.length; j++)
{
temp=preChs[i]+ postChs[j];
result.add(temp);
}
}
return result;
}
import unittest
def multiply(buffer, elements):
if len(buffer) == 0:
return elements
return [item+element for item in buffer for element in elements]
def get_nested_expr(expr):
paren_cnt = 1
i = 0
while paren_cnt > 0:
i += 1
if expr[i] == '(':
paren_cnt += 1
if expr[i] == ')':
paren_cnt -= 1
return expr[:i]
def nest(expr):
ret = []
buffer = []
i = 0
while i < len(expr):
if expr[i] == ',':
ret += buffer
buffer = []
i += 1
elif expr[i] == '(':
nested_expr_str = get_nested_expr(expr[i + 1:])
i += 2 + len(nested_expr_str)
nested_expr = nest(nested_expr_str)
buffer = multiply(buffer, nested_expr)
else:
buffer = multiply(buffer, [expr[i]])
i += 1
ret += buffer
return ret
class MyTestCase(unittest.TestCase):
def test_get_nested_expr(self):
expr = 'a,s,d)ert'
ret = get_nested_expr(expr)
self.assertEqual('a,s,d', ret)
def test_multiply(self):
actual = multiply([], ['a'])
self.assertEqual(['a'], actual)
def test_multiply__non_empty_buffer(self):
actual = multiply(['a'], ['b'])
self.assertEqual(['ab'], actual)
def test_multiply__buffer(self):
actual = multiply(['a', 'b'], ['c'])
self.assertEqual(['ac', 'bc'], actual)
def test_multiply__two_buffers(self):
actual = multiply(['a', 'b'], ['c', 'd'])
#print(actual)
self.assertEqual(['ac', 'ad', 'bc', 'bd'], actual)
def test_nest(self):
expr = 'a,b,c'
expected = ['a', 'b', 'c']
actual = nest(expr)
self.assertEqual(expected, actual)
def test_nest__multiple_letters(self):
expr = 'a12,b345,c'
expected = ['a12', 'b345', 'c']
actual = nest(expr)
self.assertEqual(expected, actual)
def test_nested(self):
expr = 'a(b,c)'
expected = ['ab', 'ac']
actual = nest(expr)
#print(actual)
self.assertEqual(expected, actual)
def test_nested__two_expr(self):
expr = 'a(b,c)d,(e,f)g'
expected = ['abd', 'acd', 'eg', 'fg']
actual = nest(expr)
#print(actual)
self.assertEqual(expected, actual)
def test_nested__two_levels(self):
expr = 'a(b(c1,c2,c3))d,(e,f)g'
expected = ['abc1d', 'abc2d', 'abc3d', 'eg', 'fg']
actual = nest(expr)
print(actual)
self.assertEqual(expected, actual)
My solution :-
public List<String> doBashExpansion(List<String> input) {
List<String> prefixCombi = new ArrayList<>();
String midChar = "";
String lastChar = "";
for (String toProcess : input) {
List<String> combi = null;
String[] chs = toProcess.split(",");
List<String> prefix = new ArrayList<>();
for (String ch : chs) {
if (ch.contains(")")) {
int index = ch.indexOf(')');
prefix.add(ch.substring(0, index));
midChar = ch.substring(index + 1, ch.length());
} else if (ch.startsWith("(")) {
prefix.add(ch.replace('(', (char) 0));
} else{
lastChar = ch;
}
}
combi = populateCombination(prefix, midChar);
prefixCombi.addAll(combi);
}
List<String> finalParsing = doFinalParsing(prefixCombi);
finalParsing.add(lastChar);
finalParsing.remove(",");
return finalParsing;
}
private List<String> doFinalParsing(List<String> prefixCombi) {
int indexForSplit = prefixCombi.indexOf(",");
List<String> output = new ArrayList<String>();
List<String> first = prefixCombi.subList(0, indexForSplit);
List<String> last = prefixCombi.subList(indexForSplit,
prefixCombi.size());
for (String postFix : last) {
if (postFix.equals(",")) {
continue;
}
output.addAll(populateCombination(first, postFix));
}
output.remove(",");
return output;
}
private List<String> populateCombination(List<String> prefix, String mid) {
List<String> prefixCombo = new ArrayList<>();
for (String pre : prefix) {
pre = pre + mid;
prefixCombo.add(pre);
}
prefixCombo.add(",");
return prefixCombo;
}
/**
* @param args
*/
public static void main(String[] args) {
Question1 ans = new Question1();
String regExp = "[(][a-z]+,[a-z]+[)][a-z,]*";
Pattern pattern = Pattern.compile(regExp);
Matcher matcher = pattern.matcher(args[0]);
List<String> input = new ArrayList<>();
while (matcher.find()) {
input.add(matcher.group());
}
System.out.println(ans.doBashExpansion(input));
}
/*
syntax:
exp = term | exp,term
term = prim|term prim
prim = name | (exp)
name = {a|b|c|...|z}
*/
vector<string> product(const vector<string>& arr1, const vector<string>& arr2)
{
vector<string> res;
if(!arr1.size()) return arr2;
if(!arr2.size()) return arr1;
for (string s1 : arr1) {
for (string s2 : arr2) {
res.push_back(s1+s2);
}
}
return res;
}
vector<string> Expression(string& input, size_t& pos);
vector<string> prim(string& input, size_t& pos)
{
vector<string> _arr;
if(input[pos] == '(')
{
pos++;// skip'('
_arr = Expression(input, pos);
pos++;// skip ')' or the letter
}
else
{
size_t start = pos;
while(isalnum(input[pos])){
pos++;
}
_arr.push_back(input.substr(start, pos - start));
}
return _arr;
}
vector<string> term(string& input, size_t& pos)
{
vector<string> res = prim(input, pos);
while(
(pos < input.length()) &&
((input[pos] == '(') || isalnum(input[pos]))
)
{
vector<string> _arr = prim(input, pos);
res = product(res, _arr);
}
return res;
}
vector<string> Expression(string& input, size_t& pos)
{
vector<string> res = term(input, pos);
while(pos < input.length() && (input[pos]) == ',')
{
pos++;
vector<string> _arr = term(input, pos);
for( string s : _arr) {
res.push_back(s);
}
}
return res;
}
int _tmain(int argc, _TCHAR* argv[])
{
size_t pos = 0;
string input; // = string((char*)argv[1]);
cin >> input;
vector<string> res = Expression(input, pos);
for(string s : res) {
cout << s << endl;
}
return 0;
}
Sample Input:
((a,b)c , d(e,f) , (g,h)i(j,k), (l,m)(o,p), q(r,(s,(t,u))), v((w, x), (y, z)), (4, 5)6(7, (8,9)))
public static void main(String[] args) {
Item item = calBashExpresion("((a,b)c , d(e,f) , (g,h)i(j,k), (l,m)(o,p), q(r,(s,(t,u))), v((w, x), (y, z)), (4, 5)6(7, (8,9)))");
printItem(item);
}
static class Item {
String self = null;
List<Item> child = new ArrayList<Main.Item>();
}
static void printItem(Item item) {
if (item.child == null || item.child.isEmpty()) {
System.out.println(item.self);
return;
}
for (Item i : item.child) {
printItem(i);
}
}
static int index = 0;
static Item calBashExpresion(String input) {
Item curr = new Item();
Item list = null;
Stack<Item> itemStack = new Stack<Main.Item>();
StringBuilder sb = new StringBuilder();
for (; index < input.length(); index++) {
final char ch = input.charAt(index);
switch (ch) {
case '(':
if (list != null) {
itemStack.add(list);
}
++index;
list = calBashExpresion(input);
if (sb.length() != 0) {
list.child = multiple(sb.toString(), list.child);
sb = new StringBuilder();
}
while (!itemStack.isEmpty()) {
list.child = multiple(itemStack.pop().child, list.child);
}
break;
case ',':
case ')':
if (sb.length() != 0 && list != null) {
list.child = multiple(sb.toString(), list.child);
sb = new StringBuilder();
}
if (sb.length() != 0) {
Item n = new Item();
n.self = sb.toString();
curr.child.add(n);
sb = new StringBuilder();
} else if (list != null) {
curr.child.add(list);
list = null;
}
if (ch == ')') {
return curr;
}
break;
case ' ':
break;
default:
sb.append(ch);
break;
}
}
curr.child.add(list);
return curr;
}
static List<Item> multiple(String str, List<Item> list) {
List<Item> res = new ArrayList<Main.Item>();
for (ListIterator<Item> s = list.listIterator(); s.hasNext();) {
Item i = new Item();
Item next = s.next();
if (next.self == null) {
i.child = multiple(str, next.child);
} else {
i.self = str + next.self;
}
res.add(i);
}
return res;
}
static List<Item> multiple(List<Item> first, List<Item> second) {
List<Item> res = new ArrayList<Main.Item>();
for (Item f : first) {
for (Item s : second) {
Item i = new Item();
if (f.self == null && s.self == null) {
i.child = multiple(f.child, s.child);
} else if (f.self == null) {
i.child = multiple(s.self, f.child);
} else if (s.self == null) {
i.child = multiple(f.self, s.child);
} else {
System.out.println("4");
}
res.add(i);
}
}
return res;
}
for first three sample inputs, it just took about 30 mins. However, I came up with some complicated inputs as last three later, it took about two hours.
it seems to be similar to one posted earlier and less than 10 mins modification on above logic will handle below question as well.
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148
// in main, the func can be called like this:
// int[] index = new int[1];
// List<String> res = parse(myStr, index);
public List<String> parse(String s, int[] index) {
if (s == null || s.length() == 0)
return new ArrayList<String>();
List<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
List<String> cur = null;
List<String> next = null;
while (index[0] < s.length()) {
char ele = s.charAt(index[0]);
if (ele == '(' || ele == ')' || ele == ',') {
if (cur == null)
cur = new ArrayList<String>();
if (sb.length() != 0) {
cur = append(cur, sb.toString(), false);
sb.setLength(0);
}
if (ele == '(') {
index[0]++;
next = parse(s, index);
cur = append(cur, next, false);
}
if (ele == ')') {
res = append(res, cur, true);
return res;
}
if (ele == ',') {
res = append(res, cur, true);
cur = null;
}
} else {
if (ele != ' ')
sb.append(String.valueOf(ele));
}
index[0]++;
}
if (sb.length() != 0) {
res = append(res, sb.toString(), true);
sb.setLength(0);
} else {
if (cur != null)
res = append(res, cur, true);
}
return res;
}
public List<String> append(List<String> origin, String tail,
boolean isAppend) {
List<String> tails = new ArrayList<String>();
tails.add(tail);
return append(origin, tails, isAppend);
}
public List<String> append(List<String> origin, List<String> tail,
boolean isAppend) {
if (isAppend)
origin.addAll(tail);
else {
int len = origin.size();
if (len == 0)
return tail;
for (int i = 0; i < len; i++) {
for (int j = 0; j < tail.size(); j++)
origin.add(origin.get(i) + tail.get(j));
}
origin = origin.subList(len, origin.size());
}
return origin;
}
Not doable (by me) within the requested time period :
#include <stdio.h>
#include <string.h>
static
void split(char *str, int n, char *out, int o, int depth)
{
int i, cnt = depth;
if (!n) {
printf("%.*s\n", o, out);
return;
}
if (depth == -1) {
for (i = 0; i < n; i++) {
split(str + i, n - i, out, o, 0);
for (; i < n; i++) {
if (cnt == depth && (str[i] == ','))
break;
cnt += (str[i] == '(') - (str[i] == ')');
}
}
return;
}
if (str[0] == '(') {
for (i = 1, cnt = ++depth;; i++) {
split(str + i, n - i, out, o, depth);
for (; i < n; i++) {
if (cnt == depth && (str[i] == ')' || str[i] == ','))
break; /* found */
cnt += (str[i] == '(') - (str[i] == ')');
}
if (str[i] == ')')
break;
}
} else if (str[0] == ')') {
split(str + 1, n - 1, out, o, depth - 1);
} else if (str[0] == ',') {
for (i = 1; i < n; i++) {
if (cnt == depth && str[i] == ')')
break; /* found next step */
cnt += (str[i] == '(') - (str[i] == ')');
}
split(str + i, n - i, out, o, depth);
} else {
for (i = 0; i < n; i++) {
if (str[i] == ',' || str[i] == '(' || str[i] == ')')
break;
out[o++] = str[i];
}
split(str + i, n - i, out, o, depth);
}
}
int main(void)
{
int i;
char *txt, out[50], *str[] = {"a,(b,cy)n,m", "((a,b(,aze))o(m,n)p,b)"};
for (i = 0; i < 2; i++) {
txt = str[i];
printf("%s:\n", txt);
split(txt, strlen(txt), out, 0, -1);
}
return 0;
}
pseudo code:
void parse(position)
{
while(position<input.length())
{
switch(input[position])
{
case '(':
parse(position+1);
parse(getNextAlternativeChar(position+1));
return;
case ')':
position(getNextCharPositionAfterCurrentBrace(position));
brake;
case ',':
position(getNextCharPositionAfterCurrentBrace(position));
brake;
default:
position+=1;
brake;
}
}
}
void main()
{
parse(0);
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BashBrace {
public static void main(String[] args) {
BashBrace bb = new BashBrace();
bb.parse("(a,b,cy)n,m");
// bb.parse("(a,b)o(m,n)p,b");
}
private void parse(String str) {
Queue<String> elements = new LinkedList<String>();
int index = 0;
while(index < (str.length())){
String token = nextToken(str, index);
elements.add(token);
index += token.length();
}
handle(elements);
}
private void handle(Queue<String> elements) {
Stack<StringBuilder> group = buildGroup(elements);
for(StringBuilder sb: group){
System.out.println(sb);
}
}
private Stack<StringBuilder> buildGroup(Queue<String> elements) {
Stack<StringBuilder> group = new Stack<StringBuilder>();
group.add(new StringBuilder());
while (!elements.isEmpty()) {
String ch = elements.poll();
if (ch.equalsIgnoreCase("(")) {
group = merge(group, buildGroup(elements));
} else if (ch.equalsIgnoreCase(")")) {
return group;
} else if (ch.equalsIgnoreCase(",")) {
if (!elements.peek().equalsIgnoreCase("(")) {
String symbol = elements.poll();
StringBuilder sb = new StringBuilder();
sb.append(symbol);
group.add(sb);
}
} else {
merge(ch, group);
}
}
return group;
}
private Stack<StringBuilder> merge(Stack<StringBuilder> first, Stack<StringBuilder> second) {
Stack<StringBuilder> mergedGroup = new Stack<StringBuilder>();
for (StringBuilder firstStr : first) {
for (StringBuilder secondStr : second) {
mergedGroup.add(new StringBuilder(firstStr.toString() + secondStr.toString()));
}
}
return mergedGroup;
}
private Stack<StringBuilder> merge(String ch, Stack<StringBuilder> group) {
for (StringBuilder groupStr : group) {
groupStr.append(ch);
}
return group;
}
private String nextToken(String str, int curIndex) {
int nextInd = getFirstSeparatorIndex(str, curIndex);
if (nextInd == curIndex){
nextInd++;
}
return str.substring(curIndex, nextInd );
}
private int getFirstSeparatorIndex(String str, int fromIndex){
int firstLeftBracket = str.indexOf('(', fromIndex);
if(firstLeftBracket < 0){
firstLeftBracket = str.length();
}
int firstRightBracket = str.indexOf(')', fromIndex);
if(firstRightBracket < 0){
firstRightBracket = str.length();
}
int firstComma = str.indexOf(',', fromIndex);
if(firstComma < 0){
firstComma = str.length();
}
return less(firstLeftBracket, less(firstRightBracket, firstComma));
}
private int less(int first, int second){
if(first < second){
return first;
}
return second;
}
}
This is my solution in python
def getSubExprList(expr):
braceCount = 0
nextToken = ""
subExprList = []
for c in expr:
if c in "(":
braceCount += 1
nextToken += c
elif c in ")":
braceCount -= 1
nextToken += c
elif c in ",":
if braceCount is 0:
subExprList.append(nextToken)
nextToken = ""
else:
nextToken += c
else:
nextToken += c
if nextToken is not "":
subExprList.append(nextToken)
return subExprList
def multiplyExpr(first, second):
if len(first) is 0:
return second
if len(second) is 0:
return first
return [x+y for x in first for y in second]
def evalExpr(expr):
currSection = ""
bracesCount = 0
for c in expr:
if c in "(":
if bracesCount is not 0:
currSection += c
elif currSection is not "":
return multiplyExpr(expandExpr(currSection), expandExpr(expr[len(currSection):]))
bracesCount += 1
elif c in ")":
bracesCount -= 1
if bracesCount is 0:
return multiplyExpr(expandExpr(currSection), expandExpr(expr[len(currSection)+2:]))
currSection += c
else:
currSection += c
return currSection
def expandExpr(expr):
toReturnList = []
for val in getSubExprList(expr):
valExpr = evalExpr(val)
if isinstance(valExpr, list):
toReturnList += valExpr
else:
toReturnList.append(valExpr)
return toReturnList
print expandExpr("")
print expandExpr("((a,b)o(m,n)p,b),(a,b,cy)n,m")
This is my solution in python
def getSubExprList(expr):
braceCount = 0
nextToken = ""
subExprList = []
for c in expr:
if c in "(":
braceCount += 1
nextToken += c
elif c in ")":
braceCount -= 1
nextToken += c
elif c in ",":
if braceCount is 0:
subExprList.append(nextToken)
nextToken = ""
else:
nextToken += c
else:
nextToken += c
if nextToken is not "":
subExprList.append(nextToken)
return subExprList
def multiplyExpr(first, second):
if len(first) is 0:
return second
if len(second) is 0:
return first
return [x+y for x in first for y in second]
def evalExpr(expr):
currSection = ""
bracesCount = 0
for c in expr:
if c in "(":
if bracesCount is not 0:
currSection += c
elif currSection is not "":
return multiplyExpr(expandExpr(currSection), expandExpr(expr[len(currSection):]))
bracesCount += 1
elif c in ")":
bracesCount -= 1
if bracesCount is 0:
return multiplyExpr(expandExpr(currSection), expandExpr(expr[len(currSection)+2:]))
currSection += c
else:
currSection += c
return currSection
def expandExpr(expr):
toReturnList = []
for val in getSubExprList(expr):
valExpr = evalExpr(val)
if isinstance(valExpr, list):
toReturnList += valExpr
else:
toReturnList.append(valExpr)
return toReturnList
print expandExpr("")
print expandExpr("((a,b)o(m,n)p,b),(a,b,cy)n,m")
import java.util.Stack;
public class BashBrace {
public static void main(String[] args) {
String expr = "a,((a,b)o(m,n)p),b(a,c)";
System.out.println(bashBrace(expr));
}
public static String bashBrace(String expr) {
Stack<String> stack = new Stack<String>();
String finalStr = "";
String str1 = "";
int index = 0;
for (int i = 0; i < expr.length();) {
char ch = expr.charAt(i++);
if (ch == ',') {
if (!"".equals(finalStr)) {
finalStr = finalStr + ",";
}
finalStr = finalStr + multiply(str1, expr.substring(index, i - 1));
str1 = "";
index = i;
}
if (ch == '(') {
StringBuffer buffer = new StringBuffer();
i = evaluate(buffer, multiply(str1, expr.substring(index, i - 1)), expr, i);
str1 = buffer.toString();
index = i;
}
}
if (!"".equals(finalStr)) {
finalStr = finalStr + ",";
}
finalStr = finalStr + multiply(str1, expr.substring(index, expr.length()));
return finalStr.replaceAll(",", "\n");
}
private static int evaluate(StringBuffer buffer, String str, String expr, int i) {
int index = i;
for (; i < expr.length();) {
char ch = expr.charAt(i++);
if (ch == ')') {
buffer.append(multiply(str, expr.substring(index, i - 1)));
break;
}
if (ch == '(') {
StringBuffer buffer1 = new StringBuffer();
i = evaluate(buffer1, multiply(str, expr.substring(index, i - 1)), expr, i);
str = buffer1.toString();
index = i;
}
}
return i;
}
private static String multiply(String str1, String str2) {
String str1Arr[] = str1.split(",");
String str2Arr[] = str2.split(",");
String str = "";
for (int i = 0; i < str1Arr.length; i++) {
for (int j = 0; j < str2Arr.length; j++) {
if (!"".equals(str)) {
str = str + ",";
}
str = str + str1Arr[i] + str2Arr[j];
}
}
return str;
}
}
import java.util.Stack;
public class BashBrace {
public static void main(String[] args) {
String expr = "a,((a,b)o(m,n)p),b(a,c)";
System.out.println(bashBrace(expr));
}
public static String bashBrace(String expr) {
Stack<String> stack = new Stack<String>();
String finalStr = "";
String str1 = "";
int index = 0;
for (int i = 0; i < expr.length();) {
char ch = expr.charAt(i++);
if (ch == ',') {
if (!"".equals(finalStr)) {
finalStr = finalStr + ",";
}
finalStr = finalStr + multiply(str1, expr.substring(index, i - 1));
str1 = "";
index = i;
}
if (ch == '(') {
StringBuffer buffer = new StringBuffer();
i = evaluate(buffer, multiply(str1, expr.substring(index, i - 1)), expr, i);
str1 = buffer.toString();
index = i;
}
}
if (!"".equals(finalStr)) {
finalStr = finalStr + ",";
}
finalStr = finalStr + multiply(str1, expr.substring(index, expr.length()));
return finalStr.replaceAll(",", "\n");
}
private static int evaluate(StringBuffer buffer, String str, String expr, int i) {
int index = i;
for (; i < expr.length();) {
char ch = expr.charAt(i++);
if (ch == ')') {
buffer.append(multiply(str, expr.substring(index, i - 1)));
break;
}
if (ch == '(') {
StringBuffer buffer1 = new StringBuffer();
i = evaluate(buffer1, multiply(str, expr.substring(index, i - 1)), expr, i);
str = buffer1.toString();
index = i;
}
}
return i;
}
private static String multiply(String str1, String str2) {
String str1Arr[] = str1.split(",");
String str2Arr[] = str2.split(",");
String str = "";
for (int i = 0; i < str1Arr.length; i++) {
for (int j = 0; j < str2Arr.length; j++) {
if (!"".equals(str)) {
str = str + ",";
}
str = str + str1Arr[i] + str2Arr[j];
}
}
return str;
}
}
Sureshkumar, I tested your code with following 3 test cases:
(a,b,cy)n,m
((a,b)o(m,n)p,b)
((((a,b)c,pp)(asd,ddd))UU,j)
it only work for first case. The second and third case it is not work correctly. This is due to the evaluate() missing process of char ','. Fix that it should work for all above 3 cases. I rewrite your code into C# and further adjust the evaluate function:
/// <summary>
/// Write code that would parse an expression that is similar to BASH brace expansion.
/// Best illustrated with an example: the expression "(a,b,cy)n,m" would be parsed into
/// an array of the following strings:
/// an
/// bn
/// cyn
/// m
///
/// You can assume that the input will always be valid.
///
/// Hint: the expression can nest. Therefore, "((a,b)o(m,n)p,b)" parses into:
/// aomp
/// aonp
/// bomp
/// bonp
/// b
///
/// ((((a,b)c,pp)(asd,ddd))UU,j)
/// acasdUU
/// acdddUU
/// bcasdUU
/// bcdddUU
/// ppasdUU
/// ppdddUU
/// j
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static string BashExpansion(string expression)
{
StringBuilder finalStr = new StringBuilder();
string str1 = string.Empty;
int index = 0;
for (int i = 0; i < expression.Length; )
{
char c = expression[i];
i++;
if (c == ',')
{
if (finalStr.Length != 0)
{
finalStr.Append(',');
}
finalStr.Append(Mulply(str1, expression.Substring(index, i - 1 - index)));
str1 = string.Empty;
index = i;
}
if (c == '(')
{
StringBuilder buffer = new StringBuilder();
str1 = Mulply(str1, expression.Substring(index, i - 1 - index));
i = Evaluate(buffer, expression, i);
str1 = Mulply(str1, buffer.ToString());
index = i;
}
}
if (finalStr.Length != 0)
{
finalStr.Append(',');
}
finalStr.Append(Mulply(str1, expression.Substring(index)));
finalStr.Replace(',', '\n');
return finalStr.ToString();
}
public static string Mulply(string str1, string str2)
{
char[] del = { ',' };
string[] arr1 = str1.Split(del);
string[] arr2 = str2.Split(del);
StringBuilder buffer = new StringBuilder();
foreach (var item in arr1)
{
foreach (var item1 in arr2)
{
if (buffer.Length != 0)
{
buffer.Append(',');
}
buffer.Append(item);
buffer.Append(item1);
}
}
return buffer.ToString();
}
public static int Evaluate(StringBuilder buffer, string expression, int i)
{
int index = i;
string str1 = string.Empty;
while (i < expression.Length)
{
char c = expression[i];
i++;
if (c == ',')
{
if (buffer.Length != 0)
{
buffer.Append(',');
}
buffer.Append(Mulply(str1, expression.Substring(index, i - 1 - index)));
str1 = string.Empty;
index = i;
}
if (c == ')')
{
if (buffer.Length != 0)
{
buffer.Append(',');
}
buffer.Append(Mulply(str1, expression.Substring(index, i - 1 - index)));
break;
}
if (c == '(')
{
StringBuilder buffer1 = new StringBuilder();
str1 = Mulply(str1, expression.Substring(index, i - 1 - index));
i = Evaluate(buffer1, expression, i);
str1 = Mulply(str1, buffer1.ToString());
index = i;
}
}
return i;
}
public static void Main(string[] args)
{
string[] strs = { "(a,b,cy)n,m", "((a,b)o(m,n)p,b)", "((((a,b)c,pp)(asd,ddd))UU,j)" };
foreach (var str in strs)
{
Console.WriteLine("{0} Expanded to: \n{1}", str, BashExpansion(str));
Console.WriteLine("\n");
}
}
Anyway, thank you for the idea.
I don't know if this is the best way, but you could write this as a simple recursive descent parser. The trick is getting the write grammar.
This is the simplese grammar I could come up with:
EXPRLIST ::=
EXPR |
EXPR "," EXPR
EXPR ::=
STRINGEXPR |
EXPANSIONEXPR |
EXPR EXPR
STRINGEXPR ::=
"[A-Z][a-z]"
EXPANSIONEXPR ::=
"(" EXPRLIST ")"
Then translating this into a javascript like pseudo code, gives you this:
var input = "" // some input string;
var pointer= 0; // pointer to position in the input
function Run(strInput){
input = strInput;
pointer=0;
return ReadExprList();
}
function Curr(){
if(position < input.length-1)
return input[position];
else
return null; // EOF
}
function ReadExpr() {
var ctx = [""];
While(Curr().isAlphaNumericChar() || Curr() == "("){
if(Curr().isAlphaNumericChar()){
var str = ReadString();
for(i=0 to ctx.length-1){
ctx[i] += str;
}
}
else{
var expanded = ReadExpansion();
var newctx = [];
for(i in ctx){
for(j in expanded){
newctx.push(ctx[i]+expanded[j]);
}
}
ctx = newctx
}
}
return ctx;
}
function ReadExprList(){
var ctx = [];
do{
ctx = ctx + ReadExpr();
} while (Curr() == ",")
}
function ReadString(){
str = "";
while(Curr().isAlphaNumericChar){
str += ReadChar()
}
return str;
}
function ReadExpansion(){
Read("(");
var result = ReadExprList();
Read(")");
return result;
}
function Read(var char){
var c = Curr();
if(char != c){
error("Expected: " + char +" actual: " +c);
}
pointer++;
return c;
}
function Read() {
var c = Curr();
pointer++;
return c;
}
// Bash pattern generation, e.g. "(a,b,cy)n,m", or "((a,b)o(m,n)p,b)"
#include <vector>
#include <iostream>
#include <string>
using std::string;
using std::vector;
vector<string> parse(string pat) {
int L = int( pat.size() );
int lp = 0;
int up = 0;
vector<string> aseg;
vector<string> cseg(1, "");
while (up<L) {
lp = up;
++up;
switch (pat[lp]) {
case '(': {
int c = 1;
while (up<L && c) {
if (pat[up] == '(') {
++c;
} else if (pat[up] == ')') {
--c;
}
++up;
}
vector<string> part = parse(pat.substr(lp+1, up-lp-2));
vector<string> tmp;
for (auto s1 : cseg) {
for (auto s2 : part) {
tmp.push_back(s1 + s2);
}
}
cseg = tmp;
break;
}
case ',': {
if (!cseg[0].empty()) {
aseg.insert(aseg.end(), cseg.begin(), cseg.end());
cseg = vector<string> (1, "");
}
break;
}
default: {
while(up<L && pat[up] != '(' && pat[up] != ')'
&& pat[up] != ',') {
++up;
}
string part = pat.substr(lp, up-lp);
vector<string> tmp;
for (auto s : cseg) {
tmp.push_back(s + part);
}
cseg = tmp;
break;
}
}
}
if (!cseg[0].empty()) {
aseg.insert(aseg.end(), cseg.begin(), cseg.end());
}
return aseg;
}
int main() {
const string s1 = "(a,b,cy)n,m";
vector<string> r1 = parse(s1);
std::cout << "First case:" << std::endl;
for (auto t : r1) {
std::cout << t << std::endl;
}
const string s2 = "((a,b)o(m,n)p,b)";
vector<string> r2 = parse(s2);
std::cout << "Second case:" << std::endl;
for (auto t : r2) {
std::cout << t << std::endl;
}
}
void ParseBrace(std::string prefix, char* pCur, int depth, bool bCommaTerm)
{
std::string curTok;
while (1)
{
bool bClearCurTok = true;
switch (*pCur)
{
case '(':
case ')':
prefix += curTok;
depth += (*pCur == '(') ? 1 : -1;
break;
case ',':
case '\0':
if (depth)
{
int targetDepth = depth-1;
char* pNext = pCur;
for (; depth != targetDepth; pNext++)
depth += (*pNext == '(') ? 1 : (*pNext == ')') ? -1 : 0;
ParseBrace(prefix + curTok, pNext, depth++, true);
}
else
{
std::cout << prefix << curTok << "\n";
if (bCommaTerm || !*pCur)
return;
}
break;
default:
curTok += *pCur;
case ' ': case '\t': case '\r': case '\n':
bClearCurTok = false;
break;
}
pCur++;
if (bClearCurTok)
curTok.clear();
}
}
void main()
{
char buf[128];
while(1)
ParseBrace("", gets(buf), 0, false);
}
Works right for all inputs tested
package strings;
import java.util.ArrayList;
/**
* Created by Emin Guliyev on 24/08/2015.
*/
//http://www.careercup.com/question?id=5717301963784192
public class BashBrace {
private int i=0;
public String s;
public BashBrace(String s) {
this.s = "(" + s + ")";
}
public ArrayList<String> getStringArray() {
ArrayList<String> result = new ArrayList<>();
ArrayList<String> temp;
if (s.charAt(i) == '(') {
i++;
while (s.charAt(i-1) != ')') {
temp = getStringArray();
result.addAll(temp);
i++;// skip "," or ")"
}
if (i == s.length()) {
return result;
}
result = getCartesianProductStringArray(result);
} else {
String literal = "";
while (i < s.length() && s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
literal += s.charAt(i);
i++;
}
result.add(literal);
result = getCartesianProductStringArray(result);
}
return result;
}
private ArrayList<String> getCartesianProductStringArray(ArrayList<String> result) {
ArrayList<String> temp;
while (i < s.length() && s.charAt(i) != ',' && s.charAt(i) != ')') {
temp = getStringArray();
result = cartesianProduct(result, temp);
}
return result;
}
private ArrayList<String> cartesianProduct(ArrayList<String> listA, ArrayList<String> listB) {
ArrayList<String> result = new ArrayList<>();
for (String a: listA) {
for (String b : listB) {
result.add(a+b);
}
}
return result;
}
public static void main(String[] args) {
BashBrace bashBrace = new BashBrace("((a,b)o(m,n)p,b)");
for (String item : bashBrace.getStringArray()){
System.out.println(item);
}
}
}
Python code with recursion. The complexity of this problem makes it too hard to solve more elegantly..
- bboczeng March 04, 2015def bashbrace(string): if not string: return [[]] # do it recursively: def recursiveSol(strA): if not strA: return [[]] elif len(strA)==1: return [[strA[0]]] else: temp=[[]] i=0 while i<len(strA): if strA[i]=="(": count=1 for j in range(i+1,len(strA)): if strA[j]=="(": count+=1 elif strA[j]==")": count-=1 if count==0: break subresult=recursiveSol(strA[i+1:j]) thistime=[] for each in subresult: for toadd in temp: tmp=toadd[:] tmp.extend(each[:]) thistime.append(tmp) temp=thistime[:] i=j+1 elif strA[i]==",": j=i+1 while j<len(strA): if strA[j]==",": subresult=recursiveSol(strA[i+1:j]) temp.extend(subresult[:]) i=j j=j+1 subresult=recursiveSol(strA[i+1:]) temp.extend(subresult[:]) i=len(strA) else: for each in temp: each.append(strA[i]) i=i+1 return temp result=recursiveSol(string) strresult=[] for each in result: strresult.append("".join(each)) return strresult print(bashbrace("(a,b)o(m,n)p,b"))