transform the expression...getting wrong answer

[sittan]

The question is :
Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" would be written "3 4 − 5 +" first subtract 4 from 3, then add 5 to that.

Transform the algebraic expression with brackets into RPN form.

You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like a*b*c)
Input

The first line contains t, the number of test cases (less then 100).

Followed by t lines, containing an expression to be translated to RPN form, where the length of the expression is less then 400.
Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*


The Code is :
#include<stdio.h>
int main()
{
long int i=0,count=0,c=0;
long int n;
scanf("%ld",&n);
while(n!=0)
{
long int arr[n+1],out[n+1];
for(i=1;i<=n;i++)
scanf("%ld",&arr[i]);
for(i=1;i<=n;i++)
{
out[arr[i]]=i;
}

for(i=1;i<=n;i++)
{
if(out[i]==arr[i])
count++;
else
{
c=1;
printf("not ambigous\n");
break;
}
}
if(c!=1)
printf("ambigous\n");
scanf("%ld",&n);
count==0;
c=0;
}
return 0;
}


I am getting wrong answer. The test cases run fine but fails for some unknown cases. I am not able to find out the fault. Please help me!

[simeonz]

I am sorry, but I don't understand your code. I don't see the connection.

Let me explain from memory what RPN is supposed to do:
First, without parentheses you simply have a stream of operands interspersed with operations. The problem is that the operations must be applied in clusters according to their precedence. That is, the problem is that the actual operands are not generally atomic, but are the result from entire expressions.

So, what you do is this.

- Every time you reach some atomic operand (one letter variable in your case) you can directly output it in the RPN stream. The reason is simple. If you observe your RPN example, you will notice that the order of the operands does not change when converting from infix to RPN. Only the operations are reordered. In other words you have no reason to hold on to the operands. You simply output them.

- You don't know if an operation will bind to its right operand, because the succeeding one may have greater precedence. That is why you maintain a stack. You push an operation there to remember that it waits for arbitration. Then when you try to push another operation later, you first look at the top of the stack. If you find that another higher or equal priority operation is waiting for decision, you pop it off the stack and output it. Why? Because it does indeed bind to its right operand (which has already been output). Then you again look at the top of the stack and so on. You do this until the top of the stack holds operation with lower priority or until the stack is empty. Then you push the new operation (that started all of this) on the stack.

- Left parenthesis are pushed on the stack without any processing whatsoever. For the purposes of the previous paragraph, parens will serve as temporary bottom of the stack. That is, you don't pop operations from the stack past left paren. When you reach right parenthesis you output all operations currently on the stack after the left paren by poping them one after another. You then pop the left parenthesis too, but without outputing it.

For the stack you can use: http://www.cplusplus.com/reference/stl/stack/
You can use stack of chars (stack<char>) and look up the priority of the operation symbol every time. Or you can determine the priority when you push the symbol and remember the priority level on auxiliary stack. Or you can use one stack that holds structures that contain the symbol and its priority. There are some design decisions to be made.

It is not simple algorithm. It will need some time to sink in. One important invariant here is that the right operand is at all times already outputted in RPN. You just don't know what binds to it.

You can find full description here, but it is for a bit tougher version (with associativity rules and other stuff): http://en.wikipedia.org/wiki/Shunting-yard_algorithm

Regards