需要多少操作才能将RPN字符串转换为有效的RPN字符串？

Question

今天早上早些时候，我在这个问题上的面试失败了，也找不出原因。有人能帮我吗？

由操作数和二元运算符组成的表达式可以用反向波兰表示法(RPN)编写，方法是在操作符后面同时写入这两个操作数。例如，3+ (4 * 5)可以写成"3 4 5* +“。

给定一个由x和*‘组成的字符串。x表示操作数，*表示二元运算符。很容易看出，并非所有这样的字符串都表示有效的RPN表达式。例如，"x*x“不是有效的RPN表达式，而"xx*”和"xxx**“是有效的表达式。将给定的字符串转换为有效的RPN表达式所需的最小插入、删除和替换操作次数是多少？

5
x
xx*
xxx**
*xx
xx*xx**

输出

0
0
0
2
0

到目前为止的代码：

import fileinput

def solution (rpn):
    xs = 0
    numReplaces = 0
    numDeletes = 0
    numInserts = 0

    for i in xrange(len(rpn)):
        if rpn[i] == 'x':
            xs += 1
        elif rpn[i] == '*':
            if xs > 1:
                xs -= 1
            elif xs == 1:
                if numDeletes > 0:
                   numReplaces += 1
                   numDeletes -= 1
                else:
                    if i == len(rpn)-1:
                        numInserts += 1
                    else:
                        numDeletes += 1
            else:
                if numDeletes > 1:
                    numDeletes -= 2
                    numReplaces += 2
                else:
                    numDeletes += 1

    while xs > 1:
        if xs > 2:
            numReplaces += 1
            xs -= 2
        if xs == 2:
            numInserts += 1
            xs -= 1

    return numReplaces + numDeletes + numInserts

    first = True
    for line in fileinput.input():
        if first:
            numCases = int(line)
            first = False

        else:
            print solution(line)

Answer 1

我认为开始的方法是，RPM计算可以通过维护一个操作数堆栈来轻松执行。对于有效的输入字符串，当您点击一个运算符时，您将最后两个值从堆栈中弹出，应用该运算符，并将结果推回到堆栈。

因此，我们需要找到每个“修复”所增加的价值：

1. Insert

- Operand: you hit an operator, and there is only one item on the stack
- Operator: You finish the string and there are multiple items left on the stack

​

1. Delete

- Operand: you are at the end of the string. Adding operators will have the same result
- Operator: there is only one item on the stack, adding an operand will have the same result. If the stack is empty, delete the operator

​

1. Replace

- Operator -> operand: There is only one operand on the stack
- Operand -> operator: _Here be dragons._ I believe that this will be useful only when you're out of operators, meaning the stack size is > 1; unfortunately, we don't know if these are direct operands or the result of operations, so we'll just add `n-1` operators to condense the stack into a result.

​

我不能百分之百地确定这些，但听起来任何错误情况都可以由它们中的任何一个来处理，成本相等，所以：

def count_errors(input_):
    def tokenize(input_):
        ''' for our purposes, each character is a token '''
        for char in input_:
            yield char

    def is_operator(val):
        return val == '*'

    def is_operand(val):
        return val == 'x'

    stack = []
    error = 0
    for token in tokenize(input_):
        if is_operand(token):
            stack.append(token)
        elif is_operator(token):
            if len(stack) >= 2:
                stack.pop()
                stack.pop()
                stack.append('x')
            elif len(stack) == 1:
                stack.pop()
                stack.append('x')
                errors += 1
            else:
                errors += 1

    if len(stack):
        return errors + len(stack) - 1
    else:
        return errors + 1