Any body has a solution to this code..!!

Talk about any languages right here. Share and discuss source, but don't expect your homework to be done for you.
Post Reply
rahulraina7
n00b
Posts: 1
Joined: Wed Sep 05, 2012 5:35 am

Any body has a solution to this code..!!

Post by rahulraina7 » Wed Sep 05, 2012 5:40 am

I am not asking any 1 to write it , but preferably looking for a person who already has the solution for this code..!!!
Preferable language is c/c++ .



Code: Select all

An expression consisting of operands and binary operators can be written in Reverse Polish Notation (RPN) by writing both the operands followed by the operator. For example, 3 + (4 * 5) can be written as "3 4 5 * +".
 
You are given a string consisting of x's and *'s. x represents an operand and * represents a binary operator. It is easy to see that not all such strings represent valid RPN expressions. For example, the "x*x" is not a valid RPN expression, while "xx*" and "xxx**" are valid expressions. What is the minimum number of insert, delete and replace operations needed to convert the given string into a valid RPN expression?
 
Input:
The first line contains the number of test cases T. T test cases follow. Each case contains a string consisting only of characters x and *.
 
Output:
Output T lines, one for each test case containing the least number of operations needed.
 
Constraints:
1 <= T <= 100
The length of the input string will be at most 100.
 
Sample Input:
5
x
xx*
xxx**
*xx
xx*xx**
 
Sample Output:
0
0
0
2
0
 
Explanation:
 
For the first three cases, the input expression is already a valid RPN, so the answer is 0.
For the fourth case, we can perform one delete, and one insert operation: *xx -> xx -> xx*
[/b]

User avatar
Cool_Fire
Not a sandwich
Posts: 1912
Joined: Fri May 09, 2003 1:20 pm
Location: 41 6d 73 74 65 72 64 61 6d
Contact:

Re: Any body has a solution to this code..!!

Post by Cool_Fire » Wed Sep 05, 2012 6:50 pm

This is know as postfix notation. The only thing you need to do is push everything onto a stack until you hit an operator, pop the two operands and push the result back onto the stack.
If we're breaking the rules, then how come you can't catch us? You can't find us? I know why. Cause, it's ... MAGIC!
Hackerthreads chat, where the party is going 24/7.

Post Reply