## dprediction

BAN USER- 0of 0 votes

AnswersAn 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 * +".

- dprediction in United States

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| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer C# - -2of 2 votes

AnswerAn 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 * +".

- dprediction in United States

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| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer C#

Rep**richardcstrong**, Accountant at AppPerfectI am a modern magician, except I transform complicated technical ideas into user-friendly images before the eyes of your company ...

Rep**markglove17**, Associate at Arista NetworksHi, I am Mark from North Edwards, CA .I am just crazy about dance.I am not professionally trained, but ...

Rep**novathomes**, abc at 8x8I am a friendly and outgoing person who enjoys greeting people with a smile. I have more than eight years ...

Rep**sherrymrex**, Computer Scientist at CGI-AMSI am Sherry from West Palm Beach USA, I started my journey in 2016 as a yoga teacher. I like ...

Rep**cherylthurber**, Developer Advocate at Absolute Softech LtdHi,I am from Taxes, USA. Passionate multilingual translator with 2.5 years experience in Spanish-English translations.Looking to further ...

Rep**SherriMooney**, Network Engineer at Arista NetworksI am not a model but as a photographer, I can't see how one could call it fun. Matter ...

Rep**aalvinbrowne**, Android Engineer at ASAPInfosystemsPvtLtdWorking as an Agricultural laborer at Mars Music I maintain yields like natural products, vegetables, grains, and nuts, or take ...

Rep**HelanZelda**, Consultant at AdventHelanZelda from Atlanta, GA, United States. I have a passion for exploring/sharing new ideas and experiences throughout the interdisciplinary ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

This code doesn't solve the problem.

- dprediction April 03, 2012First of all there are 3 operations: deletion, addition and replacement.

What your input string is *******?

I believe this needs a dynamic programming approach.