11234 - Expressions

[Kallol]

i am getting runtime error signal 11 (SIGSEGV). for this code :
But I cant find why ??

Anybody to help me??

Code: Select all

removed after AC

[mf]

You don't clean your queue - Q.front and Q.back increase with every test, and access memory beyond array boundaries.

STL's queue is fast enough for this problem, btw.

[Timo]

Please remove your code if it can get AC after clean the queue ^_^.

[Kallol]

Thank you very much , I did not notice that is not being cleaned. Now I have cleaned it. But unfortunately , this time I am getting WA.

here is the changed code ( just cleaned the queue)

Code: Select all

removed after AC

To mf, thank you very much for your advice , I am at very beginning stage of STL learning. I tried to use a STL queue of the pointers of the objects of my self-defined class 'node' . But when popping , the compiler threw an error that the pop function is returning a void type pointer which cannot be casted to my object's pointer. So, I had to go back to my straight forward queue class.

[mf]

Now your array 't' doesn't get cleaned between test cases. Try this input to see that in action.

Code: Select all

3
xyPzwIM
abcABdefgCDEF
xyPzwIM

I tried to use a STL queue of the pointers of the objects of my self-defined class 'node' . But when popping , the compiler threw an error that the pop function is returning a void type pointer which cannot be casted to my object's pointer.

Use queue::front() to access the head element of the queue.
There's no member function in STL's queue that both extracts the head and returns it, but you could write one like this:

Code: Select all

template<typename T>
T pop(queue<T> &q) { T x = q.front(); q.pop(); return x; }

[Kallol]

Oh My GOD! What is going on with me !! I made this code during the contest and could not get AC for this 2 silly mistakes !! really frustrating. If some problems are missed which I really cant solve doesnt cause me that much pain , but this type of missing is really embarrassing !

Anyway , mf , You are really of great help, Thank you !

and thanks again for STL advice . It sounds cooler now

[albet_januar]

Code: Select all

delete

[jjtse]

Does anyone know more ways to optimize this code? I already optimized my queue usage. I'm suspecting I can do my string concatenations faster, but I don't know how to do it. Any ideas how I can get this faster?


Here's the code:

Code: Select all

#include <iostream>
#include <string>

//11234.cpp

using namespace std;

int t;
string q[990000];
string ans;
int idx;
int head;

void push(string s){
	q[idx++] = s;
}

string pop(){
	string s = q[head];
	head++;
	return s;
}

bool isEmpty(){
	if (head >= idx)
		return true;
	else
		return false;
}


int numOfOps(string s){
	int cnt = 0;
	int len = s.length();

	for (int i=len -1; i>=0; i--){
		if (s[i] < 95)  {//operator
			cnt ++;
			continue;
		}
		else
			break;
	}

	return cnt;
}


int main(){
	
	string s;
	int len;
	int skip;

	cin >> t;

	for (int i=0; i<t; i++){
		cin >> s;
		idx = 0;
		head = 0;
		push(s);
		ans = "";
		while (!isEmpty()){
			s = pop();
			len = s.length();
			if (s[len-1] < 95){
				ans = s[len-1] + ans;
				skip = numOfOps(s);
				if (skip > 1){
					string right = s.substr(len-2*skip, 2*skip-1);
					string left = s.substr(0, len-2*skip);
					push(left);
					push(right);
				}
				else{
					push(s.substr(0, len-1));
				}
			}
			else{
				for (int j=0; j<len; j++)					
					ans = s[j] + ans;
			}
		}		//end while

		cout << ans << endl;
	}		//end for

}

[sclo]

Does anyone know more ways to optimize this code? I already optimized my queue usage. I'm suspecting I can do my string concatenations faster, but I don't know how to do it. Any ideas how I can get this faster?

You are copying string all the time, your algorithm is slow because of that.

[dallen]

I'm trying to upload my solution to problem #11234 but I keep getting CE from the Judge. Anyone experienced in Java willing to help? thanks.

Here's my code.

Code: Select all

//import java.io.File;
//import java.io.FileInputStream;
//import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

class Main {

	private static Stack<Character> stack = new Stack<Character>();

