0

我今天早上早些时候在这个问题上的面试失败了，并且无法弄清楚为什么。谁能帮我吗？

由操作数和二元运算符组成的表达式可以用逆波兰表示法 (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)
4

1 回答 1

0

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

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

  1. 插入

    • 操作数：你点击了一个操作符，堆栈中只有一项
    • 操作员：你完成了字符串，堆栈上还有多个项目

  2. 删除

    • 操作数：你在字符串的末尾。添加运算符将具有相同的结果
    • 运算符：栈中只有一项，添加一个操作数将得到相同的结果。如果堆栈为空，则删除操作符

  3. 代替

    • 运算符 -> 操作数：栈上只有一个操作数
    • 操作数 -> 运算符：这里是龙。我相信这仅在您没有运算符时才有用，这意味着堆栈大小> 1；不幸的是，我们不知道这些是直接操作数还是运算的结果，所以我们只是添加n-1运算符以将堆栈压缩为结果。

我不是 100% 确定这些，但听起来任何错误情况都可以由其中任何一个以相同的成本处理，所以：

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
于 2013-11-07T19:40:52.953 回答