CareerCup

Ya even I failed the last test case and my friend who got this question also failed the last test case... Has anyone passed all test cases???

Has anyone solved this question? I have a very lengthy approach for this question but was wondering if it can be done in more feasible ways.

public class TwitterProblem {


    public static void main(String args[] ) throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        ArrayList<String> allStringsToManipulate = new ArrayList<String>();

        String test1="(AB)C/";
        String test2="(AB)C/S";
        String test3="(AB)C/RS";
        String test4="A(BC)/RS";
        String test5="A(BC)/RSR";

        String test6= "(AB)C((DE)F)A(BC)/RSR";

        String test7= "(AB)C/S\nA(BC)/RSR";
        //String test7= "(AB)C((DE)F)/SSSS";

        allStringsToManipulate.add(test1);
        allStringsToManipulate.add(test2);
        allStringsToManipulate.add(test3);
        allStringsToManipulate.add(test4);
        allStringsToManipulate.add(test5);
        allStringsToManipulate.add(test6);



                String[] myList=allExpressionsInLine(test6);

        for(String expression: myList){

                String answer = stripEverythingAfterBackslash(expression);
                char[] allOperations = operations(expression);
                if(expression!=null || expression.length()>0){
                    expression=expression.trim();
                    expression = expression.replaceAll("\\s","");
                    boolean simplified=false;
                    int index = 0;

                    while (index < allOperations.length) {
                        if (allOperations[index] == 'S'  &&!simplified|| allOperations[index] == 's' &&!simplified) {
                            String result = simplify(answer);
                            answer = result;
                            simplified=true;
                        } else if (allOperations[index] == 'R' || allOperations[index] == 'r') {
                            answer = reverse(answer);
                        } else {

                        }
                        index++;
                    }
                    System.out.println(answer);
                }else{
                    System.out.println("");
                }

        }
    }


    static String[] allExpressionsInLine(String line){
        String lines[] = line.split("(\r\n|\r|\n)", -1);
        return lines;
    }


    static char[] operations(String expression){

        int counter=0;
        boolean begin =false;
        for(int i=0;i<expression.length(); i++){

            if(begin){
                counter++;
            }
            if(expression.charAt(i)=='/'){
                begin=true;
            }

        }
        char[] allOperations = new char[counter];
        begin=false;
        int index=0;
        for(int i=0;i<expression.length(); i++){

            if(begin){
                allOperations[index]= expression.charAt(i);
                index++;
            }
            if(expression.charAt(i)=='/'){
                begin=true;
            }

        }

        return allOperations;
    }



    static String simplify(String expression){
        String answer=expression;

        int totalNests = isItWorthSimplifying(answer);

        if(expression.charAt(0) =='(') {
             answer= removeFirstPairOfParanthesis(expression);
        }

        if(totalNests>1) {
            String result = removeNestedParanthesis(answer, totalNests);
            return result;
        }

        return answer;
    }



    static int isItWorthSimplifying(String expression){

        Stack<Character> openParan = new Stack<>();
        int maxNest=0;

        for(int i=0;i<expression.length();i++){
            char currLetter= expression.charAt(i);
            if(currLetter == '('){
                openParan.push('(');
            }else if(currLetter ==')'){
                openParan.pop();
            }else{

                if(maxNest<openParan.size()){
                    maxNest=openParan.size();
                }
            }

        }

        return maxNest;

    }



    static String removeNestedParanthesis(String expression, int maxNest){

        Stack<Character> openParan = new Stack<>();
        StringBuilder word = new StringBuilder("");

        int index=0;

        while(index<expression.length()){

            char currLetter= expression.charAt(index);
            if(currLetter == '(' && openParan.size()+1<maxNest){
                openParan.push('(');
                word.append(currLetter);
            }else if(currLetter ==')'){

                if(openParan.size()!=maxNest){
                    word.append(currLetter);
                }
                openParan.pop();

            }else{

                if(currLetter == '(' && openParan.size()+1==maxNest){
                    openParan.push('(');
                }else{
                    word.append(currLetter);
                }
            }
            index++;
        }

        return word.toString();
    }





    static String removeFirstPairOfParanthesis(String s){

        StringBuilder answer= new StringBuilder("");
        boolean firstOpen=false;
        boolean firstClosed=false;

        for(int i=0; i<s.length(); i++){

            if(s.charAt(0)=='(' && !firstOpen){
                firstOpen=true;
            }else if(s.charAt(i)== ')' && !firstClosed){
                firstClosed=true;
            }else{
                answer.append(s.charAt(i));
            }
        }
        return answer.toString();
    }




    static String stripEverythingAfterBackslash(String expression){
        int end=expression.indexOf('/');
        if(end!=-1) {
            String newExpression = expression.substring(0, end);
            return newExpression;
        }
       return expression;
    }


    static String reverse(String expression){
        StringBuilder word = new StringBuilder("");
        for(int i=expression.length()-1; i>=0; i--){
            if(expression.charAt(i)=='(') {
                word.append(")");
            }else if(expression.charAt(i)==')'){
                word.append("(");
            }else{
                word.append(expression.charAt(i));
            }

        }
        return word.toString();
    }
}

