Here is the link to the problem:
http://www.spoj.pl/problems/EXPRESS/
And here is the link to my solution:
The solution gets a Time Limit Exceeded on SPOJ. I have first transformed the Postfix expression to a Infix tree and then I simply used a queue to reverse the described process(in the problem). Is this solution so slow or is this due to the input/output that I am facing TLE?
It seems to me that you have problems with your implementation of the solution:
- You do a lot of string concatenations, do note that that appending a string at the beginning of the string is painful (like 'ans=n->op+ans;' and etc).
- There are a lot of dynamic memory allocations (you use operator new for every nodes) and accesses to different, possibly disjoint, memory areas (when traversing the tree).
- Additionally, you may assume that proper usage of vector<> instead of the queue<> and stack<> (both, by default, use deque implementation) may be vividly faster in many cases.
- Among other possible things, which may add speed improvements: either using scanf() instead of cin input stream or switching the sync_with_stdio flag for the input stream.
- Also, conversions from char[] to string look suspicious.
I haven't done any actual testing of your code, those were the things that I've seen and assumed from the first glance. Hope it helps.
Thanks, that'll be good notes. Will work on those lines.