Expressions in postfix notation

[kaushik_acharya]

http://poj.org/problem?id=3367

Have received Time Limit Exceeded.

My algo:
1. create the tree.
2. BFS traversal. Pushed the elements into string as the elements are visited.
3. reversed the string.

I checked the Judges's comment from the original source http://www.informatik.uni-ulm.de/acm/Locals/2007/.
My algo seems similar.

I ran on the test case mentioned there(200 test cases).

To test the timing(using clock()) I tried two approach:

a) instead of writing on console I wrote on file.
b) wrote on console.

Code: Select all

	if (WRITE_INTO_FILE)
	{
		fprintf(pFile,"%s\n",str.c_str());
	}
	else
	{
		printf("%s\n",str.c_str());
	}

Timing in case(a):
Total time: 297 ms.
Individual timing: usually 0 except for some cases its 15-16 ms.

Timing in case(b):
Total time: 6.36 sec

Any idea what should I change?

[brianfry713]

In the code you submit: read from stdin, write to stdout. You can redirect to/from a file for testing.

[kaushik_acharya]

I redirected the stdout to a file as mentioned here:
http://www.mathinfo.u-picardie.fr/asch/ ... ction.html

$ myprog < myin > myout

I am still not sure why I am getting Time Limit Exceeded.

[brianfry713]

It's hard to guess why without seeing your code.

[kaushik_acharya]

This is what I had tried:

Code: Select all

#define MAX_STR_LENGTH 10001

class TreeNode
{
public:
       // functions to get and set the member variables
private:
	char item_;
	TreeNode* parent_;
	TreeNode* left_;
	TreeNode* right_;
}

class Tree
{
public:
	void read_input();
	void traversal();
	void write_output();
private:
	TreeNode* root_;
	std::string str_;
	unsigned int size_;
}

void Tree::read_input()
{
	std::stack<TreeNode* > stk;
	//char* str = (char*)malloc(MAX_STR_LENGTH);
	// http://stackoverflow.com/questions/51592/is-there-a-need-to-destroy-char-string-or-char-new-char6
	char* str = new char[MAX_STR_LENGTH];
	
	gets(str);
	
	unsigned int i = 0;

	while (str[i] != '\0')
	{
		char ch = str[i];
		TreeNode* node = new TreeNode(ch);

		if (isupper(ch))
		{
			TreeNode* rightNode = stk.top();
			stk.pop();
			TreeNode* leftNode = stk.top();
			stk.pop();
			// set the parent-child relations
			(*node).setRight(rightNode);
			(*rightNode).setParent(node);
			(*node).setLeft(leftNode);
			(*leftNode).setParent(node);
		}

		stk.push(node);
		++i;
		++size_;
	} // while

	delete[] str;
	//free(str);

	// assign the root of the tree
	root_ = stk.top();
	stk.pop();
}

void Tree::traversal()
{
	std::queue<TreeNode* > qu;
	
	str_.reserve(size_);
	//vec_.reserve(size_);
	qu.push(root_);

	while (!qu.empty())
	{
		TreeNode* node = qu.front();
		str_.push_back((*node).item());
		//vec_.push_back((*node).item());

		qu.pop();

		if ((*node).left())
		{
			qu.push((*node).left());
		}
		if ((*node).right())
		{
			qu.push((*node).right());
		}
	}
}

void Tree::write_output()
{
	std::string str = std::string(str_.rbegin(),str_.rend());
	printf("%s\n",str.c_str());
}


// in the main()

	for(unsigned int case_i=0; case_i != nCase; ++case_i)
	{
		Tree tree;
		tree.read_input();
		tree.traversal();
		tree.write_output();
	}

[brianfry713]

Post your full code that you'd actually submit.