逆向波兰语符号的C ++问题 [英] C++ question on Reverse polish notation

问题描述

大家好，

在我的大学评估考试中，有人问我这个问题.
谁能解决这个问题:

通过写两个操作数后跟运算符，可以用反向波兰表示法(RPN)编写由操作数和二进制运算符组成的表达式.例如，3 +(4 * 5)可以写为"3 4 5 * +".

系统会为您提供一个由x's和*'s组成的字符串. x表示操作数，*表示二进制运算符.很容易看出，并非所有此类字符串都代表有效的RPN表达式.例如，"x * x"不是有效的RPN表达式，而"xx *"和"xxx **"是有效的表达式.将给定字符串转换为有效RPN表达式所需的最小插入，删除和替换操作次数是多少?

输入:
第一行包含测试用例T的数量.后面是T个测试用例.每个案例包含一个仅包含字符x和*的字符串.

输出:
输出T行，每个测试用例一条，包含最少数量的操作.

限制条件:
1< = T< = 100
输入字符串的长度最多为100.

样本输入:
5
x
xx *
xxx **
* xx
xx * xx **

样本输出:
0
0
0
2
0

说明:

对于前三种情况，输入表达式已经是有效的RPN，因此答案为0.
对于第四种情况，我们可以执行一次删除和一项插入操作:* xx-> xx-> xx *

Hi All,

On my college assessment test I was asked this question.
Could any one please solve this question :

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*

推荐答案

我们不做作业:它的设置是有原因的.在这里，您可以考虑自己被告知的内容，并尝试理解它.也可以在那里帮助您的导师识别您的弱点，并将更多的注意力放在补救措施上.

自己尝试，您可能会发现它并不像您想的那么困难！

We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think!

这篇关于逆向波兰语符号的C ++问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！