IBM Interview Question
Software Engineer / DevelopersCountry: United States
Thanks ashish for your code. But the output of your code is: James
is
a
boy
eating
sausages
Instead it should be: James is a boy eating sausages.
public static void main(String[] args) {
Stack<Character> ps = new Stack<Character>();
Stack<Character> ss = new Stack<Character>();
//List<String> list = new ArrayList<String>();=
args= new String[]{"(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a)(NN boy)) "+
"(VP (VBG eating) (NP (NNS sausages))))))"};
char[] toArray = args[0].toCharArray();
for (char c : toArray) {
if(c =='('){
ps.push('(');
}else if(c ==')'){
ps.pop();
StringBuilder sb = new StringBuilder();
while(!ss.isEmpty()){
char s = ss.pop();
if(s == ' '){//reverse expected
char[] a = sb.toString().toCharArray();
for (int i = sb.length()-1; i >=0; i--) {
System.out.print(a[i]);
}System.out.println();
ss.clear();
break;
}else{
sb.append(s);
}
}
}else{
ss.push(c);
}
}
}
public static void main(String[] args) {
Stack<Character> ps = new Stack<Character>();
Stack<Character> ss = new Stack<Character>();
//List<String> list = new ArrayList<String>();=
args= new String[]{"(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a)(NN boy)) "+
"(VP (VBG eating) (NP (NNS sausages))))))"};
char[] toArray = args[0].toCharArray();
for (char c : toArray) {
if(c =='('){
ps.push('(');
}else if(c ==')'){
ps.pop();
StringBuilder sb = new StringBuilder();
while(!ss.isEmpty()){
char s = ss.pop();
if(s == ' '){//reverse expected
char[] a = sb.toString().toCharArray();
for (int i = sb.length()-1; i >=0; i--) {
System.out.print(a[i]);
}System.out.println();
ss.clear();
break;
}else{
sb.append(s);
}
}
}else{
ss.push(c);
}
}
}
// ZoomBA
tree = { "NP" : [ { "DT" : "a" } , { "NN" : "boy" } ] }
def traverse( node , s ){
names = list( node.keySet )
name = names.0 // yes, we did it ourselves
value = node[name]
if ( value isa [ ] ){
for ( child : value ){
traverse ( child , s )
}
}else{
s += value
}
}
s = list()
traverse ( tree, s )
println( str(s, ' ') )
Here, we are forced to use minimal dictionary ( json ) format to store the parse tree.
Observe that the ordering does not matter at all for the nodes, because of the format chosen. Order is implicit in the list.
//ZoomBA
s = "(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a) (NN boy)) (VP (VBG eating) (NP (NNS sausages))))))"
def simplified_solution(s){
// observe that every ')' previous to that is the word to add, so :
cur = 0
len = #|s|
words = list()
while ( cur < len ){
r = index ( [cur: len] ) :: { s[$.item] == ')' } + cur
break ( r >= len )
l = rindex ( [ cur:r ] ) :: { s[$.item] == ' ' } + cur
break ( l >= len )
w = s[l+1:r-1]
if ( !empty( w.trim() ) ) { words += w }
cur = r + 1
}
println ( str ( words , ' ' ) )
}
simplified_solution( s )
A much faster and alternative -- to do it directly from string rep.
String st = "(S (NP (NNP james)) (VP (VBZ is) (NP (NP (DT a)(NN boy))";
StringBuffer str = new StringBuffer(st);
for (int i = str.length()-1; i >= 0 ; i--) {
System.out.println(i);
if(str.charAt(i)=='(' || str.charAt(i)== ')'){
str.deleteCharAt(i);
} else if(Character.isUpperCase(str.charAt(i))){
str.deleteCharAt(i);
}
}
System.out.println(str);
public class StringExtract {
public static void extractString(String inp) {
String[] stringPattern = inp.split(" ");
for (int i = 0; i < stringPattern.length; i++) {
String temp = stringPattern[i];
if (!String.valueOf(temp.charAt(0)).equals("(")) {
if (temp.contains("(")) {
temp = temp.substring(0, temp.indexOf("("));
System.out.println(temp.replace(")", ""));
} else {
System.out.println(temp.replace(")", ""));
}
}
}
}
public static void main(String[] args) {
String inp = "(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a)(NN boy))(VP (VBG eating) (NP (NNS sausages))))))";
//String inp = "(NP(DT a) (NN boy))";
extractString(inp);
}
}
static StringBuilder trim(String arg){
String [] arr = arg.split("\\)");
StringBuilder sb = new StringBuilder();
for(String str: arr ){
if(str.length()>0){
sb.append(str.substring(str.lastIndexOf(" ")));
}
}
return sb;
}
public static void main(String... args) {
String str1 = "(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a) (NN boy)) (VP (VBG eating) (NP (NNS sausages))))))";
System.out.println(trim(str1));
String str2 = "(NNS sausages)";
System.out.println(trim(str2));
String str3 = "(NP (NP (DT a) (NN boy))";
System.out.println(trim(str3));
}
static StringBuilder trim(String arg){
String [] arr = arg.split("\\)");
StringBuilder sb = new StringBuilder();
for(String str: arr ){
if(str.length()>0){
sb.append(str.substring(str.lastIndexOf(" ")));
}
}
return sb;
}
public static void main(String... args) {
String str1 = "(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a) (NN boy)) (VP (VBG eating) (NP (NNS sausages))))))";
System.out.println(trim(str1));
String str2 = "(NNS sausages)";
System.out.println(trim(str2));
String str3 = "(NP (NP (DT a) (NN boy))";
System.out.println(trim(str3));
}
static StringBuilder trim(String arg){
String [] arr = arg.split("\\)");
StringBuilder sb = new StringBuilder();
for(String str: arr ){
if(str.length()>0){
sb.append(str.substring(str.lastIndexOf(" ")));
}
}
return sb;
}
public static void main(String... args) {
String str1 = "(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a) (NN boy)) (VP (VBG eating) (NP (NNS sausages))))))";
System.out.println(trim(str1));
String str2 = "(NNS sausages)";
System.out.println(trim(str2));
String str3 = "(NP (NP (DT a) (NN boy))";
System.out.println(trim(str3));
}
def main():
outputString =""
inputString = "(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a) (NN boy)) (VP (VBG eating) (NP (NNS sausages))))))"
inputString = inputString.strip().split(' ')
for word in inputString:
if word.endswith(')'):
outputString = outputString + str(word.strip(')')) + " "
print(outputString)
main()
public static void main(String[] args) {
String sText = "(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a)(NN boy)) "+
"(VP (VBG eating) (NP (NNS sausages))))))";
StringBuffer sBuffer = new StringBuffer();
String[] textunderTest = sText.split("\\s|\\)");
for(String string : textunderTest){
if(string.length() > 0 && string.charAt(0) != '(' ){
sBuffer.append(string + " ");
}
}
System.out.println(sBuffer.toString());
}
public static void main(String[] args) {
String sText = "(S (NP (NNP James)) (VP (VBZ is) (NP (NP (DT a)(NN boy)) "+
"(VP (VBG eating) (NP (NNS sausages))))))";
StringBuffer sBuffer = new StringBuffer();
String[] textunderTest = sText.split("\\s|\\)");
for(String string : textunderTest){
if(string.length() > 0 && string.charAt(0) != '(' ){
sBuffer.append(string + " ");
}
}
System.out.println(sBuffer.toString());
}
}
- Ashis Kumar Chanda October 13, 2016