	public static void main(String[] args) /*throws FileNotFoundException*/ {
		//final long startTime = System.currentTimeMillis();
//		System.setIn(new FileInputStream(new File("test.txt")));

		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		
		StringBuilder output = new StringBuilder();

		while (sc.hasNextLine()) {
			String line = sc.nextLine();
			for (char c : line.toCharArray()) {
				stack.push(c);
			}

			Node tree = buildTree();
			output.append(tree.queueExpression() +  "\n");
			stack.clear();
		}
		
		output.deleteCharAt(output.length() - 1);
		System.out.println(output.toString());
		//System.out.println(System.currentTimeMillis() - startTime);
	}

	public static Node buildTree() {
		Character c = stack.pop();
		Node leftSubtree, rightSubtree;

		if (Character.isUpperCase(c)) {
			leftSubtree = buildTree();
			rightSubtree = buildTree();
		} else {
			return new Node(c);
		}

		return new Node(c, leftSubtree, rightSubtree);
	}

}

class Node {
	Character value;
	Node leftChild;
	Node rightChild;

	Node(Character value) {
		this(value, null, null);
	}

	Node(Character value, Node leftChild, Node rightChild) {
		this.value = value;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}

	public String queueExpression() {
		Queue<Node> frontier = new LinkedList<Node>();
		Stack<Character> visited = new Stack<Character>();
		frontier.add(this);

		while (!frontier.isEmpty()) {
			Node current = frontier.remove();
			visited.push(current.value);

			if (current.rightChild != null) {
				frontier.add(current.rightChild);
			}

			if (current.leftChild != null) {
				frontier.add(current.leftChild);
			}
		}

		StringBuilder sb = new StringBuilder();

		while (!visited.isEmpty()) {
			sb.append(visited.pop());
		}

		return sb.toString();
	}

//	@Override
//	public String toString() {
//		String str = "[value:" + value + ", left:" + leftChild.value
//				+ ", right:" + rightChild.value + "]";
//		return str;
//	}

}

[brianfry713]

That is AC code. You can click "My Submissions" to see the reason for a Compile Error.

[dallen]

I already solved the problem. I don't know why the judge displayed "compilation error" but later it changed to "runtime error", BTW if you're curious the mistake in the code is not handling empty input the rest is correct and I got accepted when I fixed that. Thanks anyway for responding.

[@li_kuet]

Who are getting WA try this case

Code: Select all

1
abDcdEBefFghGCA

answer should be

Code: Select all

hgfedcbaGFEDCBA

[SIO__Five]

I already solve the problem, but got a "runtime error". Can anybody tell me why? Thanks!

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<stack>
using namespace std;
char str[10010],in[10010];
struct node
{
    char ch;
    node* lchild;
    node* rchild;
};
node* build(int n, char *in, char *str, node* u)
{
    if (n<=0) return NULL;
    int i=0;
    while(*(in+i)!=*str) i++;
    u=(node*) malloc (sizeof(node));
    u->ch=*str;
    u->lchild=build(i,in,str-n+i,u->lchild);
    u->rchild=build(n-i-1,in+i+1,str-1,u->rchild);
    return u;
}
void bfs(node* u)
{
    node* tree[20010];
    int front=0,rear=1,n=0;
    char cx[10010];
    tree[0]=u;
    while(front<rear)
    {
        node* temp=tree[front++];
        cx[n++]=temp->ch;
        if (temp->lchild!=NULL) tree[rear++]=temp->lchild;
        if (temp->rchild!=NULL) tree[rear++]=temp->rchild;
    }
    for (int i=n-1; i>=0; i--)
        cout<<cx[i];
    cout<<endl;
    return;
}
int main ()
{
    int t,len,i;
    cin>>t;
    while(t--)
    {
        memset(str,0,sizeof(str));
        cin>>str;
        stack<string> s;
        len=strlen(str);
        for (i=0; i<len; i++)
        {
            if (str[i]<='Z')
            {
                string t1,t2,temp;
                t1=s.top();
                s.pop();
                t2=s.top();
                s.pop();
                temp+=t1+str[i]+t2;
                s.push(temp);
            }
            else
            {
                string temp;
                temp+=str[i];
                s.push(temp);
            }
        }
        string temp;
        temp=s.top();
        while(!s.empty())
        {
            s.pop();
        }
        int j=0;
        memset(in,0,sizeof(in));
        for (i=temp.length()-1; i>=0; i--)
            in[j++]=temp[i];
        in[j]='\0';
        node* root=build(j,in,str+j-1,root);
        bfs(root);
    }
    return 0;
}

[brianfry713]

You call malloc but never free, maybe you are running out of memory.
You can solve this with only recursion. No queues, stacks, trees, or bfs is needed.