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
This is one unusually big answer. I wouldn't be surprised if there exist also an elegant two-liner, but until that one is posted here's mine.
Imagine that you have a simple graph 2D, where x-axis denotes the parsing step, and y-axis denotes the difference between the current number of X's and stars, n(x)-n(*). For example, for input xx*xx** the graph would be this:
╫
╫ +
╫ + + +
╫ + + +
╬═╧═╧═╧═╧═╧═╧═╧
x x * x x * *
In order for expression to be valid this graph must never reach zero or below on y-axis, and at the end the value of y must be one (single value left on stack).
You are given three operations to be used on input expression: insert, delete, and replace. This replace operation is actually one of the two: replace x with *, and replace * with x. When you apply insert or delete somewhere in the middle of the expression the graph is changed so that from that point onward all points in graph are moved up or down. When replace is applied the points are moved up or down for two notches in the graph. One interesting note: we don't have to deal with delete operations, because the result is the same as applying the opposite insert, with the difference that inserts can be applied always and deletes only if there is a symbol available.
Your goal is to find minimal number of operations. If we would observe only the final goal (y=1) then we would determine the number of notches we have to move the graph and apply as much of replace operations as possible, and one additional insert operation. If total of N(x)-N(*) is N then number of operations would be floor((N-1)/2). The sign determines which operations are to be applied.
The problem is we must pay attention to the other condition, which is that graph must never reach zero. To determine this we must first apply previous operations on our expression. 'Insert x' is added at the start, 'insert *' comes at the end, search and replace every * with x going from start, and search and replace every x with * going from the end backwards.
After this step we have new expression. Iterate from the beginning and look for place where y=0. If there is such a place then you must insert one x before it, and compensate with inserting one * at the expression end. But remember that you already may have had done that (insert x at start, or insert * at end). If you have two inserts x then pretend it was actually replace * with x (one operation less), and forget about having to insert x. Analogously with pair of inserts *: remove two insert *, and apply one more 'replace x with *'. You really have to apply it, i.e change the expression, because if x that you find when search from end is actually before your current position then you can't apply replace, and so can't compact two insert operations into one replace.
Continue iteration until end, count for additional operations, and all the time keep in mind if you have one insert x and one insert *. That should be it. In the end you'll have a number of operations.