. lolol

Ignore the lol at the end. But I passed 3/4 Test Cases with that.

Couldnt think of a way to do it that wasn't lengthy. So Came up with what I think is an easy to read solution. No Idea why I was failing the last test case though. Feel Free to blow my mind with whats wrong with it

an alternative approach using an AST.

Where was this question from? Looks like from a contest.

/*
the productions of the expression are
RootExpression = {Term}*
Term = Variable | Expression
Expression = '(' Term ')'
Variable = [a-zA-Z]

the following structs represent a syntax tree, I omitted 
access levels to have shorter code

the application of the transformation can be optimized as 
SRRS = S
SRSRSRS = SRS
RSS = RS
etc...
*/
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <iostream>

using namespace std;

struct Term
{
	Term() { }
	virtual void simplify() { };
	virtual void reverse() { };
	virtual void print(ostream& os) = 0;
};

struct Variable : Term
{
	char name_;
	Variable(char name) : name_(name) { }
	void print(ostream& os) override { os << name_; }
};

struct Expression : Term
{
	vector<Term*> terms_;	
	
	// parses and creates expression structure
	Expression(istream& is) { 
		char chr;
		while (is.get(chr)) {
			if (chr == '(') terms_.push_back(new Expression(is));
			else if (chr == ')') break;
			else terms_.push_back(new Variable(chr));
		}
	}
	
	// reverses 
	void reverse() override { 
		std::reverse(terms_.begin(), terms_.end());
		for (Term* t : terms_) t->reverse();
	}

	// simplifies
	void simplify() override {
		Expression *ex = dynamic_cast<Expression*>(*terms_.begin());
		if (ex != nullptr) {
			ex->simplify();
			terms_.erase(terms_.begin());
			terms_.insert(terms_.begin(), ex->terms_.begin(), ex->terms_.end());
		}
		for (Term* t : terms_) t->simplify();
	}

	// print
	void print(ostream& os) override { os << "("; printSubExprs(os); os << ")"; }
	void printSubExprs(ostream& os) { for (Term* t : terms_) t->print(os); }
};

struct RootExpression : Expression {
	RootExpression(istream& is) : Expression(is) { }
	void print(ostream& os) override { printSubExprs(os); }
};

void transformAndPrintExpression(const string& expression, const string& transformation)
{
	RootExpression expr = RootExpression(stringstream(expression));
	
	// optimize transformation string
	bool reverse = false;
	bool simplify = false;
	bool simplifyReversed = false;
	for (char t : transformation) {
		if (t == 'S') {
			simplify |= !reverse;
			simplifyReversed |= reverse;
		} else if (t == 'R') {
			reverse = !reverse;
		}
	}
	
	// apply
	if (simplify) {
		expr.simplify();
	}
	if (simplifyReversed) {
		expr.reverse();
		reverse = !reverse;
		expr.simplify();
	}
	if (reverse) {
		expr.reverse();
	}

	expr.print(cout);
	cout << endl;
}

int main()
{
	transformAndPrintExpression("(AB)(C(DE))", "SS"); // AB(C(DE))
	transformAndPrintExpression("(((AB)C)D)E", "SS"); // ABCDE
	transformAndPrintExpression("(((AB)C)D)E", "SR"); // EDCBA
	transformAndPrintExpression("(AB)C((DE)F)", "SRS"); // FEDCBA
	transformAndPrintExpression("(AB(CD((EF)G)H))(IJ)", "SRS"); // JI(H(GFE)DC)BA
	transformAndPrintExpression("(A(B(C)D)E(FGH(IJ)))", "SRRSSRSSRRRSSRS"); // JIHFGE(D(C)B)A
	transformAndPrintExpression("(A(B(C)D)E(FGH(IJ)))", "SRS"); // JIHFGE(D(C)B)A
	transformAndPrintExpression("(A(BC(D(E((Z)K(L)))F))GH(IJK))", "S"); // A(BC(D(E(ZK(L)))F))GH(IJK)/S	
}